Table of Contents
SIAM


ERROR NORM ESTIMATION
IN THE CONJUGATE GRADIENT ALGORITHM

Gérard MEURANT and Petr TICHY

SIAM
2024
ISBN 978-1-611977-8-51
x + 127 pages



The conjugate gradient (CG) algorithm is almost always the iterative method of choice for solving linear systems with symmetric positive definite matrices.

This book

-describes and analyzes techniques based on Gauss quadrature rules to cheaply computes bounds on norms of the error that can be used to derive reliable stopping criteria;

-shows how to compute estimates of the smallest and largest eigenvalues during CG iterations;

-illustrates algorithms using many numerical experiments; these algorithms also can be easily incorporated into existing CG codes.

  • Table of Contents (PDF) [download]

    Table of Contents

    0/ Preface [TOC]

    

    1/ The conjugate gradient algorithm  [TOC]
    

    1.1 The Lanczos algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1
1.2 The conjugate gradient algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 The A-norm of the error. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Inverse of Tk. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5 The l2 norm of the error . . . . . . . . . . . . . . . . . . . . . . . . . . . . .12
1.6 Riemann-Stieltjes integral and Gauss quadrature . . . . . . . . . . . . . . . . . 15
1.7 MINRES and the CG residual norms . . . . . . . . . . . . . . . . . . . . . . . . .17
1.8 Estimates in finite precision arithmetic . . . . . . . . . . . . . . . . . . . . .18
1.9 The preconditioned conjugate gradient algorithm . . . . . . . . . . . . . . . . . 22
1.10 Parallel variants of CG . . . . . . . . . . . . . . . . . . . . . . . . . . . . .23

    

    2/ Numerical examples I  [TOC]
    

    2.1 bcsstk01 and its inverse . . . . . . . . . . . . . . . . . . . . . . . . . . . .  25
2.2 Prescribing the convergence curve . . . . . . . . . . . . . . . . . . . . . . . . 26
2.3 Effects of rounding errors . . . . . . . . . . . . . . . . . . . . . . . . . . . .28

    

    3/ The CGQL algorithm  [TOC]
    

    3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .31
3.2 The Gauss-Radau rule in CG . . . . . . . . . . . . . . . . . . . . . . . . . . . .34

    

    4/ The CGQ algorithm  [TOC]
    

    4.1 The factorization of tridiagonal matrices . . . . . . . . . . . . . . . . . . . . 39
4.2 Another upper bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

    

    5/ Approximation of the extreme eigenvalues  [TOC]
    

    5.1 Estimates of norms of triangular matrices . . . . . . . . . . . . . . . . . . . . 45
5.2 Estimates of norms of bidiagonal matrices and their inverses . . . . . . . . . . .47
5.3 Estimates of matrix norms in CG . . . . . . . . . . . . . . . . . . . . . . . . . 50

    

    6/ Numerical examples II  [TOC]
    

    6.1 bcsstk01 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .55
6.2 1138 bus. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
6.3 Pb26 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .57
6.4 Approximation of the extreme eigenvalues . . . . . . . . . . . . . . . . . . . . .59

    

    7/ Problems with the Gauss-Radau upper bound  [TOC]
    

    7.1 A model problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
7.2 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .66
7.3 Finite precision arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
7.4 Conclusion on the Gauss-Radau problem . . . . . . . . . . . . . . . . . . . . . . 80

    

    8/ Adaptive choice of the delay   [TOC]
    

    8.1 The delay for the Gauss lower bound . . . . . . . . . . . . . . . . . . . . . . . 83
8.2The delay for the Gauss-Radau upper bound . . . . . . . . . . . . . . . . . . . . .86

    

    9/ Numerical examples III  [TOC]
    

    9.1 bcsstk01 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .89
9.2 1138 bus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .89
9.3 Pb26 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .90
9.4 bcsstk09 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .90
9.5 Adaptove choice of mu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

    

    10/  Bounds and estimates of other norms  [TOC]
    

    10.1 The relative A-norm of the error . . . . . . . . . . . . . . . . . . . . . . . . 95
10.2 The l2 norm of the error . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
10.3 Other error norm estimates . . . . . . . . . . . . . . . . . . . . . . . . . . .102
10.4 Estimates of error norms by extrapolation . . . . . . . . . . . . . . . . . . . 102
10.5 Using the estimates in least squares problems . . . . . . . . . . . . . . . . . 103

    

    10/ Numerical examples IV  [TOC]
    

    11.1 bcsstk01 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .107
11.2 1138 bus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .108
11.3 Pb26 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .109

    

    Appendix  [TOC]
    


    References  [TOC]
    
There are 108 references.