6. Valeurs et vecteurs propres
133
sont constituées de vecteurs propres. Au cours des itérations un terme peut
redevenir nul, mais on démontre que
lim
n$4
X
l6 =m
(d
(n)
lm )
2 =0
On arrête l’itération quand
1
q
P
l=1
(d
(n)
ll )
2
q
P
l=1
(d
(n+1)
ll
) 2
?%
En pratique, on a le choix à chaque pas d’itération du couple (s> t).O n
définit diérentes stratégies. Dans la méthode de Jacobi classique, on choisit
(s> t)t e l sq u e
¯
¯
¯d
(n)
st
¯
¯
¯ =sup
l6 =m
¯
¯
¯d
(n)
lm
¯
¯
¯
Dans la m é t h o d ed eJ a c o b ic y c l i q u e ,o ne ectue un balayage systématique
en prenant pour (s> t) les couples (1> 2), (1> 3), ...,(1>q) puis (2> 3),...,(2>q)>
etc., jusqu’à (q 1>q). Dans la méthode de Jacobi cyclique avec seuil,o n
eectue comme précédemment un balayage sur les éléments triangulaires
supérieurs, chaque élément d lm étant pris comme élément à annuler d st >
mais on ne retient le couple (s> t) que si |d lm | est supérieur à un certain
seuil qui peut être réajusté à chaque itération. La méthode de Jacobi est
stable, mais sa convergence est lente, ce qui en fait une méthode très peu
utilisée.
6.4 Méthode de Givens-Householder
Proposée en 1958, la méthode de Givens-Householder est la réunion de
deux algorithmes. La méthode de Householder met la matrice initiale D
sous la forme tridiagonale symétrique (cet algorithme a été étudié dans
le chapitre précédent). L’algorithme de Givens calcule les valeurs propres
d’une matrice tridiagonale symétrique. Supposons que D soit mis sous la
forme
E =
3
E
E
E
E
E
E
E
C
e 1 f 1 0
···
0
f 1 e 2 f 2
. . .
. . .
0 f 2
. . .
. . .
0
. . .
. . .
. . .
. . .
f q1
0 ··· 0
f q1 e q
4
F
F
F
F
F
F
F
D