Foreword......Page 6
Preface......Page 7
Acknowledgments......Page 9
Contents......Page 10
List of Figures......Page 17
List of Tables......Page 19
Listings......Page 20
1.1 Notation......Page 21
1.2 Vector Spaces and Subspaces......Page 25
1.2.1 Linear Independence and Bases......Page 26
1.2.2 Subspaces......Page 28
1.2.3 The Vector Spaces Rn and Cn......Page 30
1.3 Linear Systems......Page 31
1.3.1 Basic Properties......Page 32
1.3.2 The Inverse Matrix......Page 33
1.4 Determinants......Page 35
1.5 Eigenvalues, Eigenvectors and Eigenpairs......Page 38
1.6.1 Exercises Sect. 1.1......Page 40
1.6.2 Exercises Sect. 1.3......Page 41
1.6.3 Exercises Sect. 1.4......Page 42
Part I LU and QR Factorizations......Page 45
2.1 Cubic Spline Interpolation......Page 46
2.1.2 Piecewise Linear and Cubic Spline Interpolation......Page 47
2.1.3 Give Me a Moment......Page 50
2.1.4 LU Factorization of a Tridiagonal System......Page 53
2.2 A Two Point Boundary Value Problem......Page 56
2.2.1 Diagonal Dominance......Page 57
2.3.1 The Buckling of a Beam......Page 59
2.4 The Eigenpairs of the 1D Test Matrix......Page 60
2.5.1 Block Multiplication......Page 62
2.5.2 Triangular Matrices......Page 65
2.6.1 Exercises Sect. 2.1......Page 67
2.6.2 Exercises Sect. 2.2......Page 71
2.6.4 Exercises Sect. 2.4......Page 72
2.6.5 Exercises Sect. 2.5......Page 73
2.7 Review Questions......Page 74
3.1 3 by 3 Example......Page 75
3.2 Gauss and LU......Page 77
3.3.1 Algorithms for Triangular Systems......Page 80
3.3.2 Counting Operations......Page 82
3.4.2 Permutation Matrices......Page 84
3.4.3 Pivot Strategies......Page 87
3.5 The LU and LDU Factorizations......Page 88
3.5.1 Existence and Uniqueness......Page 89
3.6 Block LU Factorization......Page 92
3.7.1 Exercises Sect. 3.3......Page 93
3.7.2 Exercises Sect. 3.4......Page 94
3.7.3 Exercises Sect. 3.5......Page 96
3.8 Review Questions......Page 99
4.1 The LDL Factorization......Page 100
4.2 Positive Definite and Semidefinite Matrices......Page 102
4.2.1 The Cholesky Factorization......Page 104
4.2.2 Positive Definite and Positive Semidefinite Criteria......Page 106
4.3 Semi-Cholesky Factorization of a Banded Matrix......Page 108
4.4 The Non-symmetric Real Case......Page 112
4.5.1 Exercises Sect. 4.2......Page 113
4.6 Review Questions......Page 114
5.1 Inner Products, Orthogonality and Unitary Matrices......Page 116
5.1.1 Real and Complex Inner Products......Page 117
5.1.2 Orthogonality......Page 119
5.1.3 Sum of Subspaces and Orthogonal Projections......Page 121
5.1.4 Unitary and Orthogonal Matrices......Page 123
5.2 The Householder Transformation......Page 124
5.3.1 The Algorithm......Page 128
5.3.3 Solving Linear Systems Using Unitary Transformations......Page 130
5.4.1 Existence......Page 131
5.5 QR and Gram-Schmidt......Page 133
5.6 Givens Rotations......Page 134
5.7.2 Exercises Sect. 5.2......Page 136
5.7.3 Exercises Sect. 5.4......Page 137
5.7.5 Exercises Sect. 5.6......Page 140
5.8 Review Questions......Page 142
Part II Eigenpairs and Singular Values......Page 144
6.1 Defective and Nondefective Matrices......Page 145
6.1.1 Similarity Transformations......Page 147
6.1.2 Algebraic and Geometric Multiplicity of Eigenvalues......Page 148
6.2 The Jordan Factorization......Page 149
6.3.2 Unitary and Orthogonal Matrices......Page 151
6.3.3 Normal Matrices......Page 153
6.3.5 The Quasi-Triangular Form......Page 155
6.3.6 Hermitian Matrices......Page 156
6.4 Minmax Theorems......Page 157
6.5 Left Eigenvectors......Page 159
6.5.1 Biorthogonality......Page 160
6.6.1 Exercises Sect. 6.1......Page 161
6.6.2 Exercises Sect. 6.2......Page 163
6.6.3 Exercises Sect. 6.3......Page 165
6.7 Review Questions......Page 166
7 The Singular Value Decomposition......Page 168
7.1.1 The Matrices AA, AA*......Page 169
7.2.1 The Singular Value Factorization......Page 171
7.3 A Geometric Interpretation......Page 174
7.4.1 The Frobenius Norm......Page 176
7.4.2 Low Rank Approximation......Page 177
7.5.1 Exercises Sect. 7.1......Page 178
7.5.2 Exercises Sect. 7.2......Page 179
7.5.3 Exercises Sect. 7.4......Page 182
7.6 Review Questions......Page 183
Part III Matrix Norms and Least Squares......Page 184
8.1 Vector Norms......Page 185
8.2.1 Consistent and Subordinate Matrix Norms......Page 188
8.2.2 Operator Norms......Page 189
8.2.3 The Operator p-Norms......Page 191
8.2.4 Unitary Invariant Matrix Norms......Page 193
8.3 The Condition Number with Respect to Inversion......Page 194
8.3.1 Perturbation of the Right Hand Side in a Linear Systems......Page 195
8.3.2 Perturbation of a Square Matrix......Page 197
8.4 Proof That the p-Norms Are Norms......Page 199
8.4.1 p-Norms and Inner Product Norms......Page 202
8.5.1 Exercises Sect. 8.1......Page 204
8.5.2 Exercises Sect. 8.2......Page 205
8.5.3 Exercises Sect. 8.3......Page 208
8.5.4 Exercises Sect. 8.4......Page 211
8.6 Review Questions......Page 212
9 Least Squares......Page 213
9.1 Examples......Page 214
9.1.1 Curve Fitting......Page 216
9.2 Geometric Least Squares Theory......Page 218
9.3.1 Normal Equations......Page 219
9.3.2 QR Factorization......Page 220
9.3.3 Singular Value Decomposition, Generalized Inverses and Least Squares......Page 221
9.4 Perturbation Theory for Least Squares......Page 224
9.4.1 Perturbing the Right Hand Side......Page 225
9.4.2 Perturbing the Matrix......Page 226
9.5.1 The Minmax Theorem for Singular Values and the Hoffman-Wielandt Theorem......Page 227
9.6.1 Exercises Sect. 9.1......Page 230
9.6.2 Exercises Sect. 9.2......Page 231
9.6.3 Exercises Sect. 9.3......Page 232
9.6.5 Exercises Sect. 9.5......Page 235
9.7 Review Questions......Page 236
Part IV Kronecker Products and Fourier Transforms......Page 237
10.1 The 2D Poisson Problem......Page 238
10.1.1 The Test Matrices......Page 241
10.2 The Kronecker Product......Page 242
10.3 Properties of the 2D Test Matrices......Page 245
10.4.2 Exercises Sect. 10.3......Page 247
10.5 Review Questions......Page 249
11.1 Algorithms for a Banded Positive Definite System......Page 250
11.1.2 Block LU Factorization of a Block Tridiagonal Matrix......Page 251
11.2 A Fast Poisson Solver Based on Diagonalization......Page 252
11.3.2 The Discrete Fourier Transform (DFT)......Page 255
11.3.3 The Fast Fourier Transform (FFT)......Page 257
11.4.1 Exercises Sect. 11.3......Page 260
11.5 Review Questions......Page 263
Part V Iterative Methods for Large Linear Systems......Page 264
12.1 Classical Iterative Methods; Component Form......Page 265
12.1.1 The Discrete Poisson System......Page 267
12.2 Classical Iterative Methods; Matrix Form......Page 269
12.2.2 The Splitting Matrices for the Classical Methods......Page 270
12.3 Convergence......Page 272
12.3.1 Richardson's Method......Page 273
12.3.2 Convergence of SOR......Page 275
12.3.3 Convergence of the Classical Methods for the Discrete Poisson Matrix......Page 276
12.3.4 Number of Iterations......Page 278
12.3.5 Stopping the Iteration......Page 279
12.4.1 The Spectral Radius......Page 280
12.4.2 Neumann Series......Page 282
12.5 The Optimal SOR Parameter Ο......Page 283
12.6.1 Exercises Sect. 12.3......Page 286
12.6.2 Exercises Sect. 12.4......Page 288
12.7 Review Questions......Page 289
13 The Conjugate Gradient Method......Page 290
13.1 Quadratic Minimization and Steepest Descent......Page 291
13.2.1 Derivation of the Method......Page 294
13.2.2 The Conjugate Gradient Algorithm......Page 296
13.2.4 Implementation Issues......Page 297
13.3.1 The Main Theorem......Page 299
13.3.3 Krylov Spaces and the Best Approximation Property......Page 300
13.4.1 Chebyshev Polynomials......Page 304
13.4.2 Convergence Proof for Steepest Descent......Page 307
13.4.3 Monotonicity of the Error......Page 309
13.5 Preconditioning......Page 310
13.6.1 A Variable Coefficient Problem......Page 313
13.6.2 Applying Preconditioning......Page 316
13.7.1 Exercises Sect. 13.1......Page 317
13.7.2 Exercises Sect. 13.2......Page 318
13.7.3 Exercises Sect. 13.3......Page 320
13.7.4 Exercises Sect. 13.4......Page 323
13.8 Review Questions......Page 324
Part VI Eigenvalues and Eigenvectors......Page 325
14.1 Eigenpairs......Page 326
14.2 Gershgorin's Theorem......Page 327
14.3 Perturbation of Eigenvalues......Page 329
14.3.1 Nondefective Matrices......Page 331
14.4 Unitary Similarity Transformation of a Matrix into Upper Hessenberg Form......Page 333
14.5 Computing a Selected Eigenvalue of a Symmetric Matrix......Page 335
14.5.1 The Inertia Theorem......Page 337
14.5.2 Approximating Ξ»m......Page 338
14.6.1 Exercises Sect. 14.1......Page 339
14.6.3 Exercises Sect. 14.3......Page 340
14.6.5 Exercises Sect. 14.5......Page 341
14.7 Review Questions......Page 343
15.1.1 The Power Method......Page 344
15.1.2 The Inverse Power Method......Page 348
15.1.3 Rayleigh Quotient Iteration......Page 349
15.2 The Basic QR Algorithm......Page 351
15.2.1 Relation to the Power Method......Page 352
15.2.2 Invariance of the Hessenberg Form......Page 353
15.3 The Shifted QR Algorithms......Page 354
15.4.1 Exercises Sect. 15.1......Page 355
15.5 Review Questions......Page 356
Part VII Appendix......Page 357
16 Differentiation of Vector Functions......Page 358
References......Page 361
Index......Page 362