Volume 13, pp. 56-80, 2002.
On error estimation in the conjugate gradient method and why it works in finite precision computations
Zdeněk Strakoš and Petr Tichý
Abstract
In their paper published in 1952, Hestenes and Stiefel
considered the conjugate gradient (CG) method an iterative method which terminates in at
most $n$ steps if no rounding errors are encountered [p.~410].
They also proved identities for the $A$-norm and the Euclidean norm
of the error which could justify the stopping criteria
[Theorems~6:1 and 6:3, p.~416].
The idea of estimating errors in iterative methods, and in the CG method in
particular, was independently (of these results) promoted by Golub;
the problem was linked to Gauss
quadrature and to its modifications [7], [8].
A comprehensive summary of this
approach was given in [15], [16].
During the last decade several papers developed error bounds algebraically
without using Gauss quadrature.
However, we have not found any reference to the corresponding results in [24].
All the existing bounds assume exact arithmetic.
Still they seem to be in a striking agreement with finite precision numerical experiments,
though in finite precision computations they estimate quantities which
can be orders of magnitude different from their exact precision counterparts!
For the lower bounds obtained from Gauss quadrature formulas
this nontrivial phenomenon was
explained, with some limitations, in [17].
In our paper we show that the lower bound for the $A$-norm of the
error based on Gauss quadrature ([15], [17], [16]) is mathematically equivalent to the original formula
of Hestenes and Stiefel [24].
We will compare existing bounds and we will demonstrate
necessity of a proper rounding error analysis:
we present an example of the well-known bound which can fail in
finite precision arithmetic.
We will analyse the simplest bound based on [24, Theorem~6:1],
and prove that it is numerically stable.
Though we concentrate mostly on the lower bound for the $A$-norm of
the error, we describe also an estimate for the Euclidean norm of
the error based on [24, Theorem~6:3].
Our results are illustrated by numerical experiments.
Full Text (PDF) [322 KB], BibTeX
Key words
conjugate gradient method, Gauss quadrature, evaluation of convergence, error bounds, finite precision arithmetic, rounding errors, loss of orthogonality.
AMS subject classifications
15A06, 65F10, 65F25, 65G50.
ETNA articles which cite this article
| Vol. 22 (2006), pp. 41-70 M. Arioli and G. Manzini: A network programming approach in solving Darcy's equations by mixed finite-element methods |
| Vol. 31 (2008), pp. 178-203 Gene H. Golub, Martin Stoll, and Andy Wathen: Approximation of the scattering amplitude and linear systems |
| Vol. 35 (2009), pp. 118-128 Andreas Frommer: Monotone convergence of the Lanczos approximations to matrix functions of Hermitian matrices |
| Vol. 54 (2021), pp. 256-275 Ronny Ramlau and Bernadett Stadler: An augmented wavelet reconstructor for atmospheric tomography |
< Back