Page 138 - Basic Structured Grid Generation

Differential models for grid generation 127

or
u i (b i − a i P i−1 ) = c i u i+1 + d i + a i Q i−1 ,

which is itself consistent with eqn (5.44) if
c i d i + a i Q i−1
P i = and Q i = , i = 2, 3,..., (N − 1). (5.45)
b i − a i P i−1 b i − a i P i−1
Since we now have a 1 = 0,
c 1 d 1
P 1 = and Q 1 = . (5.46)
b 1 b 1
We are now able to generate recursively the values of P 2 ,P 3 ,...,
P N−2 ,and Q 2 ,Q 3 ,...,Q N−1 . Since we have taken c N−1 = 0, we also have
P N−1 = 0.
Equation (5.44) now gives the value of u N−1 as

u N−1 = Q N−1 . (5.47)
We can now use eqn (5.44) to solve successively for u N−2 ,u N−3 ,. ..,u 1 .
For the Thomas Algorithm to be well-conditioned, it is sufficient that
|P i | 1, i = 1, 2,..., N − 1, (5.48)

since by eqn (5.44) the error in the computed value of u i+1 is multiplied by P i in
calculating u i . It may be shown that the conditions for diagonal dominance (5.43)
guarantee that (5.48) is satisfied.
The Thomas Algorithm is a powerful and convenient solution method for a set of
linear equations of the form (5.41), requiring computer storage and computer time of
2
3
the order of N rather than N or N . It can be extended to ‘block-tridiagonal’ systems
in which a i ,b i ,c i are square matrices and the unknowns u i are vectors.

5.5.2 Jacobi, Gauss-Seidel, SOR methods

In solving matrix equations Au = d for the n × 1 column vector u when the n × n
matrix A is large but very sparse (i.e. the entries are mostly zeros), iterative methods
are usually employed. Suppose we write the equations as
1
u 1 = [d 1 − (a 12 u 2 + a 13 u 3 +· · · + a 1n u n )]
a 11
1
u 2 = [d 2 − (a 21 u 1 + a 23 u 3 +· · · + a 2n u n )]
a 22
...
1
u n = [d n − (a n1 u 1 + a n2 u 2 + ··· + a n(n−1) u n−1 )],
a nn