The Conjugate Gradient Method - Finite Elements: Theory, Fast Solvers, and Applications in Elasticity Theory - page 189

1.3 Theorem. For every n × n matrix G,

k →∞ G k

1 /k

= ρ(G).

lim ( 1 . 6 )

Proof. Let ε> 0, ρ = ρ(G) , and

1

B =

ε G.

ρ +

Then ρ(B) = ρ/(ρ + ε) < 1, and lim k →∞ B k 0. Hence, sup k ≥ 0 B k = ≤ a< ∞ .

G k ≤ a(ρ + ε) k and lim k →∞ G k

1 /k

This implies ≤ ρ + ε . Thus, the left-hand

side of (1.6) is at most ρ(G) .
On the other hand, the left-hand side of (1.6) cannot be smaller than ρ(G)
since G has an eigenvalue of modulus ρ .
Here we have made use of the usual notation. In particular, M − 1 can be
thought of as an approximate inverse of A . In the framework of the CG method,
the matrix M is called a preconditioner , and is usually denoted by the symbol C .

The Jacobi and Gauss-Seidel Methods

One way to get an iterative method is to start with the decomposition

A = D − L − U.

Here D is diagonal, L lower-triangular, and U upper-triangular:

a ik

if i = k ,

D ik =

0 otherwise,

− a ik

− a ik

if i>k ,

if i<k ,

L ik = U ik =

0 otherwise, 0 otherwise.

The Jacobi method corresponds to the iteration

Dx k + 1 = (L + U)x k + b, ( 1 . 7 )

which can be written componentwise as

a ii x k + 1

a ij x j +

=− b i ,i = 1 , 2 ,...,n. ( 1 . 8 )

i

j = i

The associated iteration matrix is G = G J = D − 1 (L + U) , and thus

a ik
a ii

− for k = i ,

G ik =

0 otherwise.