Accurate predictions of the convergence of iterative methods are difficult to make, but useful bounds can often be obtained. For the Conjugate Gradient method, the error can be bounded in terms of the spectral condition number of the matrix . (Recall that if and are the largest and smallest eigenvalues of a symmetric positive definite matrix , then the spectral condition number of is . If is the exact solution of the linear system , with symmetric positive definite matrix , then for CG with symmetric positive definite preconditioner , it can be shown that

where (see Golub and Van Loan [][.2.8]GoVL:matcomp, and Kaniel [131]), and . From this relation we see that the number of iterations to reach a relative reduction of in the error is proportional to .

In some cases, practical application of the above error bound is straightforward. For example, elliptic second order partial differential equations typically give rise to coefficient matrices with (where is the discretization mesh width), independent of the order of the finite elements or differences used, and of the number of space dimensions of the problem (see for instance Axelsson and Barker [.5]AxBa:febook). Thus, without preconditioning, we expect a number of iterations proportional to for the Conjugate Gradient method.

Other results concerning the behavior of the Conjugate Gradient
algorithm have been obtained. If the extremal eigenvalues of the
matrix are well separated, then one often observes so-called
(see Concus, Golub and
O'Leary [58]); that is, convergence at a
rate that increases per iteration.
This phenomenon is explained by
the fact that CG tends to eliminate components of the error in the
direction of eigenvectors associated with extremal eigenvalues first.
After these have been eliminated, the method proceeds as if these
eigenvalues did not exist in the given system, *i.e.*, the
convergence rate depends on a reduced system with a (much) smaller
condition number (for an analysis of this, see Van der Sluis and
Van der Vorst [199]). The effectiveness of
the preconditioner in reducing the condition number and in separating
extremal eigenvalues can be deduced by studying the approximated
eigenvalues of the related Lanczos process.

Mon Nov 20 08:52:54 EST 1995