180
5 Approximation des valeurs propres et des vecteurs propres
Le probl` eme serait r´ esolu si on savait d´ eterminer de mani` ere directe, c’est` a-dire en un nombre fini d’it´ erations, la matrice unitaire U de la d´ ecomposition
de Schur 1.4, i.e. la matrice U telle que T = U
∗ AU, o` u T est triangulaire
sup´ erieure avec t ii = λ i (A) pour i = 1, . . ., n. Malheureusement, d’apr` es le
th´ eor` eme d’Abel, d` es que n ≥ 5 la matrice U ne peut pas ˆ etre calcul´ ee de
fa¸ con directe (voir Exercice 6). Notre probl` eme ne peut donc ˆ etre r´ esolu que
de mani` ere it´ erative.
L’algorithme de r´ ef´ erence sur ce th` eme est la m´ ethode QR que nous n’examinerons que dans le cas des matrices r´ eelles (pour des remarques sur l’extension
des algorithmes au cas complexe, voir [GL89], Section 5.2.10 et [Dem97], Section 4.2.1).
Soit A ∈ R
n×n ; on se donne une matrice orthogonale Q
(0)
∈ R
n×n et on
pose T
(0) = (Q
(0) )
T AQ
(0) . Les it´ erations de la m´ ethode QR s’´ ecrivent pour
k = 1, 2, . . ., jusqu’` a convergence :
d´ eterminer Q
(k) , R
(k) telles que
Q
(k) R
(k) = T
(k−1)
(factorisation QR);
puis poser
T
(k) = R
(k) Q
(k) .
(5.32)
A chaque ´ etape k ≥ 1, la premi` ere phase consiste en la factorisation de la
matrice T
(k−1) sous la forme du produit d’une matrice orthogonale Q
(k) par
une matrice triangulaire sup´ erieure R
(k) (voir Section 5.6.3). La seconde phase
est un simple produit matriciel. Remarquer que
T
(k) = R
(k) Q
(k) = (Q
(k) )
T (Q
(k) R
(k) )Q
(k) = (Q
(k) )
T T
(k−1) Q
(k)
= (Q
(0) Q
(1)
· · · Q
(k) )
T A(Q
(0) Q
(1)
· · · Q
(k) ),
k ≥ 0,
(5.33)
autrement dit, toute matrice T
(k) est orthogonalement semblable ` a A. Ceci est
particuli` erement appr´ eciable pour la stabilit´ e de la m´ ethode. On a en effet vu
` a la Section 5.2 que dans ce cas le conditionnement du probl` eme aux valeurs
propres pour T
(k) est au moins aussi bon que celui pour A (voir aussi [GL89],
p. 360).
On examine `
a la Section 5.5 une impl´ ementation basique de la m´ ethode
QR (5.32) o` u on prend Q
(0) = I n . Un version plus efficace en termes de calcul,
qui d´ emarre avec T
(0) sous la forme d’une matrice de Hessenberg sup´ erieure,
est d´ ecrite en d´ etail `
a la Section 5.6.
Si A poss` ede des valeurs propres r´ eelles, distinctes en valeur absolue, nous
verrons `
a la Section 5.5 que la limite de T
(k) est une matrice triangulaire
sup´ erieure (avec bien sˆ ur les valeurs propres de A sur la diagonale). En revanche, si A a des valeurs propres complexes, la limite T de T
(k) ne peut pas
5 Approximation des valeurs propres et des vecteurs propres
Le probl` eme serait r´ esolu si on savait d´ eterminer de mani` ere directe, c’est` a-dire en un nombre fini d’it´ erations, la matrice unitaire U de la d´ ecomposition
de Schur 1.4, i.e. la matrice U telle que T = U
∗ AU, o` u T est triangulaire
sup´ erieure avec t ii = λ i (A) pour i = 1, . . ., n. Malheureusement, d’apr` es le
th´ eor` eme d’Abel, d` es que n ≥ 5 la matrice U ne peut pas ˆ etre calcul´ ee de
fa¸ con directe (voir Exercice 6). Notre probl` eme ne peut donc ˆ etre r´ esolu que
de mani` ere it´ erative.
L’algorithme de r´ ef´ erence sur ce th` eme est la m´ ethode QR que nous n’examinerons que dans le cas des matrices r´ eelles (pour des remarques sur l’extension
des algorithmes au cas complexe, voir [GL89], Section 5.2.10 et [Dem97], Section 4.2.1).
Soit A ∈ R
n×n ; on se donne une matrice orthogonale Q
(0)
∈ R
n×n et on
pose T
(0) = (Q
(0) )
T AQ
(0) . Les it´ erations de la m´ ethode QR s’´ ecrivent pour
k = 1, 2, . . ., jusqu’` a convergence :
d´ eterminer Q
(k) , R
(k) telles que
Q
(k) R
(k) = T
(k−1)
(factorisation QR);
puis poser
T
(k) = R
(k) Q
(k) .
(5.32)
A chaque ´ etape k ≥ 1, la premi` ere phase consiste en la factorisation de la
matrice T
(k−1) sous la forme du produit d’une matrice orthogonale Q
(k) par
une matrice triangulaire sup´ erieure R
(k) (voir Section 5.6.3). La seconde phase
est un simple produit matriciel. Remarquer que
T
(k) = R
(k) Q
(k) = (Q
(k) )
T (Q
(k) R
(k) )Q
(k) = (Q
(k) )
T T
(k−1) Q
(k)
= (Q
(0) Q
(1)
· · · Q
(k) )
T A(Q
(0) Q
(1)
· · · Q
(k) ),
k ≥ 0,
(5.33)
autrement dit, toute matrice T
(k) est orthogonalement semblable ` a A. Ceci est
particuli` erement appr´ eciable pour la stabilit´ e de la m´ ethode. On a en effet vu
` a la Section 5.2 que dans ce cas le conditionnement du probl` eme aux valeurs
propres pour T
(k) est au moins aussi bon que celui pour A (voir aussi [GL89],
p. 360).
On examine `
a la Section 5.5 une impl´ ementation basique de la m´ ethode
QR (5.32) o` u on prend Q
(0) = I n . Un version plus efficace en termes de calcul,
qui d´ emarre avec T
(0) sous la forme d’une matrice de Hessenberg sup´ erieure,
est d´ ecrite en d´ etail `
a la Section 5.6.
Si A poss` ede des valeurs propres r´ eelles, distinctes en valeur absolue, nous
verrons `
a la Section 5.5 que la limite de T
(k) est une matrice triangulaire
sup´ erieure (avec bien sˆ ur les valeurs propres de A sur la diagonale). En revanche, si A a des valeurs propres complexes, la limite T de T
(k) ne peut pas