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.
