Page 181 - Matrices theory and applications

9. Iterative Methods for Linear Problems
164
• For k ≥ 0 with unit increment, do
– Compute r k = r(x k )= Ax k − b.If r k =0, then ¯x = x k .
– Otherwise, minimize J(x k + αr k + βp k−1 ), by computing α k ,β k
as above.
– Define
p k+1 = r k +(β k /α k )p k−1 , x k+1 = x k + α k p k .
A priori, this computation furnishes the exact solution ¯ in l iterations.
x
2
However, l equals n in general, and the cost of each iteration is O(n ).
The conjugate gradient, viewed as a direct method, is thus rather slow.
One often uses this method for sparse matrices, whose maximal number
of nonzero elements m per rows is small compared to n.The complexity
of an iteration is then O(mn). However, that is still rather costly as a
2
direct method (O(mn ) operations in all), since the complexity of iterative
methods is also reduced for sparse matrices.
This explains why one prefers to consider the conjugate gradient as an
iterative method, in which one makes only a few iterations N n. Strictly
speaking, Theorem 9.5.1 does not define a convergence rate τ,since one
does not have, in general, an inequality of the form
x k+1 − ¯x ≤ e −τ x k − ¯x .
In particular, one is not certain that x 1 − ¯x is smaller than x 0 − ¯x .
However, the inequality (9.6) is analogous to what we have for a classi-
cal iterative method, up to the factor 4. We shall therefore say that the
conjugate gradient admits a convergence rate τ CG that satisfies

K(A) − 1
. (9.8)
τ CG ≤ θ = − log
K(A)+1
This rate is equivalent to 2K(A) −1/2 when K(A) is large. This method
canbe consideredasaniterative method when nτ CG 1 since then it is
2
possible to choose N n. Obviously, a sufficient condition is K(A) n .
Application: Let us consider the resolution of the Laplace equation in an
d
open bounded set Ω of IR , with a Dirichlet boundary condition, by the
finite elements method:
∆u = f in Ω, u =0 on ∂Ω.
The matrix A is symmetric, reflecting the symmetry of the variational
formulation

1
(∇u ·∇v + fv) dx =0, ∀v ∈ H (Ω).
0
Ω
If the diameter of the grid is h with 0 <h 1, and if that grid is regular
enough, the number of degrees of freedom (the size of the matrix) n is of
d
order C/h ,where C is a constant. The matrix is sparse with m = O(1).