A Taxonomy for Conjugate Gradient Methods 论文

摘要

The conjugate gradient method of Hestenes and Stiefel is an effective method for solving large, sparse Hermitian positive definite (hpd) systems of linear equations, $Ax = b$. Generalizations to non-hpd matrices have long been sought. The recent theory of Faber and Manteuffel gives necessary and sufficient conditions for the existence of a CG method. This paper uses these conditions to develop and organize such methods. It is shown that any CG method for $Ax = b$ is characterized by an hpd inner product matrix B and a left preconditioning matrix C. At each step the method minimizes the B-norm of the error over a Krylov subspace. This characterization is then used to classify known and new methods. Finally, it is shown how eigenvalue estimates may be obtained from the iteration parameters, generalizing the well-known connection between CG and Lanczos. Such estimates allow implementation of a stopping criterion based more nearly on the true error.