Page 174 - Matrices theory and applications

2. ρ(G)= ρ(J) ,
3. the Gauss–Seidel method converges if and only if the Jacobi method
converges; moreover, in case of convergence, the Gauss–Seidel method
converges twice as fast as the Jacobi method;
4. the spectrum of J is even: Sp J = − Sp J.
Proof 2 9.4. The Tridiagonal Case 157
Formula (1) comes from Lemma 9.4.2. The spectrum of G is thus formed
of λ = 0 (which is of multiplicity [(n +1)/2] at least) and of squares of the
eigenvalues of J, which proves 2). Point 3 follows immediately. Finally, if
n
2
µ ∈ Sp J,then P J (µ) = 0, and also P G (µ ) = 0, so that (−µ) P J (−µ)= 0.
Finally, either P J (−µ) = 0, or µ =0= −µ,inwhichcase P J (−µ)also
vanishes.
In fact, the comparison given in point 3 of the proposition holds under
various assumptions. For example (see Exercises 3 and 8), it holds true
when D is positive and E, F are nonnegative.
We go back to the SOR, with an additional hypothesis: The spectrum of
J is real, and the Jacobi method converges. This property is satisfied, for
instance, when A is Hermitian positive definite, since Theorem 9.3.1 and
Proposition 9.4.1 ensure the convergence of the Jacobi method, and since
J is similar to the Hermitian matrix D −1/2 (E + F)D −1/2 .
We also select a real ω,that is, ω ∈ (0, 2), taking into account Proposition
9.2.1. The spectrum of J is thus formed of the eigenvalues
−λ r < ··· < −λ 1 ≤ λ 1 < ··· <λ r = ρ(J) < 1,

from Proposition 9.4.1. This notation does not mean that n be even: If n is
odd, λ 1 = 0. Aside from the zero eigenvalue, which does not enter into the
computation of the spectral radius, the eigenvalues of L ω are the squares
of the roots of
2
µ + ω − 1= µωλ a , (9.3)
for 1 ≤ a ≤ r. Indeed, taking −λ a instead of λ a furnishes the sames squares.
2 2
Let us define ∆(λ):= ω λ +4(1−ω), the discriminant of (9.3). If ∆(λ a )
is negative, both roots of (9.3) are complex conjugate, hence have modulus
1/2
|ω −1| .The case λ = 0 furnishes the same modulus. If that discriminant
is strictly positive, the roots are real and of distinct modulus. One of them,
2
denoted by µ a ,satisfies µ > |ω − 1|, the other one satisfying the opposite
a
inequality.
From Proposition 9.2.1, ρ(L ω ) is thus equal to one of the following:
•|ω − 1|,if ∆(λ a ) ≤ 0 for every a,that is, if ∆(ρ(J)) ≤ 0;
2
• the maximum of the µ ’s defined above, otherwise.
a