Page 234 -

5.2. Gradient and Conjugate Gradient Methods 217

5.2 Gradient and Conjugate Gradient Methods

In this section let A ∈ R m,m be symmetric and positive definite. Then the
system of equations Ax = b is equivalent to the problem
1 T T m
Minimize f(x):= x Ax − b x for x ∈ R , (5.44)
2
since for such a functional the minima and stationary points coincide, where
a stationary point is an x satisfying
0= ∇f(x)= Ax − b. (5.45)
d
In contrast to the notation x · y for the “short” space vectors x, y ∈ R we
T
write here the Euclidean scalar product as matrix product x y.
For the finite element discretization this corresponds to the equivalence
of the Galerkin method (2.23) with the Ritz method (2.24) if A is the
stiffness matrix and b the load vector (see (2.34) and (2.35)). More generally,
Lemma 2.3 implies the equivalence of (5.44) and (5.45), if as bilinear form
the so-called energy scalar product
T
x, y A := x Ay (5.46)
is chosen.
A general iterative method to solve (5.44) has the following structure:
Define a search direction d (k) .

˜
Minimize α → f(α):= f x (k) + αd (k) (5.47)
exactly or approximately, with the solution α k .
Define x (k+1) := x (k) + α k d (k) . (5.48)

If f is defined as in (5.44), the exact α k can be computed from the condition
˜
f (α)= 0 and
(k) (k) T (k)

˜
f (α)= ∇f x + αd d
as
g (k) T d (k)
α k = − T , (5.49)
d (k) Ad (k)
where

g (k) := Ax (k) − b = ∇f x (k) . (5.50)
The error of the kth iterate is denoted by e (k) :
e (k) := x (k) − x.
Some relations that are valid in this general fromework are the following:
Due to the one-dimensional minimization of f,wehave
T (k)
(k+1)
g d =0 , (5.51)