GMRES and the Minimal Polynomial
- We present bounds on the convergence rate of the Generalized Minimal
method for solving nonsingular systems of linear equations Ax = b
in exact arithmetic.
The results are valid in finite and infinite dimensional spaces.
The bounds are derived by constructing residual polynomials
that are related to the minimal polynomial of A and can be
interpreted as follows:
If the eigenvalues of A consist of a single cluster plus outliers
then the convergence factor is bounded by the cluster radius,
while the asymptotic error constant is proportional
to the deviation of A from normality as well as the indices
of the outliers and their distance from the cluster.
If the eigenvalues of A consist of several close clusters, then
GMRES treats the clusters as a single big cluster, and the
convergence factor is the radius of this big cluster. Our bounds also lead to
a simpler proof of existing r-superlinear convergence
results in Hilbert space. This research was partially supported by National Science Foundation grants
DMS-9122745 & D-9423705 (Campbell), CCR-9102853 (Ipsen), DMS-9321938 (Kelley), and
DMS-9020915 & DMS-9403224 (Meyer).
- Vol. 36, 1996, pp. 32-43
- S. L. Campbell
- I. C. F. Ipsen
- C. T. Kelley
C. D. Meyer
- THE POSTSCRIPT FILE
- The postscript file (uncompressed) for the entire paper is 848 KB.
- To receive it, click on
Return To Home Page
Return To Abstracts