Page 183 - Matrices theory and applications

9. Iterative Methods for Linear Problems
166
Frobenius theorem, prove that either 1 ≤ ρ(J) ≤ ρ(G)or ρ(G) ≤
ρ(J) ≤ 1. In particular, as in point 3 of Proposition 9.4.1, the Jacobi
and Gauss–Seidel methods converge or diverge simultaneously, and
Gauss–Seidel is faster in the former case. Hint: Prove that
and (ρ(G) ≥ 1) =⇒ (ρ(J) ≥ 1) =⇒ (ρ(G) ≥ ρ(J))
(ρ(G) ≤ 1) =⇒ (ρ(J) ≥ ρ(G)).
4. Let n ≥ 2and A ∈ HPD n be given. Assume that A is tridiagonal.
(a) Verify that the spectrum of J is real and even.
(b) Show that the eigenvalues of J satisfy λ< 1.
(c) Deduce that the Jacobi method is convergent.
∗
5. Let A ∈ HPD n , A = D − E − E . Use the Hermitian norm · 2.
n
2
(a) Show that |((E + E )v, v)|≤ ρ(J) D 1/2 v for every v ∈ CC .
∗
Deduce that
1+ ρ(J)
K(A) ≤ K(D).
1 − ρ(J)
(b) Let us define a function by
√
x − 1
g(x):= √ .
x +1
Verify that

2
1+ ρ(J) 1 − 1 − ρ(J)
g = .
1 − ρ(J) ρ(J)
(c) Deduce that if A is tridiagonal and if D = dI n , then the con-
vergence ratio θ of the conjugate gradient is the half of that of
SOR with optimal parameter.
6. Here is another proof of Theorem 9.3.1, when ω is real. Let A ∈
HPD n .
(a) Suppose we are given ω ∈ (0, 2).
i. Assume that λ = e 2iθ (θ real) is an eigenvalue of L ω . Show
that (1 − ω − λ)e −iθ ∈ IR.
ii. Deduce that λ = 1, then show that this case is impossible
too.
iii. Let m(ω) be the number of eigenvalues of L ω of modulus
less than or equal to one (counted with multiplicities). Show
that m is constant on (0, 2).
(b) i. Compute
1
lim (L ω − I n ).
ω→0 ω