English
资源说明：APPLIED
NUMERICAL
LINEAR
ALGEBRA
James W. Demmel
University of California
Berkeley, California
Society for Industrial and Applied Mathematics
Philadelphia
Contents
Preface ix
1 Introduction 1
1.1 Basic Notation 1
1.2 Standard Problems of Numerical Linear Algebra 1
1.3 General Techniques 2
1.3.1 Matrix Factorizations 3
1.3.2 Perturbation Theory and Condition Numbers 4
1.3.3 Effects of Roundoff Error on Algorithms 5
1.3.4 Analyzing the Speed of Algorithms 5
1.3.5 Engineering Numerical Software 6
1.4 Example: Polynomial Evaluation 7
1.5 Floating Point Arithmetic 9
1.5.1 Further Details 12
1.6 Polynomial Evaluation Revisited 15
1.7 Vector and Matrix Norms 19
1.8 References and Other Topics for Chapter 1 23
1.9 Questions for Chapter 1 24
2 Linear Equation Solving 31
2.1 Introduction 31
2.2 Perturbation Theory 32
2.2.1 Relative Perturbation Theory 35
2.3 Gaussian Elimination 38
2.4 Error Analysis 44
2.4.1 The Need for Pivoting 45
2.4.2 Formal Error Analysis of Gaussian Elimination 46
2.4.3 Estimating Condition Numbers 50
2.4.4 Practical Error Bounds 54
2.5 Improving the Accuracy of a Solution 60
2.5.1 Single Precision Iterative Refinement 62
2.5.2 Equilibration 62
2.6 Blocking Algorithms for Higher Performance 63
2.6.1 Basic Linear Algebra Subroutines (BLAS) 66
2.6.2 How to Optimize Matrix Multiplication 67
2.6.3 Reorganizing Gaussian Elimination to Use Level 3 BLAS 72
2.6.4 More About Parallelism and Other Performance Issues . 75
vi
Contents
2.7
2.8
2.9
Special Linear Systems
2.7.1 Real Symmetric Positive Definite Matrices
2.7.2 Symmetric Indefinite Matrices
2.7.3 Band Matrices
2.7.4 General Sparse Matrices
2.7.5 Dense Matrices Depending on Fewer Than O(n2) Pa-
rameters
References and Other Topics for Chapter 2
Questions for Chapter 2
76
76
79
79
83
90
93
93
3 Linear Least Squares Problems
101
3.1 Introduction
101
3.2 Matrix Factorizations That Solve the Linear Least Squares Prob-
lem
105
3.2.1 Normal Equations
106
3.2.2 QR Decomposition
107
3.2.3 Singular Value Decomposition
109
3.3 Perturbation Theory for the Least Squares Problem
117
3.4 Orthogonal Matrices
118
3.4.1 Householder Transformations
119
3.4.2 Givens Rotations
121
3.4.3 Roundoff Error Analysis for Orthogonal Matrices . . . . 123
3.4.4 Why Orthogonal Matrices?
124
3.5 Rank-Deficient Least Squares Problems
125
3.5.1 Solving Rank-Deficient Least Squares Problems Using
the SVD
128
3.5.2 Solving Rank-Deficient Least Squares Problems Using
QR with Pivoting
130
3.6 Performance Comparison of Methods for Solving Least Squares
Problems
132
3.7 References and Other Topics for Chapter 3
134
3.8 Questions for Chapter 3
134
4
Nonsymmetric Eigenvalue Problems
4.1 Introduction
4.2 Canonical Forms
4.2.1 Computing Eigenvectors from the Schur Form
4.3 Perturbation Theory
4.4 Algorithms for the Nonsymmetric Eigenproblem
4.4.1 Power Method
4.4.2 Inverse Iteration
4.4.3 Orthogonal Iteration
4.4.4 QR Iteration
4.4.5 Making QR Iteration Practical
4.4.6 Hessenberg Reduction
139
139
140
148
148
153
154
155
156
159
163
164
Contents
4.5
4.6
4.7
4.8
vii
4.4.7
4.4.8
Other
4.5.1
4.5.2
Tridiagonal and Bidiagonal Reduction
166
QR Iteration with Implicit Shifts
167
Nonsymmetric Eigenvalue Problems
173
Regular Matrix Pencils and Weierstrass Canonical Form 173
Singular Matrix Pencils and the Kronecker
Canonical Form
180
4.5.3 Nonlinear Eigenvalue Problems
183
Summary
184
References and Other Topics for Chapter 4
187
Questions for Chapter 4
187
5 The Symmetric Eigenproblem and Singular Value Decompo-
sition
195
5.1 Introduction
195
5.2 Perturbation Theory
197
5.2.1 Relative Perturbation Theory
207
5.3 Algorithms for the Symmetric Eigenproblem
210
5.3.1 Tridiagonal QR Iteration
212
5.3.2 Rayleigh Quotient Iteration
214
5.3.3 Divide-and-Conquer
216
5.3.4 Bisection and Inverse Iteration
228
5.3.5 Jacobi's Method
232
5.3.6 Performance Comparison
235
5.4 Algorithms for the Singular Value Decomposition
237
5.4.1 QR Iteration and Its Variations for the Bidiagonal SVD 242
5.4.2 Computing the Bidiagonal SVD to High Relative Accuracy245
5.4.3 Jacobi's Method for the SVD
248
5.5 Differential Equations and Eigenvalue Problems
254
5.5.1 The Toda Lattice
255
5.5.2 The Connection to Partial Differential Equations . . . . 259
5.6 References and Other Topics for Chapter 5
260
5.7 Questions for Chapter 5
260
6 Iterative Methods for Linear Systems
265
6.1 Introduction
265
6.2 On-line Help for Iterative Methods
266
6.3 Poisson's Equation
267
6.3.1 Poisson's Equation in One Dimension
267
6.3.2 Poisson's Equation in Two Dimensions
270
6.3.3 Expressing Poisson's Equation with Kronecker Products 274
6.4 Summary of Methods for Solving Poisson's Equation
277
6.5 Basic Iterative Methods
279
6.5.1 Jacobi's Method
281
6.5.2 Gauss-Seidel Method
282
6.5.3 Successive Overrelaxation
283
viii
Contents
6.5.4
Convergence of Jacobi's, Gauss-Seidel, and
SOR(u;) Methods on the Model Problem
6.5.5 Detailed Convergence Criteria for Jacobi's,
Gauss-Seidel, and SOR(o;) Methods
6.5.6 Chebyshev Acceleration and Symmetric SOR (SSOR) .
6.6 Krylov Subspace Methods
6.6.1 Extracting Information about A via Matrix-Vector Mul-
tiplication
6.6.2 Solving Ax = b Using the Krylov Subspace /C^
6.6.3 Conjugate Gradient Method
6.6.4 Convergence Analysis of the Conjugate Gradient Method
6.6.5 Preconditioning
6.6.6 Other Krylov Subspace Algorithms for Solving Ax = b .
6.7 Fast Fourier Transform
6.7.1 The Discrete Fourier Transform
6.7.2 Solving the Continuous Model Problem Using Fourier
Series
6.7.3 Convolutions
6.7.4 Computing the Fast Fourier Transform
6.8 Block Cyclic Reduction
6.9 Multigrid
6.9.1 Overview of Multigrid on the Two-Dimensional Poisson's
Equation
6.9.2 Detailed Description of Multigrid on the One-Dimensional
Poisson's Equation
6.10 Domain Decomposition
6.10.1 Nonoverlapping Methods
6.10.2 Overlapping Methods
6.11 References and Other Topics for Chapter 6
6.12 Questions for Chapter 6
285
286
294
299
301
305
307
312
316
319
321
323
324
325
326
327
331
332
337
347
348
351
356
356
7 Iterative Methods for Eigenvalue Problems 361
7.1 Introduction ^361
7.2 The Rayleigh-Ritz Method 362
7.3 The Lanczos Algorithm in Exact Arithmetic 366
7.4 The Lanczos Algorithm in Floating Point Arithmetic 375
7.5 The Lanczos Algorithm with Selective Orthogonalization . . . . 382
7.6 Beyond Selective Orthogonalization 383
7.7 Iterative Algorithms for the Nonsymmetric Eigenproblem . . . 384
7.8 References and Other Topics for Chapter 7 386
7.9 Questions for Chapter 7 386
Bibliography 389
Index 409
本源码包内暂不包含可直接显示的源代码文件，请下载源码包。
