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

2.4 Theorem. Suppose A is a symmetric positive definite matrix with spectral con-
dition number κ. Then applying the gradient method to the function (2.1) generates
a sequence with

κ − k

1
κ + 1

x k − x ∗ A ≤ x 0 − x ∗ A . ( 2 . 11 )

Convergence Behavior in the Case of Large Condition Numbers

If we solve a system of equations with a very large condition number κ , the
convergence rate

2
κ
is very close to 1. We can show that this unfavorable rate dominates the iteration
with a simple example involving two unknowns.

κ − 1

κ + 1 ≈

1 −

2.5 Example. Let a 1. We seek the minimum of

1 .

1

2 (x 2

ay 2 ), f(x,y) = + i.e., A = ( 2 . 12 )

a

Here κ(A) = a . Suppose we choose

(x 0 ,y 0 ) = (a, 1 )

as the starting vector. Then the direction of steepest descent is given by ( − 1 , − 1 ) .

We claim that

x k + 1 = ρx k , k + 1 =− ρy k ,k =

0 , 1 ,... , ( 2 . 13 )

where ρ = (a − 1 )/(a + 1 ) . This is easily checked for k =

0, and it follows for
all k by symmetry arguments. Thus, the convergence rate is exactly as described
in Theorem 2.4.
The contour lines of the function (2.12) are strongly elongated ellipses (see
Fig. 46), and the angle between the gradient and the direction leading to a minimum
can be very large (cf. Problem 2.8).

•

•

Fig. 46. Contour lines and the gradient for Example 2.5