Page 139 - Basic Structured Grid Generation

128 Basic Structured Grid Generation

assuming that none of the diagonal entries of A are zero. Then possible choices for
(1)
iterative schemes, given an initial guess u , i = 1, 2,...,n,are
i
1
(k+1) (k) (k) (k)
u = [d 1 − (a 12 u + a 13 u +· · · + a 1n u )]
1 2 3 n
a 11
(k+1) 1 (k) (k) (k)
u = [d 2 − (a 21 u + a 23 u +· · · + a 2n u )]
2 1 3 n
a 22
...
1 (k) (k) (k)
(k+1)
u = [d n − (a n1 u + a n2 u +· · · + a n(n−1) u )], (5.49)
n 1 2 n−1
a nn
which is the Jacobi method, and
1
(k+1) (k) (k) (k)
u = [d 1 − (a 12 u + a 13 u +· · · + a 1n u )]
1 2 3 n
a 11
1
(k+1) (k+1) (k) (k)
u = [d 2 − (a 21 u + a 23 u +· · · + a 2n u )]
2 1 3 n
a 22
...
1
(k+1) (k+1) (k+1) (k+1)
u n = [d n − (a n1 u 1 + a n2 u 2 +· · · + a n(n−1) u n−1 )], (5.50)
a nn
(k+1)
called the Gauss-Seidel method, in which the new value u is used in the second
1
(k+1)
equation to calculate u 2 , both of these values are used in the third equation to
(k+1)
calculate u 3 , and the continual updating proceeds until the last equation. Thus
Gauss-Seidel involves immediate replacement of old u i values in the appropriate loca-
tion and therefore requires less storage space than the Jacobi method. It is also generally
faster than the Jacobi method.
Equations (5.50) can be written as
 
i−1 n
1
(k+1) (k+1) (k)
u =  d i − a ij u − a ij u  ,
i j j
a ii
j=1 j=i+1
i = 1, 2,...,n (i not summed). (5.51)
The SOR (Successive Over-Relaxation) method introduces an extra parameter ω,
called the acceleration parameter, which can speed up convergence of the iteration.
The scheme is given by
 
i−1 n
ω
(k+1) (k) (k+1) (k) (k)
u = u +  d i − a ij u − a ii u − a ij u  (5.52)
i i j i j
a ii
j=1 j=i+1
 
i−1 n
ω (k+1) (k) (k)
=  d i − a ij u j − a ij u j  + (1 − ω)u i , i = 1, 2,...,n,
a ii
j=1 j=i+1
(5.53)
which gives a weighted average of the old value of u i and the value given by eqn (5.51).
When ω = 1 the SOR method is the same as Gauss-Seidel. ‘Over-relaxation’ refers to