Page 137 - Basic Structured Grid Generation

126 Basic Structured Grid Generation

involving a tridiagonal matrix (one in which the only non-zero entries appear along
the main diagonal and the two adjacent parallel diagonals on either side). These can
usually be solved efficiently using the Thomas Algorithm (otherwise known as the
Tridiagonal Matrix Algorithm), which is based on Gaussian Elimination. A typical set
of equations for the (N − 1) unknowns u 1 ,u 2 ,. ..,u N−1 ,is
−a i u i−1 + b i u i − c i u i+1 = d i , i = 1, 2,. ..,(N − 1), (5.41)

where the values of u 0 and u N are supposed known due to the given boundary
conditions.
The equivalent matrix equation is
Au = d (5.42)

where
 
b 1 −c 1 0 0 − – 0
 0 – – – 
−a 2 b 2 −c 2
 
0 −a 3 b 3 −c 3 – – –
 
 
0 0 – – – – –  ,
 
A = 
 
 − – – – – – 0 
 
 − −− – 0 −a N−2 b N−2 −c N−2 
0 – – 0 0 −a N−1 b N−1
   
u 1 d 1
u 2 d 2
   
   
− d 3
   
   
   
−  , −  .
u =  d = 
   
− −
   
   
−
   d N−2 
u N−1 d N−1
Here we have transferred the terms −a 1 u 0 and −c N−1 u N to the right-hand side, where
they are assumed to have been incorporated into the d 1 and d N−1 terms, respectively.
So now we can assume a 1 = c N−1 = 0 in eqn (5.41).
A is diagonally dominant if
b i > 0and b i > |a i |+ |c i |, i = 1, 2,..., (N − 1) (5.43)
The Thomas Algorithm replaces eqn (5.41) with a simpler recurrence relation from
which u i−1 has been eliminated, thereby reducing A to an upper triangular matrix. The
equations can then be solved by simple back substitution.
Suppose that we seek a recurrence relation of the form
u i = P i u i+1 + Q i , i = 1, 2,...,(N − 1) (5.44)
This is consistent with eqn (5.41) if
−a i (P i−1 u i + Q i−1 ) + b i u i − c i u i+1 = d i , i = 2, 3,...,(N − 1)