Page 200 - Matrices theory and applications

10.3. The Jacobi Method
In particular, the spectrum of A consists of the diagonal terms of D,and
the Jacobi method is of order one at least.
Proof
With the optimal choice of (p, q), we have

2
2
pq
Hence, (n − n) a (k) 2 ≥ E k . 183

2
2 2
E k+1 ≤ 1 − 2 E k .
n − n
k
It follows that E k ≤ ρ E 0 .Inparticular, E k tends to zero as k → +∞.
It remains to show that D k converges too. A calculation using the
notation of Section 10.3.1 and the fact that k pq =0 yield
k pp − h pp = th pq .
(k+1) (k) (k)
Since |θ k |≤ π/4, we have |t|≤ 1, so that |a pp − a pp |≤ |a pq |. Likewise,
(k+1) (k) (k)
|a qq − a qq |≤ |a pq |. Since the other diagonal entries are unchanged, we
have D k+1 − D k ≤ E k .
k
We have seen that E k ≤ ρ E 0 . Therefore,
ρ k
D l − D k ≤ E 0 , l > k.
1 − ρ
The sequence (D k ) k∈IN is thus Cauchy, hence convergent. Since E k tends
to zero, A k converges to the same limit D. This matrix is diagonal, with
the same spectrum as A, since this is true for each A k . Finally, we obtain
2 2
(k)
2
2
2
A − D = D k − D + E k ≤ E k .
(1 − ρ) 2
10.3.4 Quadratic Convergence
The following statement shows that the Jacobi method compares rather
well with other methods.
Theorem 10.3.2 The Jacobi method with optimal choice of (p, q) is of
order two when the eigenvalues of A are simple, in the following sense. Let
N = n(n − 1)/2 be the number of elements under the diagonal. Then there
exists a number c> 0 such that
2
E k+N ≤ c E k ,
for every k ∈ IN.

Proof