Page 227 -

210 5. Iterative Methods for Systems of Linear Equations

This shows the stringency of Theorem 3.45, and again we can conclude that
π π 2
(M ¯ω )= cos ≈ 1 − . (5.35)
n 2n 2
Due to Theorem 3.45 the convergence behaviour seen for the model problem
is also valid in general for quasi-uniform triangulations.

5.1.4 SOR and Block-Iteration Methods

We assume again that A is a general nonsingular matrix. For the relaxation
of the Gauss–Seidel method we use it in the form

Dx (k+1) = −Lx (k+1) − Rx (k) + b,
instead of the resolved form (5.20).
The relaxed method is then

(k+1) (k+1) (k) (k)
Dx = ω − Lx − Rx + b +(1 − ω)Dx (5.36)
with a relaxation parameter ω> 0. This is equivalent to

(D + ωL) x (k+1) =(−ωR +(1 − ω)D) x (k) + ωb . (5.37)
Hence
−1
:= (D + ωL) (−ωR +(1 − ω)D) ,
M ω
−1
N ω := (D + ωL) ω.
In the application to discretizations of boundary value problems, nor-
mally we choose ω> 1, which means overrelaxation. This explains the
name of the SOR method as an abbreviation of successive overrelaxation.
The effort to execute an iteration step is hardly higher than for the Gauss–
Seidel method. Although we have to add 3m operations to the evaluation
of the right side of (5.36), the forward substitution to solve the auxiliary
system of equations in (5.37) is already part of the form (5.36).
The calculation of the optimal ¯ω here is more difficult, because M ω
depends nonlinearly on ω. Only for special classes of matrices can the opti-
mal ¯ω minimizing (M ω ) be calculated explicitly in dependence on (M 1 ),
the convergence rate of the (nonrelaxed) Gauss–Seidel method. Before we
sketch this, we will look at some further variants of this procedure:
The matrix N ω is nonsymmetric even for symmetric A.One gets a sym-
metric N ω if after one SOR step another one is performed in which the
indices are run through in reverse order m, m − 1,... , 2, 1, which means
that L and R are exchanged. The two half steps
1
1 (k+ ) (k) (k)
(k+ )
Dx 2 = ω − Lx 2 − Rx + b +(1 − ω)Dx ,
1 1
2 ,
2 − Rx
Dx (k+1) = ω − Lx (k+ ) (k+1) + b +(1 − ω)Dx (k+ )