Page 197 - Matrices theory and applications

10. Approximation of Eigenvalues
180
by translating A k → A k − α k I n . The strategies for the choice of α k are
described in [25]. This procedure is called Rayleigh translation. It allows
for a observeable improvement of the convergence of the QR method. If
the eigenvalues of A are simple, a suitable translation allows us to restrict
ourselves to the case of distinct moduli. But this trick has a nonnegligible
cost if A is a real matrix with a pair of complex conjugate eigenvalues,
since it requires a translation by a nonreal number α. As mentioned above,
the computations become much more costly than they are in the domain
of real numbers.
As k increases, the triangular form of A k appears first at the last row.
In other words, the sequence (A k ) nn converges more rapidly thanother
sequences (A k ) jj . When the last row is sufficiently close to (0,... , 0,λ n ),
the Rayleigh translation must be selected in such a way as to bring λ n−1 ,
instead of λ n , to the origin; and so on.
With a clever choice of Rayleigh translations, the QR method, when it
converges, is of order two for a generic matrix, and is of order three for a
Hermitian matrix.

10.3 The Jacobi Method

The Jacobi method allows for the approximate computation of the whole
spectrum of a real symmetric matrix A ∈ Sym .As in the QR method,
n
one constructs a sequence of matrices, unitarily similar to A.Inparticular,
the round-off errors are not amplified. Each iteration is cheap (O(n)opera-
tions), and the convergence is quadratic when the eigenvalues are distinct.
It is thus a rather efficient method.

10.3.1 Conjugating by a Rotation Matrix
Let 1 ≤ p, q ≤ n be two distinct indices and θ ∈ [−π, π)anangle. We
denote by R p,q (θ) the rotation matrix through the angle θ in the plane
p
q
spanned by e and e . For example, if p<q,then
. . . .
 
I p−1 . 0 . 0
 
 ··· cos θ ··· sin θ ··· 
 
. .
 . . 
R = R p,q (θ):=  0 . I q−p−1 . 0  .
 
··· ··· ···
 − sin θ cos θ 
. .
 
0 . . 0 . . I n−q