Page 225 -

208 5. Iterative Methods for Systems of Linear Equations

which means
M ω := ωM +(1 − ω)I, N ω := ωN , (5.31)
or if the condition of consistency M = I − NA holds,

x (k+1) = ω x (k) − N Ax (k) − b +(1 − ω)x (k)

= x (k) − ωN Ax (k) − b .
Let us assume for the procedure (5.6) that all eigenvalues of M are real.
For the smallest one λ min and the largest one λ max we assume
λ min ≤ λ max < 1;

this is, for example, the case for the Richardson method. Then also the
eigenvalues of M ω are real, and we conclude that

λ i (M ω )= ωλ i (M)+ 1 − ω =1 − ω 1 − λ i (M)
if the λ i (B) are the eigenvalues of B in an arbitrary ordering. Hence

(M ω )= max |1 − ω (1 − λ min (M))| , |1 − ω (1 − λ max (M))| ,
since f(λ):= 1 − ω(1 − λ) is a straight line for a fixed ω (with f(1) = 1
and f(0) = 1 − ω).

f ρ(M )
ω
1 1 - 1 + ω ( 1 − λ min )
λ max
ω 1 - ω ( 1 − λ max )
1
λ ω ω
λ min λ max
1 λ min
1
ω 2 1 - ω ( 1 − λ min )
..
f (λ) for ω < 1 and ω > 1
2
1
Figure 5.1. Calculation of ¯ω.
For the optimal ¯ω, i.e., ¯ω with
(M ¯ω )= min (M ω ) ,
ω>0
we therefore have, as can be seen from Figure 5.1,

1 − ¯ω (1 − λ max (M)) = −1+ ¯ω (1 − λ min (M))
2
⇐⇒ ¯ ω = .
2 − λ max (M) − λ min (M)
Hence ¯ω> 0and
(M ¯ω )= 1 − ¯ω(1 − λ max (M)) < 1;