Page 141 - Basic Structured Grid Generation

130 Basic Structured Grid Generation

where, for example, the symmetry of A has been used in the identity
T
1 T 1 T 1 T T 1 T
u Ar i =
u Ar i
2 i
2 i
2 i 2 i = r A u i = r Au i .
It is easy to see that the expression (5.57) is minimized when λ i takes the (positive)
value
T
r r i
i
λ i = ,
T
r Ar i
i
giving the iterative scheme

T
r r i
i
u i+1 = u i + r i . (5.58)
T
r Ar i
i
This scheme has the feature that the direction of search r i+1 is always orthogonal
to the direction r i at the previous iterative step, since the scalar product

T
r r i
T
T
T
r
r T i+1 i = (d − u T i+1 A)r i = d r i − u + T i r T Ar i
i
i
r Ar i
i
T T T T T
= (d − u A)r i − r r i = r r i − r r i = 0.
i
i
i
i
However, this can often lead to an inefficient solution procedure, and the method of
steepest descents can be quite slow. Various methods have been proposed to accelerate
the procedure, and the conjugate gradient method may be regarded as one of these. Here
the direction of search becomes p i , so that at each iterative step (when A is symmetric
and positive definite) we search for the minimum value of E with u = u i + λ i p i and
varying λ i . Thus
T
1
T
T
E = (u + λ i p )A(u i + λ i p i ) − d (u i + λ i p i )
2 i i
1 T T T T 1 2 T
= u Au i − d u i + λ i (u A − d )p i + (λ i ) p Ap i
i
i
2 i
2
1
1 T
2 T
T
T
= u Au i − d u i − λ i r p i + (λ i ) p Ap i ,
2 i i 2 i
where the residual r i is given by
r i = d − Au i . (5.59)
We minimize E as a function of λ i by taking
T
r p i
i
λ i = . (5.60)
T
p Ap i
i
It remains to set up an iterative scheme for the selection of p i , and we choose
(5.61)
p i+1 = r i+1 + α i p i
for some scalar α i . The iteration will begin with u = u 0 and p 0 = r 0 , as in the method
of steepest descents.
Note that from eqn (5.59) we have
r i+1 = r i − A(u i+1 − u i ) = r i − λ i Ap i . (5.62)