Page 198 - Matrices theory and applications

181
10.3. The Jacobi Method
T
If H is a symmetric matrix, we compute K := R
also symmetric. Setting c =cos θ, s =sin θ the following formulas hold:
k ij
if i = p, q,
= ch ip − sh iq
k ip
if i = p, q,
= ch iq + sh ip
k iq
2
2
= c h pp + s h qq − 2csh pq ,
k pp = h ij if i, j = p, q, −1 HR = R HR,which is
2
2
k qq = c h qq + s h pp +2csh pq ,
2
2
k pq = cs(h pp − h qq )+(c − s )h pq .
The cost of the computation of entries k ij for i, j = p, q is zero; that of
k pp ,k qq ,and k pq is O(1). The cost of this conjugation is thus 6n + O(1)
T
operations, keeping in mind the symmetry K = K.
Let us remark that the conjugation by the rotation through the angle
θ±π yields the same matrix K. For this reason, we limit ourselves to angles
θ ∈ [−π/2,π/2).
10.3.2 Description of the Method
One constructs a sequence A (0) = A, A (1) ,... of symmetric matrices,
each one conjugate to the previous one by a rotation as above: A (k+1) =
(R (k) T (k) R (k) .Atstep k, we choose two distinct indices p and q (in fact,
) A
(k) (k)
p k ,q k ) in such a way that a pq = 0 (if it is not possible, A is already a
diagonal matrix similar to A). We then choose θ (in fact θ k )in such a way
(k+1)
that a pq = 0. From the formulas above, this is equivalent to
2
2
cs(a (k) − a (k) )+(c − s )a (k) =0.
pp
pq
qq
This amounts to solving the equation
(k) (k)
a qq − a pp
cot 2θ = =: σ k . (10.4)
(k)
2a pq
This equation possesses two solutions in [−π/2,π/2), namely θ k ∈
[−π/4,π/4) and θ k ± π/2. There are thus two possible rotation matri-
ces, which yield to two distinct results. Once the angle has been selected,
its computation is useless (it would be actually rather expensive). In fact,
t := tan θ k solves
2t
=tan 2θ;
1 − t 2
that is,
2
t +2tσ k − 1=0.