Page 140 - Basic Structured Grid Generation

Differential models for grid generation 129

choosing a value of ω between 1 and 2, while ‘under-relaxation’ would involve taking
0 <ω < 1.

5.5.3 The conjugate gradient method

The conjugate gradient method involves an iterative scheme for solving the matrix
equation Au = d for the n × 1 column vector u, given the n × n matrix A and column
vector d, which is of general use, but it is particularly appropriate for matrices A which
T
are symmetric and positive definite, satisfying u Au > 0for any n × 1 column vector
u not identically zero. Under these circumstances this method solves an equivalent
problem, that of minimizing the function
n n n
1
E(u 1 ,u 2 ,. ..,u n ) = a ij u i u j − d i u i , (5.54)
2
i=1 j=1 i=1
where a ij and d i are the elements of A and d respectively.

Exercise 4. Establish this equivalence, by demonstrating that E has one critical point
u (where all partial derivatives vanish) satisfying Au = d, and then showing that it is
a minimum (by representing E in the neighbourhood of the critical point in terms of
u = u+h, or directly evaluating the second-order terms in the Taylor Series expansion
of E about u.
The matrix formulation of E is

T
1 T
E = u Au − d u. (5.55)
2
A simple numerical approach to the problem of minimization is provided by the method
of steepest descents, in which, starting from some given point u i (regarded as a point
in an n-dimensional space), an iterative step involves a search for a minimum in the
value of E along the direction of steepest decrease of E at u 0 . This direction r is that
opposite to the direction of the gradient vector (the vector of partial derivatives) of E,
which gives the direction of steepest increase. At a point u the gradient vector is given
by Au − d (since A is symmetric), so that we take

r =−(Au − d) = d − Au. (5.56)
Thus when u = u i we have r = r i = d − Au i ,which we mayalsoregard asthe
residual at that point, bearing in mind the equivalent problem Au = d.
Putting u = u i + λ i r i = u i + λ i (d − Au i ) into eqn (5.55) (with no summation over
repeated indices) gives

1 T T 1 T 1 T T 1 2 T
u Ar i + r Au i − d r i + (λ i ) r Ar i
E = u Au i − d u i + λ i 2 i 2 i 2 i
2 i
1 T T T T 1 2 T
= u Au i − d u i + λ i (u Ar i − d r i ) + (λ i ) r Ar i
2 i
i
i
2
1 T T T T 1 2 T
= u Au i − d u i + λ i (u A − d )r i + (λ i ) r Ar i
2 i i 2 i
2 T
T
1
1 T
T
= u Au i − d u i − λ i r r i + (λ i ) r Ar i , (5.57)
i
2 i
i
2