Page 201 - Matrices theory and applications

10. Approximation of Eigenvalues
184
We first remark that if i = j with {i, j} = {p l ,q l },then
√
(l)
(l+1)
|a
− a |≤ |t l | 2 E l ,
ij
ij
where t l =tan θ l .To see this,observe that 1 − c ≤ t and |s|≤ t
whenever |t|≤ 1. However, Theorem 10.3.1 ensures that D k converges
to diag(λ 1 ,... ,λ n ), where the λ j ’s are the eigenvalues of A. Since these
are distinct, there exist K ∈ IN and δ> 0 such that, if k ≥ K,then (10.5)
(k) (k)
min |a ii − a jj |≥ δ
i=j

for k ≥ K. We have therefore
δ k→+∞
|σ k |≥ √ −→ +∞.
2 E k
It follows that t k tends to zero and, more precisely, that
1
t k ∼− .
2σ k
Finally, there exists a constant c 1 such that
|t k |≤ c 1 E k .
Let us fix then k larger than K,and let us denoteby J the set of pairs
(p l ,q l )when k ≤ l ≤ k + N − 1. For such an index, we have E l ≤
ρ l−k E k ≤ E k .In particular, |t l |≤ c 1 E k .
If (p, q) ∈ J and if l< k+N is the largest index such that (p, q)= (p l ,q l ),
a repeated application of (10.5) shows that
√
2
|a (k+N) |≤ c 1 N 2 E k .
pq
If J is equal to the set of pairs (i, j)such that i<j, these inequalities
2
ensure that E k+N ≤ c 2 E k . Otherwise, there exists a pair (p, q)that
one twice sets to zero: (p, q)= (p l ,q l )= (p m ,q m )with k ≤ l< m < k + N.
In that case, the same argument as above shows that
√ √
2
E k+N ≤ E m ≤ 2N|a (m) |≤ 2 Nc 1 (m − l) E k .
pq
Remarks: Exercise 18 shows that the distance between the diagonal and
2
the spectrum of A is O( E k ), and not O( E k ) as naively expected. We
shall also analyze, in Exercise 10, the (bad) behavior of D k when we make
the opposite choice π/4 ≤|θ k |≤ π/2.
10.4 The Power Methods

The power methods allow only for the approximation of a single eigenvalue.
Of course, their cost is significantly lower than that of the previous ones.