Table of contents for The Lanczos and conjugate gradient algorithms : from theory to finite precision computations / GeĢrard Meurant.


Bibliographic record and links to related information available from the Library of Congress catalog
Note: Electronic data is machine generated. May be incomplete or contain other coding.


Counter
1  The ancros algorith  in exact arthmetic                              1
1.1    Introduction to the Lanczos algorithm ..  . .. .     .     .    2
1.2    Lanczos polynomiials  .    .. . .. .                            9
1.3    Interlacing properties and approximations of eigenvalues  . .   16
1.4    The components of the eigenvectors of T  .        .  .     . . 20
1.5    Study of the pivot functions .  . .. .  .  .    .    .     .   22
1.6    Bounds for the approximation of eigenvalues . ..  .. . ..      25
17     A priori bounds . . . .  .  .......     . .                   41
1.8    Computation of the approximate eigenvalues .  .. .   . .  .    43
1.9    Harmonic Ritz values .     . .  . ..    ......       .    .    43
2    The     algorit    in eact arithmetic                                  45
211    Derivation of the CG algorithm from the Lanczos algorthn  . .   .46
2.2     Relations between residuals and descent d rections .  .  . .  53
2 3    The norm of the residual .. . .   . . .  ...                 . 55
2 4    The A -norm of the error . . . .  .   . .           . .    . .  58
2.5     he   norm of the error  .  . . . .. .68
2.6    Other forms of the CG algorithm  . .  ..  ..  .        .       74
2.7     Bounds for the norms of the error  . .  .  ..  . . . .  . .   77
3    A hisorical perspective on theLnczos algoith  in i    pecision         81
3.1    The tools of the trade  ...- ....                              83
3.2    Numerical example . ..     .  ...         ......          .     89
3      The work of Chris Paige .        .           . .  . .  .93
3.4    Illustration of the work of Chris Paige  . ....     .   .      102
35     The work of Joe Grear           .       . ..     .             105
3.6    Illustration of the work of Joe Grar . .  . .   .  .   .       109
3.7  The work of Horst Simon .       .   ..      ..      .     .    110
3.8    Illustration of the work of Horst Simon .  . . ..  .           118
3)9    The work ofAnne Greenbaum and Zdenek Strako   .. . .      .. . . 121
3.10   The work of J.Cullum and R. Willoughby .. ....    .            130
3.     The work of V. Druskin and L. Knizhnerman      .   . . . .     130
3.12   Recent related results . .. . .                                36
4    The Lancs algrith      finite precision                              139
4.     Numerical examples ..............                          .  139
4.2    Solution of three-term recurrences . .... .                  . 149
4.3    The anczos vectors in finite precision  ..  .... .     .   .  152
4.4    Another solution to three-term recurrences                   166
4. 5   Bounds for the perturbation terms                             174
4 6    Some more examples       . .  . ...                           176
4 7    Conclusions of this chapter                                   184
5     The CG algorthm in finite precision                                 187
5.1    Numerical examples          . . .87
5.2    Relations between CG and Lanczos in finite precision . . . ..  191
5.3    Study of the CG three-term recurrences  .  . .     . ...      198
5 4    Study of the CG two-term recurrences                          210
5.5    Relations between p5 and  . . .. . .   ...    . .   .         214
5.6    Local orthogonality in finite pecision   . .  .   .          215
5.7    CG convergence in finite precision               ..... . . . 223
5 8    Numerical examples of convergence in variable precision  . . . 230
6  he 2maxi m attainable accuracy                                    239
6 i    Difference of residuals  . , .. .            .        .    . . 239
62     Numerical experiments for Ax = 0 ...     .    .....      .     241
6.3    Estimate of the maximum attainable accuracy                . . 249
6.4    Some ways to improve the maximum attainable accuracy  . . .  . 252
7    Estimates of norms of the error in finite precision                  257
7.     Compulaion of estimates of the norms of the error in exact arithmetic 257
72     The A-norm of the error in finite precision     .            263
713    The 12 norm of the error in finite precision  . .  . .  .  . 265
7.4    Numerical examples . . .  . .. . . . .                        268
"7 5   C omparison of two-term and thre-term CG          . .275
8    The preconditioned CG algorithm                                      281
S   PCG in exact arithmetic   . . . .                            281
8.2    Formulas for norms of the error    ..      .             .    282
8.3    PCG in nite precision ..   ....     ..     ...            .   284
8.4    Numerical examples of convergence     ... .        ....   .   287
S5     NumeTaril examples of estimation of norms       . .  .        292
9    Miscellaneos                                                         297
". 1   Choice of the starting vectr  . . .  .    ..     . .. .     . 297
9 2    Variants of CG and multiple right-hand sides  .. .  .      .298
9.21       Constrained CG  .   ..                   .         298
92.2       BlockCG                                            299
2 3        Init, Augmented, and Deflated CG .  .     .        300
9.2 4      G     CG.                                   . .    302
9.3    Residual smoothing .   . . . . .  . .  .                    302
9.4    Inner-outer iterations and relaxation strategies  .  .. ..  304
9.5    Numerical experiments with starting vectors                 305
9.6    Shifted matrices                                            308
9.7    CG on indefinite systems                                    310
9 8    Examples with PCG                                           313



Library of Congress subject headings for this publication: Conjugate gradient methods, Algorithms Methodology