1 Introduction ................................................. 1
1.1 Solving Real-world Problems ............................. 2
1.2 A Short Recollection of Ideas ........................... 7
1.3 Specification of the Subject and Basic Notation ........ 10
2 Krylov Subspace Methods ..................................... 12
2.1 Projection Processes ................................... 12
2.2 How Krylov Subspaces Come into Play .................... 19
2.3 Mathematical Characterisation of Some Krylov Subspace
Methods ................................................ 22
2.4 The Arnoldi and Lanczos Algorithms ..................... 26
2.4.1 Arnoldi and Hermitian Lanczos ................... 26
2.4.2 Non-Hermitian Lanczos ........................... 31
2.4.3 Historical Note: The Gram-Schmidt Method ........ 33
2.5 Derivation of Some Krylov Subspace Methods ............. 36
2.5.1 Derivation of CG Using the Hermitian Lanczos
Algorithm ....................................... 36
2.5.2 CG and the Galerkin Finite Element Method ....... 42
2.5.3 CG and the Minimisation of a Quadratic
Functional ...................................... 47
2.5.4 Hermitian Indefinite Matrices and the SYMMLQ.
Method .......................................... 54
2.5.5 Minimising the Residual Norm: MINRES and GMRES .. 57
2.5.6 Further Krylov Subspace Methods ................. 61
2.5.7 Historical Note: A N. Krylov and the Early
History of Krylov Subspace Methods .............. 64
2.6 Summary and Outlook: Linear Projections and Nonlinear
Behaviour .............................................. 69
3 Matching Moments and Model Reduction View ................... 71
3.1 Stieltjes' Moment Problem .............................. 73
3.2 Model Reduction via Orthogonal Polynomials ............. 76
3.2.1 Derivation of the Gauss-Christoffel Quadrature .. 77
3.2.2 Moment Matching and Convergence Properties of
the Gauss-Christoffel Quadrature ................ 84
3.2.3 Historical Note: Gauss' Fundamental Idea, an
Early Application, and Later Developments ....... 87
3.3 Orthogonal Polynomials and Continued Fractions ......... 89
3.3.1 Three-term Recurrence and the Interlacing
Property ........................................ 89
3.3.2 Continued Fractions ............................. 96
3.3.3 The Gauss-Christoffel Quadrature for Analytic
Functions ...................................... 101
3.3.4 Summary of the Previous Mathematical
Development .................................... 103
3.3.5 Historical Note: Chebyshev, Markov,
Stieltjes, and the Moment Problem .............. 104
3.3.6 Historical Note: Orthogonal Polynomials and
Three-term Recurrences ......................... 107
3.4 Jacobi Matrices ....................................... 108
3.4.1 Algebraic Properties of Jacobi Matrices ........ 109
3.4.2 The Persistence Theorem, Stabilisation of
Nodes and Weights in the Gauss-Christoffel
Quadrature ..................................... 121
3.4.3 Historical Note: The Origin and Early
Applications of Jacobi Matrices ................ 130
3.5 Model Reduction via Matrices: Hermitian Lanczos and
CG .................................................... 136
3.6 Factorisation of the Matrix of Moments ................ 142
3.7 Vorobyev's Moment Problem ............................. 145
3.7.1 Application to the Hermitian Lanczos
Algorithm and the CG Method .................... 146
3.7.2 Application to the Non-Hermitian Lanczos
Algorithm ...................................... 148
3.7.3 Application to the Arnoldi Algorithm ........... 151
3.7.4 Matching Moments and Generalisations of the
Gauss-Christoffel Quadrature ................... 153
3.8 Matching Moments and Projection Processes ............. 156
3.9 Model Reduction of Large-scale Dynamical Systems ...... 160
3.9.1 Approximation of the Transfer Function ......... 161
3.9.2 Estimates in Quadratic Forms ................... 165
4 Short Recurrences for Generating Orthogonal Krylov
Subspace Bases ............................................. 168
4.1 The Existence of Conjugate Gradient Like Descent
Methods ............................................... 169
4.2 Cyclic Subspaces and the Jordan Canonical Form ........ 172
4.2.1 Invariant Subspaces and the Cyclic
Decomposition .................................. 173
4.2.2 The Jordan Canonical Form and the Length of
the Krylov Sequences ........................... 185
4.2.3 Historical Note: Classical Results of Linear
Algebra ........................................ 188
4.3 Optimal Short Recurrences ............................. 189
4.4 Sufficient Conditions ................................. 193
4.5 Necessary Conditions .................................. 196
4.6 Matrix Formulation and Equivalent Characterisations ... 204
4.7 Short Recurrences and the Number of Distinct
Eigenvalues ........................................... 209
4.8 Other Types of Recurrences ............................ 211
4.8.1 The Isometric Arnoldi Algorithm ................ 211
4.8.2 (s + 2,t)-term Recurrences ..................... 215
4.8.3 Generalised Krylov Subspaces ................... 219
4.9 Remarks on Functional Analytic Representations ........ 222
5 Cost of Computations Using Krylov Subspace Methods ......... 227
5.1 Seeing the Context is Essential ....................... 228
5.2 Direct and Iterative Algebraic Computations ........... 238
5.2.1 Historical Note: Are the Lanczos Method and
the CG Method Direct or Iterative Methods? ..... 241
5.3 Computational Cost of Individual Iterations ........... 245
5.4 Particular Computations and Complexity ................ 248
5.5 Closer Look at the Concept of Convergence ............. 250
5.5.1 Linear Stationary Iterative Methods ............ 250
5.5.2 Richardson Iteration and Chebyshev
Semi-iteration ................................. 252
5.5.3 Historical Note: Semi-iterative and Krylov
Subspace Methods ............................... 254
5.5.4 Krylov Subspace Methods: Nonlinear Methods
for Linear Problems ............................ 257
5.6 CG in Exact Arithmetic ................................ 258
5.6.1 Expressions for the CG Errors and Their Norms .. 260
5.6.2 Eigenvalue-based Convergence Results for CG .... 265
5.6.3 Illustrations of the Convergence Behaviour of
CG ............................................. 271
5.6.4 Outlying Eigenvalues and Superlinear
Convergence .................................... 275
5.6.5 Clustered Eigenvalues and the Sensitivity of
the Gauss-Christoffel Quadrature ............... 280
5.7 GMRES in Exact Arithmetic ............................. 285
5.7.1 Ritz Values and Harmonic Ritz Values ........... 286
5.7.2 Convergence Descriptions Based on Spectral
Information .................................... 289
5.7.3 More General Approaches ........................ 294
5.7.4 Any Nonincreasing Convergence Curve is
Possible with Any Eigenvalues .................. 297
5.7.5 Convection-diffusion Example ................... 303
5.7.6 Asymptotic Estimates for the GMRES
Convergence .................................... 306
5.8 Rounding Errors and Backward Stability ................ 308
5.8.1 Rounding Errors in Direct Computations ......... 311
5.8.2 Historical Note: Wilkinson and the Backward
Error Concept .................................. 315
5.8.3 The Backward Error Concept in Iterative
Computations ................................... 316
5.9 Rounding Errors in the CG Method ...................... 320
5.9.1 Delay of Convergence ........................... 320
5.9.2 Delay of Convergence can Invalidate Composite
Convergence Bounds ............................. 326
5.9.3 Maximal Attainable Accuracy .................... 328
5.9.4 Back to the Poisson Model Problem .............. 331
5.10 Rounding Errors in the GMRES Method ................... 338
5.10.1 The Choice of the Basis Affects Numerical
Stability ...................................... 338
5.10.2 Does the Orthogonalisation Algorithm Matter? ... 340
5.10.3 MGS GMRES is Backward Stable ................... 343
5.11 Omitted Issues and an Outlook ......................... 345
References ............................................ 349
Index of Historical Personalities ............................. 385
Index of Technical Terms ...................................... 388
|
