196
5 Approximation des valeurs propres et des vecteurs propres
d´ eterminer Q
(k) , R
(k) tels que
Q
(k) R
(k) = T
(k−1)
− µI
(factorisation QR);
puis, poser
T
(k) = R
(k) Q
(k) + µI,
(5.52)
o` u T
(0) =
Q
(0)
T AQ
(0) est une matrice de Hessenberg sup´ erieure. Comme la
factorisation QR dans (5.52) est effectu´ ee sur la matrice translat´ ee T
(k−1)
−µI,
le scalaire µ est appel´ e facteur de translation (shift en anglais). Les matrices
T
(k) g´ en´ er´ ees par (5.52) sont encore semblables ` a la matrice initiale A, puisque
pour tout k ≥ 1,
R
(k) Q
(k) + µI =
Q
(k)
T
Q
(k) R
(k) Q
(k) + µQ
(k)
=
Q
(k)
T
Q
(k) R
(k) + µI
Q
(k) =
Q
(0) Q
(1)
· · · Q
(k)
T A
Q
(0) Q
(1)
· · · Q
(k)
.
Supposons µ fix´ e et les valeurs propres de A telles que
|λ 1 − µ| ≥ |λ 2 − µ| ≥ . . . ≥ |λ n − µ|.
On peut alors montrer que, pour 1 < j ≤ n, le coefficient sous-diagonal t
(k)
j,j−1
tend vers z´ ero avec une vitesse proportionnelle au quotient
|(λ j − µ)/(λ j−1 − µ)|
k .
Ceci permet d’´ etendre le r´ esultat de convergence (5.37) `
a la m´ ethode QR avec
translations (voir [GL89], Sections 7.5.2 et 7.3).
Le r´ esultat ci-dessus sugg` ere que si µ est choisi de mani` ere ` a ce que
|λ n − µ| < |λ i − µ|,
i= 1, . . ., n − 1,
alors le coefficient t
(k)
n,n−1 tend rapidement vers z´ ero quand k augmente. Dans
le cas extrˆ eme o` u µ est ´ egal ` a une valeur propre de T
(k) , et donc de A, on
a t
(k)
n,n−1 = 0 et t
(k)
n,n = µ. En pratique on prend dans la m´ ethode QR avec
translations
µ = t
(k)
n,n .
La convergence vers z´ ero de la suite
t
(k)
n,n−1
est alors quadratique
dans le sens suivant : si |t
(k)
n,n−1 |/T
(0)
2 = η k < 1, pour k ≥ 0, alors
|t
(k+1)
n,n−1 |/T
(0)
2 = O(η
2
k ) (voir [Dem97], p. 161-163 et [GL89], p. 354-355).
Quand on impl´ emente la m´ ethode QR avec translations, on peut exploiter
ce r´ esultat avec profit en examinant la taille des coefficients sous-diagonaux
t
(k)
n,n−1 . En pratique, t
(k)
n,n−1 est remplac´ e par z´ ero si
|t
(k)
n,n−1 | ≤ ε(|t
(k)
n−1,n−1 | + |t
(k)
n,n |),
k ≥ 0,
(5.53)
5 Approximation des valeurs propres et des vecteurs propres
d´ eterminer Q
(k) , R
(k) tels que
Q
(k) R
(k) = T
(k−1)
− µI
(factorisation QR);
puis, poser
T
(k) = R
(k) Q
(k) + µI,
(5.52)
o` u T
(0) =
Q
(0)
T AQ
(0) est une matrice de Hessenberg sup´ erieure. Comme la
factorisation QR dans (5.52) est effectu´ ee sur la matrice translat´ ee T
(k−1)
−µI,
le scalaire µ est appel´ e facteur de translation (shift en anglais). Les matrices
T
(k) g´ en´ er´ ees par (5.52) sont encore semblables ` a la matrice initiale A, puisque
pour tout k ≥ 1,
R
(k) Q
(k) + µI =
Q
(k)
T
Q
(k) R
(k) Q
(k) + µQ
(k)
=
Q
(k)
T
Q
(k) R
(k) + µI
Q
(k) =
Q
(0) Q
(1)
· · · Q
(k)
T A
Q
(0) Q
(1)
· · · Q
(k)
.
Supposons µ fix´ e et les valeurs propres de A telles que
|λ 1 − µ| ≥ |λ 2 − µ| ≥ . . . ≥ |λ n − µ|.
On peut alors montrer que, pour 1 < j ≤ n, le coefficient sous-diagonal t
(k)
j,j−1
tend vers z´ ero avec une vitesse proportionnelle au quotient
|(λ j − µ)/(λ j−1 − µ)|
k .
Ceci permet d’´ etendre le r´ esultat de convergence (5.37) `
a la m´ ethode QR avec
translations (voir [GL89], Sections 7.5.2 et 7.3).
Le r´ esultat ci-dessus sugg` ere que si µ est choisi de mani` ere ` a ce que
|λ n − µ| < |λ i − µ|,
i= 1, . . ., n − 1,
alors le coefficient t
(k)
n,n−1 tend rapidement vers z´ ero quand k augmente. Dans
le cas extrˆ eme o` u µ est ´ egal ` a une valeur propre de T
(k) , et donc de A, on
a t
(k)
n,n−1 = 0 et t
(k)
n,n = µ. En pratique on prend dans la m´ ethode QR avec
translations
µ = t
(k)
n,n .
La convergence vers z´ ero de la suite
t
(k)
n,n−1
est alors quadratique
dans le sens suivant : si |t
(k)
n,n−1 |/T
(0)
2 = η k < 1, pour k ≥ 0, alors
|t
(k+1)
n,n−1 |/T
(0)
2 = O(η
2
k ) (voir [Dem97], p. 161-163 et [GL89], p. 354-355).
Quand on impl´ emente la m´ ethode QR avec translations, on peut exploiter
ce r´ esultat avec profit en examinant la taille des coefficients sous-diagonaux
t
(k)
n,n−1 . En pratique, t
(k)
n,n−1 est remplac´ e par z´ ero si
|t
(k)
n,n−1 | ≤ ε(|t
(k)
n−1,n−1 | + |t
(k)
n,n |),
k ≥ 0,
(5.53)