Page 171 - Matrices theory and applications

9. Iterative Methods for Linear Problems
154
shows that

ω


|λ + ω − 1|≤ max


|a ii |
j<i
j>i

(9.2)
If |λ|≥ 1, we deduce that  |λ| |a ij | + |a ij |  ;1 ≤ i ≤ n  .
 
 
ω|λ|
|λ + ω − 1|≤ max |a ij | ;1 ≤ i ≤ n .
 |a ii | 
j =i
In case (1), this yields
|λ + ω − 1| <ω|λ|,
so that |λ|≤ |λ+ω−1|+|1−ω| < |λ|ω+1−ω;that is, (|λ|−1)(1−ω) <
0, which is a contradiction. In case (2), Proposition 4.5.2 says that
inequality (9.2) is strict. One concludes the proof the same way as in
case (1).
Of course, this result is not fully satisfactory, since ω ≤ 1is not the
hypothesis that we should consider. Recall that in practice, one uses over-
relaxation (that is, ω> 1), which turns out to be much more efficient than
the Gauss–Seidel method for an appropriate choice of the parameter.
9.3.2 The Case of a Hermitian Positive Definite Matrix
Let us begin with an intermediate result.
Lemma 9.3.1 If A and M + N are Hermitian positive definite (in a
∗
decomposition A = M − N), then ρ(M −1 N) < 1.
Proof
∗
∗
Letus remark firstthat M +N = M +M −A is necessarily Hermitian
when A is.
It is therefore enough to show that M −1 Nx A < x A for every nonzero
n
x ∈ CC ,where · A denotes the norm associated to A:
√
x A = x Ax.
∗
We have M −1 Nx = x − y with y = M −1 Ax. Hence,
2
M −1 Nx 2 A = x − y Ax − x Ay + y Ay
∗
∗
∗
A
2
∗
= x − y (M + N)y.
∗
A
We conclude by observing that y is not zero; hence y (M + N)y> 0.
∗
∗