5.8 Calcul des valeurs propres des matrices sym´ etriques
199
On note c = cos θ et s = sin θ, les calculs pour obtenir les nouveaux coefficients
de A
(k) ` a partir de ceux de A
(k−1) s’´ ecrivent
⎡
⎣
a
(k)
pp
a
(k)
pq
a
(k)
pq
a
(k)
qq
⎤
⎦ =
c s
−s c
T
⎡
⎣
a
(k−1)
pp
a
(k−1)
pq
a
(k−1)
pq
a
(k−1)
qq
⎤
⎦
c s
−s c
.
(5.55)
Si a
(k−1)
pq
= 0, on peut obtenir (5.54) en prenant c = 1 et s = 0. Si a
(k−1)
pq
= 0,
on pose t = s/c, et (5.55) n´ ecessite la r´ esolution de l’´ equation
t
2 + 2ηt − 1 = 0,
η=
a
(k−1)
qq
− a
(k−1)
pp
2a
(k−1)
pq
.
(5.56)
On choisit la racine t = 1/(η +
1 + η 2 ) de (5.56) si η ≥ 0, autrement on
prend t = −1/(−η +
1 + η 2 ) ; puis, on pose
c =
1
√
1 + t 2
,
s= ct.
(5.57)
Pour examiner la vitesse avec laquelle les termes extra-diagonaux de A
(k)
tendent vers z´ ero, il est commode d’introduire, pour une matrice donn´ ee M ∈
R
n×n , la quantit´ e
Ψ(M) =
⎛
⎜
⎝
n
i,j=1
i =j
m
2
ij
⎞
⎟
⎠
1/2
=
2
F −
n
i=1
m
2
ii
1/2
.
(5.58)
La m´ ethode de Jacobi assure que Ψ(A
(k) ) ≤ Ψ(A
(k−1) ), pour tout k ≥ 1. En
effet le calcul de (5.58) pour la matrice A
(k) donne
(Ψ(A
(k) ))
2 = (Ψ(A
(k−1) ))
2
− 2
a
(k−1)
pq
2 ≤ (Ψ(A
(k−1) ))
2 .
(5.59)
L’estimation (5.59) sugg` ere qu’` a chaque ´ etape k, le choix optimal des indices
p et q est celui qui implique
|a
(k−1)
pq
| = max
i =j
|a
(k−1)
ij
|.
Mais le coˆ ut de cette m´ ethode est de l’ordre de n
2 flops pour la recherche du
coefficient de module maximum, et de l’ordre de n flops pour l’´ etape de mise ` a
jour A
(k) = (G pq )
T A
(k−1) G pq (voir Section 5.6.5). On propose donc une autre
solution, appel´ ee m´ ethode de Jacobi cyclique par lignes, dans laquelle le choix
des indices p et q est fait par un balayage des lignes de la matrice A
(k) selon
l’algorithme suivant :
pour tout k = 1, 2, . . . et pour la ligne i de A
(k) (i = 1, . . ., n − 1), on
pose p = i et q = (i + 1), . . . , n. Chaque balayage n´ ecessite N = n(n − 1)/2