Page 230 -

5.1. Linear Stationary Iterative Methods 213

Theorem 5.6 (of Kahan; Ostrowski and Reich)

(1) M SOR(ω) ≥|1 − ω| for ω =0.
(2) If A is symmetric and positive definite, then

M SOR(ω) < 1 for ω ∈ (0, 2) .

Proof: See [16, pp. 91 f.].

Therefore, we use only ω ∈ (0, 2). For a useful procedure we need more
information about the optimal relaxation parameter ω opt,given by

M SOR(ω opt ) =min M SOR(ω) ,
0<ω<2
and about the size of the contraction number. This is possible only if the
ordering of equations and unknowns has certain properties:
Definition 5.7 Amatrix A ∈ R m,m is consistently ordered if for the
partition (5.18), D is nonsingular and
C(α):= α −1 D −1 L + αD −1 R
has eigenvalues independent of α for α ∈ C\{0}.

There is a connection to the possibility of a multi-colour ordering, because
a matrix in the block form (5.39) is consistently ordered if it is block-
tridiagonal (i.e., A ij =0 for |i − j| > 1) and the diagonal blocks A ii are
nonsingular diagonal matrices (see [28, pp. 114 f.]).
In the case of a consistently ordered matrix one can prove a relation
between the eigenvalues of M J , M GS ,and M SOR(ω) .Fromthiswecan see
how much faster the Gauss–Seidel method converges than Jacobi’s method:
Theorem 5.8 If A is consistently ordered, then
2
(M J ) = (M GS ) .

Proof: For a special case see Remark 5.5.2 in [16].
Due to (5.4) we can expect a halving of the number of iteration steps,
but this does not change the asymptotic statement (5.27).
Finally, in the case that Jacobi’s method converges the following theorem
holds:
Theorem 5.9 Let A be consistently ordered with nonsingular diagonal ma-
trix D, the eigenvalues of M J being real and β := (M J ) < 1. Then we have
for the SOR method:
2
(1) ω opt = 2 1/2 ,
1+ (1 − β )