Page 175 - Matrices theory and applications

9. Iterative Methods for Linear Problems
158
The first case corresponds to the choice ω ∈ [ω J , 2), where

2
1 − ρ(J)
2
1 −
∈ [1, 2).
ω J =2
=
2

ρ(J)
2
1+
1 − ρ(J)
Then ρ(L ω )= ω − 1.
The second case is ω ∈ (0,ω J ). If ∆(λ a ) > 0, let us denote by Q a (X)
2
the polynomial X + ω − 1 − Xωλ a . The sum of its roots being positive,
µ a is the largest one; it is thus positive. Moreover, Q a (1) = ω(1 − λ a ) > 0
shows that both roots belong to the same half-line of IR \{1}. Since their
product has modulus less than or equal to one, they are less than or equal
to one. In particular,
1/2
|ω − 1| <µ a < 1.
This shows that ρ(L ω ) < 1holds for every ω ∈ (0, 2). Under our
hypotheses, the relaxation method is convergent.
If λ a = ρ(J), we have Q r (µ a )= µ a ω(λ a − ρ(J)) < 0. Hence, µ a lies
between both roots of Q r ,so that µ a <µ r . Finally, the case ∆(ρ(J)) ≤ 0
2
furnishes ρ(L ω )= µ .Wethenhave
r
dµ r
(2µ r − ωρ(J)) +1 − µ r ρ(J)= 0.
dω
Since 2µ r is larger than the sum ωρ(J) of the roots and since µ r ,ρ(J) ∈
[0, 1), one deduces that ω → ρ(L ω ) is nonincreasing over (0,ω J ).
We conclude that ρ(L ω ) reaches its minimum at ω J , that minimum being
2
1 − 1 − ρ(J)
ω J − 1= .
1+ 1 − ρ(J) 2
Theorem 9.4.1 [See Figure 9.1] Suppose that A is tridiagonal, D is in-
vertible, and that the eigenvalues of J are real and belong to (−1, 1).Assume
also that ω ∈ IR.
Then the relaxation method converges if and only if ω ∈ (0, 2).
Furthermore, the convergence ratio is optimal for the parameter
2
ω J := ∈ [1, 2),
1+ 1 − ρ(J) 2
is
where the spectral radius of L ω J
2

1 − 1 − ρ(J) 2 1 − 1 − ρ(J) 2
(ω J − 1=) = .
1+ 1 − ρ(J) 2 ρ(J)
Remarks:
• We shall see in Exercise 7 that Theorem 9.4.1 extends to complex
values of ω: Under the same assumptions, ρ(L ω ) is minimal at ω J ,
and the relaxation method converges if and only if |ω − 1| < 1.