182
5 Approximation des valeurs propres et des vecteurs propres
Alors
lim
k→+∞
T
(k) =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣
λ 1 t 12 . . . t 1n
0
λ 2 t 23 . . .
. . .
. . .
. . .
. . .
0
0
. . . λ n
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎦
.
(5.36)
Le taux de convergence est de la forme
|t
(k)
i,i−1 | = O
λ i
λ i−1
k
,
i= 2, . . ., n,
pour k → +∞.
(5.37)
Si on suppose de plus que la matrice A est sym´ etrique, la suite {T
(k)
} tend
vers une matrice diagonale.
Si les valeurs propres de A, bien que distinctes, ne sont pas bien s´ epar´ ees,
on d´ eduit de (5.37) que la convergence de T
(k) vers une matrice triangulaire
peut ˆ etre assez lente. Pour l’acc´ el´ erer, on peut recourir `
a la technique des
translations qu’on abordera `
a la Section 5.7.
Remarque 5.2 Il est toujours possible de r´ eduire la matrice A sous une forme
triangulaire au moyen d’algorithmes it´ eratifs utilisant des transformations non
orthogonales. C’est le cas par exemple de la m´ ethode LR (ou m´ ethode de
Rutishauser, [Rut58]), qui est en fait `
a l’origine de la m´ ethode QR (voir
aussi [Fra61], [Wil65]). La m´ ethode LR est bas´ ee sur la factorisation de la
matrice A sous la forme du produit de deux matrices L et R, respectivement
triangulaire inf´ erieure et triangulaire sup´ erieure, et sur la transformation (non
orthogonale)
L
−1 AL = L
−1 (LR)L = RL.
On utilise rarement la m´ ethode LR dans la pratique `
a cause de la perte de
pr´ ecision due `
a l’augmentation en module des coefficients sur-diagonaux de
R au cours de la factorisation LR. On trouvera dans [Wil65], Chapitre 8, des
d´ etails sur ce point particulier et sur l’impl´ ementation de l’algorithme ainsi
que des comparaisons avec la m´ ethode QR.
Exemple 5.4 On applique la m´ ethode QR `
a la matrice sym´ etrique A∈ R
4×4 telle
que aii = 4, pour i = 1, . . . , 4, et aij = 4 + i − j pour i < j ≤ 4, dont les valeurs
propres sont λ1 = 11.09, λ2 = 3.41, λ3 = 0.9 et λ4 = 0.51. Apr` es 20 it´ erations, on
obtient
T
(20) =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣
11.09
6.44 · 10
−10
−3.62 · 10
−15
9.49 · 10
−15
6.47 · 10
−10
3.41
1.43 · 10
−11
4.60 · 10
−16
1.74 · 10
−21
1.43 · 10
−11
0.9
1.16 · 10
−4
2.32 · 10
−25
2.68 · 10
−15
1.16 · 10
−4
0.58
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎦
.
5 Approximation des valeurs propres et des vecteurs propres
Alors
lim
k→+∞
T
(k) =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣
λ 1 t 12 . . . t 1n
0
λ 2 t 23 . . .
. . .
. . .
. . .
. . .
0
0
. . . λ n
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎦
.
(5.36)
Le taux de convergence est de la forme
|t
(k)
i,i−1 | = O
λ i
λ i−1
k
,
i= 2, . . ., n,
pour k → +∞.
(5.37)
Si on suppose de plus que la matrice A est sym´ etrique, la suite {T
(k)
} tend
vers une matrice diagonale.
Si les valeurs propres de A, bien que distinctes, ne sont pas bien s´ epar´ ees,
on d´ eduit de (5.37) que la convergence de T
(k) vers une matrice triangulaire
peut ˆ etre assez lente. Pour l’acc´ el´ erer, on peut recourir `
a la technique des
translations qu’on abordera `
a la Section 5.7.
Remarque 5.2 Il est toujours possible de r´ eduire la matrice A sous une forme
triangulaire au moyen d’algorithmes it´ eratifs utilisant des transformations non
orthogonales. C’est le cas par exemple de la m´ ethode LR (ou m´ ethode de
Rutishauser, [Rut58]), qui est en fait `
a l’origine de la m´ ethode QR (voir
aussi [Fra61], [Wil65]). La m´ ethode LR est bas´ ee sur la factorisation de la
matrice A sous la forme du produit de deux matrices L et R, respectivement
triangulaire inf´ erieure et triangulaire sup´ erieure, et sur la transformation (non
orthogonale)
L
−1 AL = L
−1 (LR)L = RL.
On utilise rarement la m´ ethode LR dans la pratique `
a cause de la perte de
pr´ ecision due `
a l’augmentation en module des coefficients sur-diagonaux de
R au cours de la factorisation LR. On trouvera dans [Wil65], Chapitre 8, des
d´ etails sur ce point particulier et sur l’impl´ ementation de l’algorithme ainsi
que des comparaisons avec la m´ ethode QR.
Exemple 5.4 On applique la m´ ethode QR `
a la matrice sym´ etrique A∈ R
4×4 telle
que aii = 4, pour i = 1, . . . , 4, et aij = 4 + i − j pour i < j ≤ 4, dont les valeurs
propres sont λ1 = 11.09, λ2 = 3.41, λ3 = 0.9 et λ4 = 0.51. Apr` es 20 it´ erations, on
obtient
T
(20) =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣
11.09
6.44 · 10
−10
−3.62 · 10
−15
9.49 · 10
−15
6.47 · 10
−10
3.41
1.43 · 10
−11
4.60 · 10
−16
1.74 · 10
−21
1.43 · 10
−11
0.9
1.16 · 10
−4
2.32 · 10
−25
2.68 · 10
−15
1.16 · 10
−4
0.58
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎦
.