1. Introduction ................................................. 1
1.1. Discretization of a Differential Equation ............... 1
1.2. Least Squares Fitting ................................... 4
1.3. Vibrations of a Mechanical System ....................... 8
1.4. The Vibrating String ................................... 10
1.5. Image Compression by the SVD Factorization ............. 12
2. Definition and Properties of Matrices ....................... 15
2.1. Gram Schmidt Orthonormalization Process ................ 15
2.2. Matrices ............................................... 17
2.2.1. Trace and Determinant ........................... 19
2.2.2. Special Matrices ................................ 20
2.2.3. Rows and Columns ................................ 21
2.2.4. Row and Column Permutation ...................... 22
2.2.5. Block Matrices .................................. 22
2.3. Spectral Theory of Matrices ............................ 23
2.4. Matrix Triangularization ............................... 26
2.5. Matrix Diagonalization ................................. 28
2.6. Min-Max Principle ...................................... 31
2.7. Singular Values of a Matrix ............................ 33
2.8. Exercises .............................................. 38
3. Matrix Norms, Sequences, and Series ......................... 45
3.1. Matrix Norms and Subordinate Norms ..................... 45
3.2. Subordinate Norms for Rectangular Matrices ............. 52
3.3. Matrix Sequences and Series ............................ 54
3.4. Exercises .............................................. 57
4. Introduction to Algorithmics ................................ 61
4.1. Algorithms and pseudolanguage .......................... 61
4.2. Operation Count and Complexity ......................... 64
4.3. The Strassen Algorithm ................................. 65
4.4. Equivalence of Operations .............................. 67
4.5. Exercises .............................................. 69
5. Linear Systems .............................................. 71
5.1. Square Linear Systems .................................. 71
5.2. Over- and Underdetermined Linear Systems ............... 75
5.3. Numerical Solution ..................................... 76
5.3.1. Floating-Point System ........................... 77
5.3.2. Matrix Conditioning ............................. 79
5.3.3. Conditioning of a Finite Difference Matrix ...... 85
5.3.4. Approximation of the Condition Number ........... 88
5.3.5. Preconditioning ................................. 91
5.4. Exercises .............................................. 92
6. Direct Methods for Linear Systems ........................... 97
6.1. Gaussian Elimination Method ............................ 97
6.2. LU Decomposition Method ............................... 103
6.2.1. Practical Computation of the LU
Factorization .................................. 107
6.2.2. Numerical Algorithm ............................ 108
6.2.3. Operation Count ................................ 108
6.2.4. The Case of Band Matrices ...................... 110
6.3. Cholesky Method ....................................... 112
6.3.1. Practical Computation of the Cholesky
Factorization .................................. 113
6.3.2. Numerical Algorithm ............................ 114
6.3.3. Operation Count ................................ 115
6.4. QR Factorization Method ............................... 116
6.4.1. Operation Count ................................ 118
6.5. Exercises ............................................. 119
7. Least Squares Problems ..................................... 125
7.1. Motivation ............................................ 125
7.2. Main Results .......................................... 126
7.3. Numerical Algorithms .................................. 128
7.3.1. Conditioning of Least Squares Problems ......... 128
7.3.2. Normal Equation Method ......................... 131
7.3.3. QR Factorization Method ........................ 132
7.3.4. Householder Algorithm .......................... 136
7.4. Exercises ............................................. 140
8. Simple Iterative Methods ................................... 143
8.1. General Setting ....................................... 143
8.2. Jacobi, Gauss-Seidel, and Relaxation Methods .......... 147
8.2.1. Jacobi Method .................................. 147
8.2.2. Gauss-Seidel Method ............................ 148
8.2.3. Successive Overrelaxation Method (SOR) ......... 149
8.3. The Special Case of Tridiagonal Matrices .............. 150
8.4. Discrete Laplacian .................................... 154
8.5. Programming Iterative Methods ......................... 156
8.6. Block Methods ......................................... 157
8.7. Exercises ............................................. 159
9. Conjugate Gradient Method .................................. 163
9.1. The Gradient Method ................................... 163
9.2. Geometric Interpretation .............................. 165
9.3. Some Ideas for Further Generalizations ................ 168
9.4. Theoretical Definition of the Conjugate Gradient
Method ................................................ 171
9.5. Conjugate Gradient Algorithm .......................... 174
9.5.1. Numerical Algorithm ............................ 178
9.5.2. Number of Operations ........................... 179
9.5.3. Convergence Speed .............................. 180
9.5.4. Preconditioning ................................ 182
9.5.5. Chebyshev Polynomials .......................... 186
9.6. Exercises ............................................. 189
10.Methods for Computing Eigenvalues .......................... 191
10.1.Generalities .......................................... 191
10.2.Conditioning .......................................... 192
10.3.Power Method .......................................... 194
10.4.Jacobi Method ......................................... 198
10.5.Givens-Householder Method ............................. 203
10.6.QR Method ............................................. 209
10.7.Lanczos Method ........................................ 214
10.8.Exercises ............................................. 219
11.Solutions and Programs ..................................... 223
11.1.Exercises of Chapter 2 ................................ 223
11.2.Exercises of Chapter 3 ................................ 234
11.3.Exercises of Chapter 4 ................................ 237
11.4.Exercises of Chapter 5 ................................ 241
11.5.Exercises of Chapter 6 ................................ 250
11.6.Exercises of Chapter 7 ................................ 257
11.7.Exercises of Chapter 8 ................................ 258
11.8.Exercises of Chapter 9 ................................ 260
11.9.Exercises of Chapter 10 ............................... 262
References .................................................... 265
Index ......................................................... 267
Index of Programs ............................................. 272
|
