6. Valeurs et vecteurs propres
135
à 1 et X une matrice triangulaire supérieure. L’algorithme est le suivant :
On décompose D en D = O 1 X 1 selon les principes de la décomposition OX .
Connaissant les matrices X 1 et O 1 , on forme le produit E 1 = X 1 O 1 qui a
les mêmes valeurs propres que D. On cherche alors la décomposition OX
de E 1 = O 2 X 2 .O ni t è r el ep r oc e s s u s
E n = X n O n
E n = O n+1 X n+1
En remarquant que O n E n = O n X n O n = E n1 O n = X n1 O n1 O n on peut
écrire E n = S
1
n DS n = La suite des matrices triangulaires supérieures E n =
S
1
n DS n où S n = O 1 O 2 ===O n converge vers une matrice E dont les éléments
diagonaux sont les valeurs propres de D. Les vecteurs propres de D s’expriment en fonction des vecteurs propres de E.S o i tY les vecteurs propres
de E. La matrice H n = S n Y converge vers la matrice des vecteurs propres
de D.SiD est une matrice symétrique définie positive, la méthode converge.
Au-delà d’un certain indice d’itération la convergence devient très lente :
il faut un grand nombre d’itérations pour gagner en précision sur le calcul
des valeurs propres. En particulier, lorsque les valeurs propres sont égales
ou peu diérentes, la convergence peut être très lente.
6.6 Méthode de Francis
La méthode de Francis est identique à la méthode de Rutishauser à ceci
près qu’elle utilise la décomposition TU (au lieu de la décomposition OX ).
Àc h a q u eé t a p e ,l am a t r i c eE n est mise sous la forme d’un produit T n U n
où T n est une matrice unitaire et U n une matrice triangulaire supérieure.
Ces matrices sont réutilisées pour former la matrice E n+1 = U n T n qui est à
son tour décomposée. L’algorithme est le suivant. On décompose la matrice
D en D = T 1 U 1 . Connaissant les matrices U 1 et T 1 , on forme le produit
E 1 = U 1 T 1 . Puis, on décompose E 1 en E 1 = T 2 U 2 . À chaque étape, on
décompose E n en
E n = T n+1 U n+1
les matrices sont réutilisées pour calculer
E n+1 = U n+1 T n+1
La matrice E n
E n+1 = S
n DS n
avec S n = T 1 T 2 ===T n
est une matrice triangulaire supérieure ayant sur sa diagonale les valeurs
propres de D. La matrice S n est la matrice des vecteurs propres de D>
i.e. dont les colonnes sont les vecteurs propres associés. Pour obtenir une
135
à 1 et X une matrice triangulaire supérieure. L’algorithme est le suivant :
On décompose D en D = O 1 X 1 selon les principes de la décomposition OX .
Connaissant les matrices X 1 et O 1 , on forme le produit E 1 = X 1 O 1 qui a
les mêmes valeurs propres que D. On cherche alors la décomposition OX
de E 1 = O 2 X 2 .O ni t è r el ep r oc e s s u s
E n = X n O n
E n = O n+1 X n+1
En remarquant que O n E n = O n X n O n = E n1 O n = X n1 O n1 O n on peut
écrire E n = S
1
n DS n = La suite des matrices triangulaires supérieures E n =
S
1
n DS n où S n = O 1 O 2 ===O n converge vers une matrice E dont les éléments
diagonaux sont les valeurs propres de D. Les vecteurs propres de D s’expriment en fonction des vecteurs propres de E.S o i tY les vecteurs propres
de E. La matrice H n = S n Y converge vers la matrice des vecteurs propres
de D.SiD est une matrice symétrique définie positive, la méthode converge.
Au-delà d’un certain indice d’itération la convergence devient très lente :
il faut un grand nombre d’itérations pour gagner en précision sur le calcul
des valeurs propres. En particulier, lorsque les valeurs propres sont égales
ou peu diérentes, la convergence peut être très lente.
6.6 Méthode de Francis
La méthode de Francis est identique à la méthode de Rutishauser à ceci
près qu’elle utilise la décomposition TU (au lieu de la décomposition OX ).
Àc h a q u eé t a p e ,l am a t r i c eE n est mise sous la forme d’un produit T n U n
où T n est une matrice unitaire et U n une matrice triangulaire supérieure.
Ces matrices sont réutilisées pour former la matrice E n+1 = U n T n qui est à
son tour décomposée. L’algorithme est le suivant. On décompose la matrice
D en D = T 1 U 1 . Connaissant les matrices U 1 et T 1 , on forme le produit
E 1 = U 1 T 1 . Puis, on décompose E 1 en E 1 = T 2 U 2 . À chaque étape, on
décompose E n en
E n = T n+1 U n+1
les matrices sont réutilisées pour calculer
E n+1 = U n+1 T n+1
La matrice E n
E n+1 = S
n DS n
avec S n = T 1 T 2 ===T n
est une matrice triangulaire supérieure ayant sur sa diagonale les valeurs
propres de D. La matrice S n est la matrice des vecteurs propres de D>
i.e. dont les colonnes sont les vecteurs propres associés. Pour obtenir une