i have a an exam from Numerical Linear Algebra and Applications, Biswa Nath Datta,

for my universty
i will send the Contents of the book.
my teacher told me about exam would be from this subjects:
‫اعداد ممیز شناور‬
‫خظای نسبی و مطلق‬
‫ تجزیه ماتریسی‬qr
‫ تجزیه ماتریسی‬lu ‫با محور و بدون محور‬
svd
Cholesky
‫ماتریس های معین مثبت‬
‫مقدار ویژه‬
‫بردار ویژه‬
‫حذف گواسی‬
‫دستگاه خطی‬
‫عدد حالت‬
‫پایداری‬

- give me the list of chepter that shuld i read form book

Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . xvii

0.1 Special
Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . xvii
0.2 Additional Features and Topics for Second Edition . . . . . . . . . . . . . . .
. . . . . . xix
0.3 Intended Audience . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . xx
0.4 Some Guidelines for Using this Book . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . xx
0.4.1 A First Course in Numerical Linear Algebra (Advanced Undergraduate/One
Semester) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . xxi
0.4.2 A Second Course in Numerical Linear Algebra (Beginning Graduate Course) . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. xxi
0.4.3 A One-Semester Course in Numerical Linear Algebra for Engineers . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
xxii
0.5 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . xxii

1 Linear Algebra Problems, Their Importance, and Computational Difficulties . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . 1

1.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . 1
1.2 Fundamental Linear Algebra Problems and Their
Importance . . . . . . . . . . . . . 1
1.3 Computational Difficulties Using Theoretical Linear Algebra
Techniques . . . . . . 3

2 A Review of Some Required Concepts from Core Linear Algebra . . . . . . . 7

2.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . 7
2.2 Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . 7
2.2.1 Orthogonality, Subspace, and
Basis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3
Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . 9
2.3.1 Range and Null Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . 12
2.3.2 Rank of a
Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . 12
2.3.3 The Inverse of a Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . 13
2.3.4 Similar Matrices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . 14
2.4 Some Special Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . 14
2.4.1 Diagonal and Triangular
Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.4.2 Unitary and Orthogonal Matrices . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . 15
2.4.3 Symmetric and Hermitian
Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.4.4 Hessenberg Matrices (Almost Triangular) . . . . . . . . . . . . . . . . . . .
. . . . 16
2.5 Vector and Matrix Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . 17
2.5.1 Vector
Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . 17
2.5.2 Matrix
Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . 18
2.5.3 Norms and
Inverses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . 22
2.5.4 Norm Invariant Properties of Orthogonal and Unitary Matrices . . . . . . . 22
2.6 Singular Value
Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
2.7 Review and
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . 24
2.7.1 Special
Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . 24
2.7.2 Rank, Determinant, Inverse, and Eigenvalues . . . . . . . . . . . . . . . . .
. . . 24
2.7.3 Vector and Matrix Norms . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . 24
2.8 Suggestions for Further Reading . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . 24
Exercises on Chapter
2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . 25
3 Floating Point Numbers and Errors in Computations . . . . . . . . . . . . . . .
29

3.1 Floating Point Number Systems . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . 29
3.2 Rounding Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . 31
3.3 Laws of Floating Point Arithmetic . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . 33
3.4 Addition of n Floating Point
Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.5 Multiplication of n Floating Point
Numbers . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.6 Inner Product Computation . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . 38
3.7 Error Bounds for Floating Point Matrix Operations . . . . . . . . . . . . . . .
. . . . 39
3.8 Round-Off Errors Due to Cancellation and Recursive Computations . . . . . . 40
3.9 Review and
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . 44
3.10 Suggestions for Further
Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
Exercises on Chapter
3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . 45

4 Stability of Algorithms and Conditioning of

Problems . . . . . . . . . . . . . . . . 49

4.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . 49
4.1.1 Computing the Norm of a
Vector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.1.2 Computing the Inner Product of Two
Vectors . . . . . . . . . . . . . . . . . . . . 49
4.1.3 Solution of an Upper Triangular
System . . . . . . . . . . . . . . . . . . . . . . . . 51
4.1.4 Solution of a Lower Triangular System . . . . . . . . . . . . . . . . . . . .
. . . . 51
4.2 Efficiency of an
Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . 52
4.3 Definition and Concept of Stability . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . 52
4.4 Conditioning of the Problem and Perturbation Analysis . . . . . . . . . . . . .
. . . 57
4.5 Conditioning of the Problem, Stability of the Algorithm, and Accuracy of the
Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . 59
4.6 Perturbation Analysis of the Linear System
Problem . . . . . . . . . . . . . . . . . . 61
4.6.1 Effect of Perturbation on the Right-Hand Side Vector
b . . . . . . . . . . . . 61
4.6.2 Effect of Perturbation in the Matrix
A . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.6.3 Effect of Perturbations in Both Matrix A and Vector b . . . . . . . . . . . .
. 65
4.7 Some Properties of the Condition Number of a Matrix . . . . . . . . . . . . . .
. . 67
4.7.1 Some Well-Known Ill-Conditioned
Matrices . . . . . . . . . . . . . . . . . . . . . 68
4.7.2 How Large Must the Condition Number Be for Ill-Conditioning? . . . . . . 69
4.7.3 The Condition Number and Nearness to Singularity . . . . . . . . . . . . . .
69
4.7.4 Examples of Ill-Conditioned Eigenvalue Problems . . . . . . . . . . . . . . .
. . 70
4.8 Some Guidelines for Designing Stable Algorithms . . . . . . . . . . . . . . . .
. . . . 72
4.9 Review and
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . 72
4.9.1 Conditioning of the Problem . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 72
4.9.2 Stability of an Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . 73
4.9.3 Effects of Conditioning and Stability on the Accuracy of the Solution . . . .
74
4.10 Suggestions for Further
Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
Exercises on Chapter
4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . 74

5 Gaussian Elimination and LU Factorization . . . . . . . . . . . . . . . . . . . .

. . . . . 81

5.1 A Computational Template in Numerical Linear

Algebra . . . . . . . . . . . . . . . 81
5.2 LU Factorization Using Gaussian Elimination . . . . . . . . . . . . . . . . . .
. . . . . 82
5.2.1 Creating Zeros in a Vector or Matrix Using Elementary Matrix . . . . . . . .
83
5.2.2 Triangularization Using Gaussian
Elimination . . . . . . . . . . . . . . . . . . . . 84
5.2.3 Permutation Matrices and Their Properties . . . . . . . . . . . . . . . . . .
. . . . 96
5.2.4 Gaussian Elimination with Partial Pivoting (GEPP) . . . . . . . . . . . . . .
. 97
5.2.5 Gaussian Elimination with Complete Pivoting (GECP) . . . . . . . . . . . .
104
5.2.6 Summary of Gaussian Elimination and LU Factorizations . . . . . . . . . . 106
5.3 Stability of Gaussian Elimination . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . 106
5.4 Summary and Table of
Comparisons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
5.4.1 Elementary Lower Triangular
Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . 110
5.4.2 LU
Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . 110
5.4.3 Stability of Gaussian Elimination . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 110
5.4.4 Table of
Comparisons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. 110
5.5 Suggestions for Further Reading . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . 110
Exercises on Chapter
5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . 111

6 Numerical Solutions of Linear Systems . . . . . . . . . . . . . . . . . . . . . .

. . . . . . 117

6.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . 117
6.2 Basic Results on Existence and Uniqueness . . . . . . . . . . . . . . . . . . .
. . . . . 118
6.3 Some Applications Giving Rise to Linear Systems
Problems . . . . . . . . . . . . 119
6.3.1 An Electric Circuit Problem . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . 119
6.3.2 Analysis of a Processing Plant Consisting of Interconnected Reactors . . 120
6.3.3 Linear Systems Arising from Ordinary Differential Equations: A Case Study on
a Spring-Mass Problem . . . . . . . . . . . . . . . . . . . . . . 122
6.3.4 Linear Systems Arising from Partial Differential Equations: A Case Study on
Temperature Distribution . . . . . . . . . . . . . . . . . . . . 123
6.3.5 Approximation of a Function by a Polynomial: Hilbert System . . . . . . 128
6.4 LU Factorization Methods. . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . 129
6.4.1 Solution of the System Ax = b Using LU Factorization . . . . . . . . . . . .
129
6.4.2 Solution of Ax = b Using Factorization: MA =
U . . . . . . . . . . . . . . . . 132
6.4.3 Solution of Ax = b without Explicit Factorization . . . . . . . . . . . . . .
. . 132
6.4.4 Solving a Linear System with Multiple Right-Hand Sides . . . . . . . . . .
134
6.5 Scaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . 135
6.6 Concluding Remarks on the Use of Gaussian Elimination for Linear Systems . .
136
6.7 Inverses and
Determinant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . 136
6.7.1 Avoiding Explicit Computation of the
Inverses. . . . . . . . . . . . . . . . . . . 137
6.7.2 The Sherman-Morrison Formula for Matrix Inverse . . . . . . . . . . . . . .
137
6.7.3 Computing the Inverse of an Arbitrary Nonsingular Matrix . . . . . . . . .
138
6.7.4 Computing the Determinant of a Matrix . . . . . . . . . . . . . . . . . . . .
. . . 139
6.8 Effect of the Condition Number on Accuracy of the Computed Solution . . . . 139
6.8.1 Conditioning and Pivoting . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 140
6.8.2 Conditioning and
Scaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
6.9 Computing and Estimating the Condition Number . . . . . . . . . . . . . . . . .
. 141
6.10 Componentwise Perturbations and the Errors . . . . . . . . . . . . . . . . . .
. . . . 143
6.11 Iterative Refinement . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . 144
6.12 Special Systems: Positive Definite, Diagonally Dominant, Hessenberg, and
Tridiagonal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . 146
6.12.1 Special Linear Systems Arising from Finite Difference Methods . . . . . .
147
6.12.2 Special Linear Systems Arising from Finite Element Methods . . . . . . . 150
6.12.3 Symmetric Positive Definite
Systems . . . . . . . . . . . . . . . . . . . . . . . . . 153
6.12.4 Hessenberg
System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
158
6.12.5 Diagonally Dominant
Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
6.12.6 Tridiagonal Systems. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . 161
6.13 Review and Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . 167
6.13.1 Numerical Methods for Arbitrary Linear System Problems . . . . . . . . . 167
6.13.2 Special
Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . 168
6.13.3 Inverse and
Determinant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
168
6.13.4 The Condition Number and Accuracy of
Solution . . . . . . . . . . . . . . . . 169
6.13.5 Iterative
Refinement. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . 169
6.14 Suggestions for Further
Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
Exercises on Chapter
6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . 170

7 QR Factorization, Singular Value Decomposition, and Projections . . . . . 181

7.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . 181
7.2 Householder's Matrices and QR Factorization . . . . . . . . . . . . . . . . . .
. . . . 183
7.2.1 Definition and Basic Properties . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 183
7.2.2 Householder's Method for QR Factorization . . . . . . . . . . . . . . . . . .
. . 188
7.3 Complex QR
Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . 194
7.4 Givens Matrices and QR
Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
7.4.1 Definition and Basic Properties . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 194
7.4.2 Givens Method for QR
Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . 199
7.4.3 QR Factorization of a Hessenberg Matrix Using Givens Matrices . . . . . . 201
7.5 Classical and Modified Gram-Schmidt Algorithms for QR Factorizations . . . .
202
7.6 Solution of Ax = b Using QR Factorization . . . . . . . . . . . . . . . . . . .
. . . . . 208
7.7 Projections Using QR
Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
7.7.1 Orthogonal Projections and Orthonormal
Bases . . . . . . . . . . . . . . . . . 209
7.7.2 Projection of a Vector onto the Range and the Null Space of a Matrix . . 210
7.7.3 Orthonormal Bases and Orthogonal Projections onto the Range and Null Space
Using QR Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
210
7.8 Singular Value Decomposition and Its Properties . . . . . . . . . . . . . . . .
. . . . . 211
7.8.1 Singular Values and Singular
Vectors . . . . . . . . . . . . . . . . . . . . . . . . . . 212
7.8.2 Computation of the SVD (MATLAB Command) . . . . . . . . . . . . . . . . . 213
7.8.3 The SVD of a Complex Matrix . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . 213
7.8.4 Geometric Interpretation of the Singular Values and Singular Vectors . . .
214
7.8.5 Reduced SVD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . 214
7.8.6 Sensitivity of the Singular
Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215
7.8.7 Norms, Condition Number, and Rank via the SVD . . . . . . . . . . . . . . .
216
7.8.8 The Distance to Singularity, Rank-Deficiency, and Numerical Rank via the
SVD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . 217
7.8.9 Numerical Rank. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . 219
7.8.10 Orthonormal Bases and Projections from the SVD . . . . . . . . . . . . . . .
220
7.9 Some Practical Applications of the
SVD . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
7.10 Geometric Mean and Generalized Triangular Decompositions . . . . . . . . . .
226
7.11 Review and Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . 227
7.11.1 QR Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . 227
7.11.2 The SVD, GMD, and
GTD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
7.11.3
Projections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . 228
7.12 Suggestions for Further
Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
Exercises on Chapter
7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . 228

8 Least-Squares Solutions to Linear Systems . . . . . . . . . . . . . . . . . . . .

. . . . . 237

8.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . 237
8.2 Geometric Interpretation of the Least-Squares Problem . . . . . . . . . . . . .
. . . 238
8.3 Existence and
Uniqueness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . 239
8.3.1 Existence and Uniqueness
Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . 240
8.3.2 Normal Equations, Projections, and Least-Squares Solutions . . . . . . . .
241
8.4 Some Applications of the Least-Squares
Problem . . . . . . . . . . . . . . . . . . . . 242
8.4.1 Polynomial-Fitting to Experimental
Data. . . . . . . . . . . . . . . . . . . . . . . 242
8.4.2 Predicting Future Sales . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . 245
8.5 Pseudoinverse and the Least-Squares Problem . . . . . . . . . . . . . . . . . .
. . . . 245
8.6 Sensitivity of the Least Squares
Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 246
8.7 Computational Methods for Overdetermined Problems: Normal Equations, QR, and
SVD Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . 252
8.7.1 The Normal Equations Method . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . 252
8.7.2 QR Factorization Method . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 254
8.7.3 The SVD
Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . 259
8.7.4 Solving the Linear System Using the SVD . . . . . . . . . . . . . . . . . . .
. . 263
8.8 Underdetermined Linear
Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
8.8.1 The QR Approach for the Minimum-Norm Solution . . . . . . . . . . . . . . 264
8.8.2 The SVD Approach for the Minimum-Norm Solution . . . . . . . . . . . . . 265
8.9 Least-Squares Iterative
Refinement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
8.10 Review and Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . 269
8.10.1 Existence and Uniqueness . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . 269
8.10.2 Overdetermined
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
8.10.3 The Underdetermined
Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
8.10.4 Perturbation
Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
270
8.10.5 Iterative
Refinement. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . 270
8.10.6 Comparison of Least-Squares
Methods . . . . . . . . . . . . . . . . . . . . . . . . 270
8.11 Suggestions for Further
Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
Exercises on Chapter
8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . 271

9 Numerical Matrix Eigenvalue

Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
9.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . 281
9.2 Eigenvalue Problems Arising in Practical
Applications. . . . . . . . . . . . . . . . . . 282
9.2.1 Stability Problems for Differential and Difference
Equations . . . . . . . . . 282
9.2.2 Phenomenon of Resonance . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . 285
9.2.3 Buckling Problem (a Boundary Value Problem) . . . . . . . . . . . . . . . . .
. 286
9.2.4 Simulating Transient Current for an Electric
Circuit . . . . . . . . . . . . . . . . 288
9.2.5 An Example of the Eigenvalue Problem Arising in Statistics: Principal
Component
Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
290
9.3 Localization of Eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . 292
9.3.1 The Gersgorin Disk Theorems . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . 293
9.3.2 Eigenvalue Bounds and Matrix
Norms . . . . . . . . . . . . . . . . . . . . . . . . 295
9.4 Computing Selected Eigenvalues and
Eigenvectors. . . . . . . . . . . . . . . . . . . . 295
9.4.1 The Power Method, the Inverse Iteration, and the Rayleigh Quotient
Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . 296
9.5 Similarity Transformations and Eigenvalue
Computations . . . . . . . . . . . . . . 304
9.5.1 Diagonalization of a Matrix . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . 305
9.5.2 Numerical Instability of Nonorthogonal
Diagonalization . . . . . . . . . . . . 306
9.5.3 Reduction to Hessenberg Form via Orthogonal Similarity . . . . . . . . . . .
307
9.5.4 Uniqueness of Hessenberg
Reduction . . . . . . . . . . . . . . . . . . . . . . . . . 312
9.5.5 Eigenvalue Computations Using the Characteristic Polynomial . . . . . . . 313
9.6 Eigenvalue
Sensitivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . 315
9.6.1 The Bauer-Fike
Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
9.6.2 Sensitivity of the Individual Eigenvalues . . . . . . . . . . . . . . . . . .
. . . . . 317
9.7 Eigenvector Sensitivity . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . 319
9.8 The Real Schur Form and QR Iterations . . . . . . . . . . . . . . . . . . . . .
. . . . . . 320
9.8.1 The Basic QR
Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
322
9.8.2 The Hessenberg QR Iteration . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . 324
9.8.3 Convergence of the QR Iterations and the Shift of
Origin . . . . . . . . . . . 325
9.8.4 The Double-Shift QR Iteration . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . 326
9.8.5 Implicit QR Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . 327
9.8.6 Obtaining the Real Schur Form A . . . . . . . . . . . . . . . . . . . . . . .
. . . . . 331
9.8.7 The Real Schur Form and Invariant Subspaces . . . . . . . . . . . . . . . . .
. 334
9.9 Computing the Eigenvectors. . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . 335
9.9.1 The Hessenberg-Inverse
Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
9.10 Review and Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . 336
9.10.1 Applications of the Eigenvalues and Eigenvectors . . . . . . . . . . . . . .
. . 336
9.10.2 Localization of
Eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336
9.10.3 The Power Method and the Inverse Iteration . . . . . . . . . . . . . . . . .
. . . 337
9.10.4 The Rayleigh Quotient
Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337
9.10.5 Sensitivity of Eigenvalues and
Eigenvectors . . . . . . . . . . . . . . . . . . . . 337
9.10.6 Eigenvalue Computation via the Characteristic Polynomial and the Jordan
Canonical Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338
9.10.7 Hessenberg
Transformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338
9.10.8 The QR Iteration Algorithm . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 338
9.10.9 Ordering the Eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . 339
9.10.10 Computing the
Eigenvectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
9.11 Suggestions for Further
Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
Exercises on Chapter
9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . 341

10 Numerical Symmetric Eigenvalue Problem and Singular Value

Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . 351

10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . 351
10.2 Computational Methods for the Symmetric Eigenvalue Problem . . . . . . . . .
352
10.2.1 Some Special Properties of the Symmetric Eigenvalue Problem . . . . . . 352
10.2.2 The Bisection Method for the Symmetric Tridiagonal Matrix . . . . . . . .
354
10.2.3 The Symmetric QR Iteration
Method . . . . . . . . . . . . . . . . . . . . . . . . . 357
10.2.4 The Divide-and-Conquer Method. . . . . . . . . . . . . . . . . . . . . . . .
. . . . 359
10.2.5 The Jacobi
Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
363
10.2.6 Comparison of the Symmetric Eigenvalue Methods . . . . . . . . . . . . . . .
364
10.3 The Singular Value Decomposition and Its Computation . . . . . . . . . . . . .
. . 365
10.3.1 The Relationship between the Singular Values and the Eigenvalues . . . 366
10.3.2 Sensitivity of the Singular Values . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . 367
10.3.3 Computing the Variance-Covariance Matrix with SVD . . . . . . . . . . . .
367
10.3.4 Computing the Pseudoinverse with SVD . . . . . . . . . . . . . . . . . . . .
. . 368
10.3.5 Computing the
SVD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369
10.3.6 The Golub-Kahan-Reinsch
Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 370
10.3.7 The Chan SVD Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . 378
10.4 Generalized
SVD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . 379
10.5 Review and Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . 380
10.5.1 The Symmetric Eigenvalue Computation . . . . . . . . . . . . . . . . . . . .
. . 380
10.5.2 The
SVD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . 380
10.6 Suggestions for Further
Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
Exercises on Chapter 10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . 381

11 Generalized and Quadratic Eigenvalue

Problems . . . . . . . . . . . . . . . . . . . 387

11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . 387
11.2 Eigenvalue-Eigenvector Properties of Equivalent
Pencils . . . . . . . . . . . . . . . 389
11.3 Generalized Schur and Real Schur
Decompositions . . . . . . . . . . . . . . . . . . 389
11.4 The QZ Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . 390
11.4.1 Stage I: Reduction to Hessenberg Triangular Form . . . . . . . . . . . . . .
. 391
11.4.2 Stage II: Reduction to the Generalized Real Schur Form . . . . . . . . . . .
393
11.5 Computations of Generalized Eigenvectors . . . . . . . . . . . . . . . . . . .
. . . . . . 398
11.6 The Symmetric Positive Definite Generalized Eigenvalue Problem . . . . . . . .
399
11.6.1 Eigenvalues and Eigenvectors of Symmetric Definite Pencil . . . . . . . . .
399
11.6.2 Conditioning of the Eigenvalues of the Symmetric Definite Pencil . . . . .
400
11.6.3 The QZ Method for the Symmetric Definite
Pencil . . . . . . . . . . . . . . . 400
11.6.4 The Cholesky QR Algorithm for the Symmetric Definite Pencil . . . . . . .
401
11.6.5 Diagonalization of the Symmetric Definite Pencil: Simultaneous
Diagonalization of A and
B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402
11.6.6 Generalized Rayleigh
Quotient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404
11.7 Symmetric Definite Generalized Eigenvalue Problems Arising in Vibrations of
Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . 405
11.7.1 Vibration of a Building: A Case
Study . . . . . . . . . . . . . . . . . . . . . . . . 405
11.7.2 Forced Harmonic Vibration; Phenomenon of Resonance . . . . . . . . . . . 406
11.8 Applications of Symmetric Positive Definite Generalized Eigenvalue Problem to
Decoupling and Model
Reduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409
11.8.1 Decoupling of a Second-Order
System . . . . . . . . . . . . . . . . . . . . . . . . 410
11.8.2 The Reduction of a Large Model . . . . . . . . . . . . . . . . . . . . . . .
. . . . . 415
11.8.3 A Case Study on the Potential Damage of a Building Due to an
Earthquake . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . 415
11.9 The Quadratic Eigenvalue Problem . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . 418
11.9.1 Orthogonality Relations of the Eigenvectors of Quadratic Matrix Pencil . 419
11.9.2 Applications of the Quadratic Eigenvalue Problem . . . . . . . . . . . . . .
. 421
11.9.3 Numerical Methods for the Quadratic Eigenvalue Problem. . . . . . . . . .
422
11.10 Review and
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . 424
11.10.1 Existence Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . 424
11.10.2 The QZ
Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. 424
11.10.3 The Generalized Symmetric Eigenvalue
Problem . . . . . . . . . . . . . . . . 424
11.10.4 The Quadratic Eigenvalue
Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 426
11.11 Suggestions for Further Reading . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . 426
Exercises on Chapter 11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . 427

12 Iterative Methods for Large and Sparse Problems: An Overview . . . . . . . 435

12.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . 435
12.2 The Jacobi, Gauss-Seidel, and SOR
Methods . . . . . . . . . . . . . . . . . . . . . . . 436
12.2.1 Convergence of the Jacobi, Gauss-Seidel, and SOR Methods . . . . . . . . 438
12.3 Krylov Subspace Methods for Linear Systems: Lanczos, Arnoldi, GMRES, Conjugate
Gradient, and QMR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
445
12.3.1 The Basic Arnoldi Method . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 446
12.3.2 Solving Ax = b Using the Arnoldi
Method . . . . . . . . . . . . . . . . . . . . . . 448
12.3.3 The GMRES Method for Solving Ax =
b . . . . . . . . . . . . . . . . . . . . . . 451
12.3.4 Solving Shifted Linear Systems Using the Arnoldi Method. . . . . . . . . .
454
12.3.5 The Symmetric Lanczos
Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 455
12.3.6 The Conjugate Gradient
Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . 456
12.3.7 Solving Indefinite Symmetric Systems Using CG-Type Methods: MINRES and
SYMMLQ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
12.3.8 The Nonsymmetric Lanczos
Method . . . . . . . . . . . . . . . . . . . . . . . . . 462
12.3.9 Solving Linear System Ax = b Using the Lanczos Algorithm . . . . . . . . 464
12.3.10 The Bi-conjugate Gradient Algorithm . . . . . . . . . . . . . . . . . . . .
. . . . . 464
12.3.11 The QMR Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . 466
12.4
Preconditioners . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . 467
12.4.1 Classical Iterative Methods as Preconditioners . . . . . . . . . . . . . . .
. . . 468
12.4.2 Polynomial Preconditioners . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 468
12.4.3 Incomplete LU (ILU) Factorization as a Preconditioner . . . . . . . . . . .
469
12.4.4 Preconditioning with Incomplete Cholesky Factorization . . . . . . . . . . .
469
12.4.5 Numerical Experiments on Performance Comparison . . . . . . . . . . . . . .
470
12.5 Comparison of Krylov Subspace Methods for Linear Systems . . . . . . . . . . .
. 470
12.6 Eigenvalue Approximation Using Krylov Subspace Methods . . . . . . . . . . . .
473
12.6.1 Eigenvalue Approximation Using the Arnoldi Method . . . . . . . . . . . . .
474
12.6.2 Implicitly Restarted Arnoldi Method for the Nonsymmetric Eigenvalue
Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . 475
12.6.3 Computing the Eigenvalues of a Symmetric Matrix Using the Symmetric Lanczos
Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. 477
12.7 The Bisection Method for the Tridiagonal Symmetric Positive Definite
Generalized Eigenvalue
Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . 478
12.7.1 The Bisection Method for Tridiagonal A and B . . . . . . . . . . . . . . . .
. . 479
12.8 Krylov Subspace Methods for Generalized Eigenvalue Problems . . . . . . . . .
479
12.9 Krylov Subspace Methods for the Quadratic Eigenvalue Problem . . . . . . . .
481
12.10 The Jacobi-Davidson Method for the Quadratic Eigenvalue Problem. . . . . . .
482
12.11 Review and
Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . 483
12.11.1 The Classical Iterative Methods . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 483
12.11.2 Krylov Subspace Methods . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . 484
12.11.3 Large Eigenvalue
Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485
12.12 Suggestions for Further Reading . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . 485
Exercises on Chapter 12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . 486

13 Some Key Terms in Numerical Linear Algebra . . . . . . . . . . . . . . . . . . .

. . . 493

Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . 501

Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . 523