Page 199 - Matrices theory and applications

10. Approximation of Eigenvalues
182
The two angles correspond to the two possible roots of this quadratic
equation. We then obtain
1
,
s = tc.
c = √
2
1+ t
We shall see below that the best choice is the angle θ k ∈ [−π/4,π/4), which
corresponds to the unique root t in [−1, 1).
The computation of c, s needs only O(1) operations, so that the cost of
an iteration of the Jacobi method is 6n + O(1). Observe that an entry that
has vanished at an iteration becomes in general nonzero after a few more
iterations.
10.3.3 Convergence of the Jacobi Method
T
We use here the Schur norm M =(Tr M M) 1/2 , also called the Frobe-
nius norm, denoted elsewhere by M 2. Since it amounts to showing that
A (k) converges to a diagonal matrix, we decompose this matrix in the form
(k)
A (k) = D k + E k ,where D k =diag(a (k) ,... ,a nn ). To begin with, since the
11
sequence is formed of unitarily similar matrices, we have A (k) = A .
Lemma 10.3.1 We have
2

2
2
E k+1 = E k − 2 a (k) .
pq
Proof
It is sufficient to redo the calculations of Section 10.3.1, noting that
2
2
k + k 2 iq = h + h 2 iq
ip
ip
whenever i = p, q, while k 2 =0.
pq

2
2 2 (k)
We deduce from the lemma that D k+1 = D k +2 a pq . The
convergence of the Jacobi method depends, then, on the choice of the pair
(p, q) at each step. For example, the choice of the same pair at two consec-
utive iterations is stupid, since it yields A (k+1) = A (k) . A first strategy (the
so-called optimal choice) consists in taking the pair (p, q)thatoptimizes the
(k)
instantaneous decay of E k , that is, maximizes the number |a pq |.Since
this method involves the sorting of n(n−1)/2 entries, it is rather expensive.
Other strategies are available. One can, for instance, range over every pair
(k)
(p, q)with p< q,or choose a (p, q)for which |a pq | is larger than some
threshold. Here we shall study only the method with optimal choice.
Theorem 10.3.1 With the “optimal choice” of (p k ,q k ) and with the choice
θ k ∈ [−π/4,π/4), the Jacobi method converges in the following sense. There
exists a diagonal matrix D such that
√ %
k
A (k) − D ≤ 2 E 0 ρ , ρ := 1 − 2 .
2
1 − ρ n − n