EXPLANATION FILE OF MODULE FSEIDEL
==================================
Iterative Methods for Linear Systems A.x = B
--------------------------------------------
A Relaxation Method using the Gauss-Seidel Method
-------------------------------------------------
1. Introduction
------------
The Gauss-Seidel iteration differs from the Jacobi iterations only slightly,
st
for in it the calculated (v+1) approximations of the leading coefficients
v st
x1, x2, ..., x of x are used when calculating the (v+1) approximation of
i-1
x . For this method, the iteration rule becomes:
i
(v+1) (v) (v+1)
x = Brx + Blx + c
with | 0 b12 b13 ... b1n |
| 0 0 ... |
Br = | ---------------------- |
| 0 0 ... b n-1,n |
| 0 0 ... 0 |
(5.11)
and | 0 0 ... 0 |
| b21 ... |
Bl = | ---------------------- |
| bn1 bn2 ... b n,n-1 |
and | -a /a for i<>k
c = a / a , b = | ik ii
i i ii ik |
| 0 for i=k
Written out componentwise for i = 1, ... , n and v = 0, 1,2, ... we have:
(v+1) n (v) i-1 (v+1)
x = c + Sum b x + Sum b x (5.12)
i i k=i+1 ik k k=1 ik k
bi n aik (v) i-1 aik (v+1)
= --- - Sum --- x - Sum --- x
aii k=i+1 aii k k=1 aii k
The following convergence criteria insure convergence for the Gauss-Seidel
method:
1) the row sum criterion:
n n |aik|
max Sum |b | = max Sum |---| <= L < 1 or
1<=i<=n k=1 ik 1<=i<=n k=1 |aii| inf
k<>i
2) the column sum criterion:
n n |aik|
max Sum |b | = max Sum |---| <= L < 1 or
1<=k<=n i=1 ik 1<=k<=n i=1 |aii| 1
i<>k
T
3) if A is positive definite (x Ax > 0 for all x <> 0), then the Gauss-
Seidel method converges.
It is helpful to visualize the calculations in a scheme of the following form:
COMPUTATIONAL SCHEME (Gauss-Seidel iteration for n=3)
-----------------------------------------------------
(0) (1)
ci | Br or bik for k>= i | Bl or bik for k< i | xi | xi | ... |
---------------------------------------------------------------------
b1 | | | | | |
--- | 0 -a12/a11 -a13/a11 | 0 0 0 | 0 | | |
a11 | | | | | |
| | | | | |
b2 | | | | | |
--- | 0 0 -a23/a22 | -a21/a22 0 0 | 0 | | |
a22 | | | | | |
| | | | | |
b3 | | | | | |
--- | 0 0 0 | -a31/a33 -a32/a33 0 | 0 | | |
a33 | | | | | |
---------------------------------------------------------------------
2. Iteration Rule
--------------
Given the linear system A.x = B, so the iteration rule for the Gauss-Seidel
method is
(v+1) (v) (v+1)
x = Brx + Blx + c for v = 0,1,2...
We can rewrite this as
(v+1) (v) (v)
| x = x + z for
| (v) (v+1) (v) (5.17)
| z = c + Bl x - (I - Br) x ,
where Br and Bl denote the triangular matrices in (5.11).
(v) (v)
If one replaces the correction vector z by wz in (5.17) for a relaxa-
tion coefficient w, then one obtains the iteration rule for the method of
"successive relaxation":
(v+1) (v) (v+1) (v)
x = x + w [c + Blx - (I - Br)x ] (5.18)
The calculation of an optimum value for w is difficult. It is possible to
prove that the relaxation method (5.18) can only converge if 0 < w < 2.
The optimum correlation factor for the "successive overrelaxation method",
abbreviated customarily as "SOR method" is
2
w = -------------------2
opt 1 + sqrt(1 - lambda )
1
for a linear system with a positive definite, tridiagonal or block tridiagonal
matrix, A. Here lambda is the largest eigenvalue of the matrix B + B .
1 l r
Matrices of this kind appear naturally in discretizations of elliptic boundary
value problems. ln this case the SOR method converges much faster with Wopt
than a relaxation method with Jacobi's method.
3. Estimate for the Optimal Relaxation Coefficient, an Adaptive SOR Method
-----------------------------------------------------------------------
In order to speed up the method, at first a certain number l of steps
( l >= 1) is performed using the GauJ3-Seidel method for a fixed relaxation
coefficient w. Then the near optimal relaxation coefficient is obtained from:
-----------------------------------------------------------------------------
SOR ALGORITHM
-------------
Given: Ax = b, where A satisfies the hypothesis for the GauJ3-Seidel method
and we assume that all eigenvalues of the iteration matrix B are real.
Find: approximate solution x.
Set: w := 1, q := 1, v := O.
Choose: accuracy bound eps real, eps > 0,
number of steps l between adjustments for the relaxation parameter;
integer l >= 1.
starting vector x(O).
For each v = 0,1,2,... perform the following steps:
(v+1)
1. Compute x according to (5.18). If v is an integer multiple of l, conti-
nue with step 2, otherwise go to step 3.
2. To adjust the relaxation coefficient compute
(v+1) (v)
|xk - xk |
q = max ----------------
k (v) (v-1)
|xk - xk |
if q > 1, raise v by 1 and go to step 1; otherwise set
q = max (q, w-1)
and compute the new approximate relaxation coefficient as:
2
w = --------------------------
1 ( q+w-1 ) 2
1 + sqrt(1 - - (-------)
q ( w )
3. If (v+1) (v) (v+1)
||x - x || <= eps(1-q) ||x || ,
inf inf
(v+1
stop the iteration with x == x ; otherwise set v=v+1 and continue with
step 1.
-----------------------------------------------------------------------------
From [BIBLI 11].
------------------------------------------
End of file fseidel .txt