Projections and Conjugate Gradients

G.W. Stewart (Maryland)

Conjugate gradient methods and their relatives (such the minimum residual method) are widely used to solve large sparse linear systems and to regularize ill-posed problems. The usual approach to the analysis of these methods is to recognize that the successive approximate solutions are polynomials in the matrix of the system operating on the residual vector. Since the approximations satisfy an optimality condition, one can obtain upper bounds on the accuracy of the approximations by selecting polynomials that are nearly optimal. Unfortunately, the results are averaged over the spectrum of the matrix, so that it is difficult to see how the method converges along the individual eigenvectors.

In this talk we describe a new approach. Here the approximate solutions (in the coordinates of the eigensystem of the matrix) are expressed in terms of orthogonal projections involving certain modified Krylov subspaces. Convergence in a component is signaled by the approach of the corresponding row of the projection to a row of the identity matrix, and bounds can be given for the rate of convergence. This componentwise approach may be more suitable than the usual techniques for analyzing the behavior of the methods for ill-posed problems.