Krylov subspace methods in finite precision [Elektronische Ressource] : a unified approach / von Jens-Peter Max Zemke

Sujets

• Mathematics

Informations

• Publié par: technische_universitat_hamburg-harburg
• Publié le: 01 janvier 2003
• Nombre de lectures: 28
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Krylov Subspace Methods in Finite Precision:
A Unifled Approach
Vom Promotionsausschu… der
Technischen Universit˜at Hamburg-Harburg
zur Erlangung des akademischen Grades
Doktor der Naturwissenschaften
genehmigte Dissertation
von
Jens{Peter Max Zemke
aus Luneburg˜
20031. Gutachter: Prof. Dr. S. M. Rump
2.hter: Prof. Dr. H. Vo…
Tag der mundlic˜ hen Prufung:˜ 14.05.2003Contents
List of Figures iv
List of Algorithms vi
List of Symbols ix
1 Preliminaries 1
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Motivation and History . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Finite Precision and Error Analysis . . . . . . . . . . . . . . . . . . . 6
1.4.1 Floating Point Models . . . . . . . . . . . . . . . . . . . . . . 7
1.4.2 Error Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4.3 Perturbation Theory . . . . . . . . . . . . . . . . . . . . . . . 10
1.5 Solution of Linear Systems. . . . . . . . . . . . . . . . . . . . . . . . 12
1.5.1 Perturbation Theory . . . . . . . . . . . . . . . . . . . . . . . 12
1.5.2 Decompositions and Error Analysis . . . . . . . . . . . . . . . 14
1.6 The Algebraic Eigenproblem . . . . . . . . . . . . . . . . . . . . . . 20
1.6.1 Related Decompositions and Their Uniqueness . . . . . . . . 21
1.6.2 Necessary Deflnitions . . . . . . . . . . . . . . . . . . . . . . 31
1.6.3 Perturbation Theory . . . . . . . . . . . . . . . . . . . . . . . 36
1.6.4 Subspaces and Projectors . . . . . . . . . . . . . . . . . . . . 49
1.7 Miscellaneous . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
1.7.1 Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
1.7.2 Finite Difierence Equations . . . . . . . . . . . . . . . . . . . 52
1.7.3 Short-Term Recurrences: An Example . . . . . . . . . . . . . 52
2 Krylov Methods and Matrix Structure 57
2.1 An Algebraic Identity . . . . . . . . . . . . . . . . . . . . . . . . . . 57
2.2 Eigenvalue { Eigenvector Relations . . . . . . . . . . . . . . . . . . . 61
2.3 Hessenberg Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
2.3.1 The Eigendecomposition . . . . . . . . . . . . . . . . . . . . . 65
2.3.2 Submatrices and Eigenvectors . . . . . . . . . . . . . . . . . . 67
2.3.3 Eigenvalue { Eigenvector Relations . . . . . . . . . . . . . . . 68
2.3.4 Mathematical Folklore . . . . . . . . . . . . . . . . . . . . . . 71
2.4 Tridiagonal Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
2.4.1 Folklore . . . . . . . . . . . . . . . . . . . . . . 74
2.5 Rectangular Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
2.5.1 Singular Value { Singular Vector Relations . . . . . . . . . . 74
iii CONTENTS
3 Krylov Methods in Inflnite Precision 77
3.1 Krylov Subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
3.2v Subspace Bases . . . . . . . . . . . . . . . . . . . . . . . . . . 79
3.3 Krylov Decompositions . . . . . . . . . . . . . . . . . . . . 83
3.4v Subspace Methods . . . . . . . . . . . . . . . . . . . . . . . . 88
3.5 Krylov Methods for the Eigenproblem . . . . . . . . . . . . . . . . . 89
3.5.1 The Power Method . . . . . . . . . . . . . . . . . . . . . . . . 90
3.5.2 Subspace Iteration . . . . . . . . . . . . . . . . . . . . . . . . 93
3.5.3 The Arnoldi Method . . . . . . . . . . . . . . . . . . . . . . . 94
3.5.4 The Symmetric Lanczos Method . . . . . . . . . . . . . . . . 97
3.5.5 The Non-Symmetric Lanczos Method . . . . . . . . . . . . . 99
3.6 Krylov Methods for Solving Linear Systems . . . . . . . . . . . . . . 102
3.6.1 Richardson Iteration and Polynomial Acceleration . . . . . . 105
3.6.2 Orthores/Orthomin/Orthodir . . . . . . . . . . . . . . . . . . 106
3.6.3 FOM/GMRES . . . . . . . . . . . . . . . . . . . . . . . . . . 111
3.6.4 Truncated and Restarted Methods . . . . . . . . . . . . . . . 115
3.6.5 CG/CR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
3.6.6 SymmLQ/MinRes . . . . . . . . . . . . . . . . . . . . . . . . 118
3.6.7 Biores/Biomin/Biodir . . . . . . . . . . . . . . . . . . . . . . 121
3.6.8 QOR/QMR . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
3.6.9 Look-Ahead . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
3.6.10 Lanczos-Type Product Methods . . . . . . . . . . . . . . . . 125
3.6.11 CGNR/CGNE . . . . . . . . . . . . . . . . . . . . . . . . . . 128
3.7 Krylov Methods and Preconditioning . . . . . . . . . . . . . . . . . . 130
4 A Unifled Approach 133
4.1 Classiflcation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
4.2 Finite Precision Krylov Methods . . . . . . . . . . . . . . . . . . . . 135
4.3 Outline of Error Analysis . . . . . . . . . . . . . . . . . . . . . . . . 139
4.4 Where are we? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
4.5 Perturbed Krylov Decompositions . . . . . . . . . . . . . . . . . . . 142
4.6 Deviation from Nowhere? . . . . . . . . . . . . . . . . . . . . . . . . 148
4.7 The Sylvester Equation . . . . . . . . . . . . . . . . . . . . . . . . . 164
4.8 The Computed Basis Vectors . . . . . . . . . . . . . . . . . . . . . . 171
4.9 Impacts of the lth Error . . . . . . . . . . . . . . . . . . . . . . . . . 178
4.10 Measures of Convergence and Deviation . . . . . . . . . . . . . . . . 187
4.11 Re-Orthogonalisation Techniques . . . . . . . . . . . . . . . . . . . . 196
5 Krylov Methods in Finite Precision 199
5.1 Krylov Methods for the Eigenproblem . . . . . . . . . . . . . . . . . 199
5.1.1 The Power Method . . . . . . . . . . . . . . . . . . . . . . . . 200
5.1.2 Subspace Iteration . . . . . . . . . . . . . . . . . . . . . . . . 201
5.1.3 The Arnoldi Method . . . . . . . . . . . . . . . . . . . . . . . 202
5.1.4 The Symmetric Lanczos Method . . . . . . . . . . . . . . . . 210
5.1.5 The Non-Symmetric Lanczos Method . . . . . . . . . . . . . 217
5.2 Krylov Methods for Solving Linear Systems . . . . . . . . . . . . . . 219
5.2.1 Richardson Iteration and Polynomial Acceleration . . . . . . 219
5.2.2 Orthores/Orthomin/Orthodir . . . . . . . . . . . . . . . . . . 220
5.2.3 FOM/GMRES . . . . . . . . . . . . . . . . . . . . . . . . . . 221
5.2.4 Truncated and Restarted Methods . . . . . . . . . . . . . . . 222
5.2.5 CG/CR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
5.2.6 SymmLQ/MinRes . . . . . . . . . . . . . . . . . . . . . . . . 223
5.2.7 Biores/Biomin/Biodir . . . . . . . . . . . . . . . . . . . . . . 224
5.2.8 QOR/QMR . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224CONTENTS iii
5.2.9 Look-Ahead . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
5.2.10 Lanczos-Type Product Methods . . . . . . . . . . . . . . . . 225
5.2.11 CGNE/CGNR . . . . . . . . . . . . . . . . . . . . . . . . . . 225
5.3 Krylov Methods and Preconditioning . . . . . . . . . . . . . . . . . . 225
6 Krylov Methods: Miscellanea 227
6.1 Krylov Methods and Stability . . . . . . . . . . . . . . . . . . . . . . 227
6.1.1 Can Krylov Methods be Backward Stable? . . . . . . . . . . 228
6.1.2 All Krylovds are Forward Unstable . . . . . . . . . . . 229
6.1.3 Most Krylov Methods are not Backward Stable . . . . . . . . 229
6.1.4 Which Krylovds are Stable . . . . . . . . . . . . . . . 229
6.1.5 Wherev Methods are . . . . . . . . . . . . . . . 229
6.1.6 Alternate Notions of Stability . . . . . . . . . . . . . . . . . . 230
6.2 Krylov Methods and Other Arithmetics . . . . . . . . . . . . . . . . 231
6.2.1 Exact/Symbolic Arithmetic . . . . . . . . . . . . . . . . . . . 231
6.2.2 Multiple Precision . . . . . . . . . . . . . . . . . . 231
6.2.3 Variable Arithmetic . . . . . . . . . . . . . . . . . . 232
6.2.4 Stochastic Arithmetic . . . . . . . . . . . . . . . . . . . . . . 232
6.2.5 Interval . . . . . . . . . . . . . . . . . . . . . . . . 233
7 Conclusion and Outview 243
Bibliography 246iv CONTENTSList of Figures
1.1 A typical member of the classT . . . . . . . . . . . . . . . . . . . . 24
1.2 The Bessel labyrinth . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.1 How vectors are selected from the eigensystem . . . . . . . . . . . . 61
4.1 The governing equation in flnite precision . . . . . . . . . . . . . . . 137
4.2 The two-dimensional generalised eigenvector grid . . . . . . . . . . . 168
4.3 Symmetric Lanczos, loss versus convergence (I) . . . . . . . . . . . . 189
4.4 exact versus oating point . . . . . . . . . . . . 190
5.1 Trade-ofi between fast, robust and general applicable . . . . . . . . . 200
5.2 Arnoldi, normal matrix, equidistant eigenvalues . . . . . . . . . . . . 207
5.3 non-normal matrix, equidistant eigenvalues . . . . . . . . . 208
5.4 Symmetric Lanczos, non-negative matrix, ‚ . . . . . . . . . . . . 213max
5.5 loss versus convergence (II). . . . . . . . . . . . 214
5.6 Symmetric Lanczos,e matrix, ‚ . . . . . . . . . . . 216max¡1
5.7 Non-symmetric Lanczos, Jordan-block of size 10 . . . . . . . . . . . 218
26.1 The wrapping efiect in R . . . . . . . . . . . . . . . . . . . . . . . . 235
vvi LIST OF FIGURES