176
5 Approximation des valeurs propres et des vecteurs propres
posteriori suivante de l’erreur d’approximation sur λ m
|λ m − σ
(k)
| |
r
(k)
2
|(
w (k) ) ∗ q (k) |
,
k≥ 1,
(5.29)
o` u r
(k) = Aq
(k)
− σ
(k) q
(k) et o` u
w
(k) est la k-i` eme it´ er´ ee de la m´ ethode de la
puissance inverse pour approcher le vecteur propre `
a gauche associ´ e ` a λ m .
5.3.3 Impl´ ementations
L’analyse de convergence de la Section 5.3.1 montre que l’efficacit´ e de la m´ ethode de la puissance d´ epend fortement des valeurs propres dominantes. Plus
pr´ ecis´ ement, la m´ ethode est d’autant plus efficace que les valeurs dominantes
sont bien s´ epar´ ees, i.e. |λ 2 |/|λ 1 | | 1. Analysons `
a pr´ esent le comportement
des it´ erations (5.17) quand il y a deux valeurs propres dominantes de mˆ eme
module (c’est-` a-dire quand |λ 2 | = |λ 1 |). On doit distinguer trois cas :
1. λ 2 = λ 1 : les deux valeurs propres dominantes co¨ ıncident. La m´ ethode est
encore convergente, puisque pour k assez grand, (5.20) implique
A
k q
(0)
λ
k
1 (α 1 x 1 + α 2 x 2 )
qui est un vecteur propre de A. Pour k → ∞, la suite ˜
q
(k) (convenablement red´ efinie) converge vers un vecteur appartenant `
a l’espace engendr´ e
par x 1 et x 2 . La suite ν
(k) converge encore vers λ 1 .
2. λ 2 = −λ 1 : les deux valeurs propres dominantes sont oppos´ ees. Dans
ce cas, la valeur propre de plus grand module peut ˆ etre approch´ ee en
appliquant la m´ ethode de la puissance `
a la matrice A
2 . En effet, pour
i = 1, . . ., n, λ i (A
2 ) = [λ i (A)]
2 , donc λ
2
1 = λ
2
2 et on est ramen´ e au cas
pr´ ec´ edent avec la matrice A
2 .
3. λ 2 = λ 1 : les deux valeurs propres dominantes sont complexes conjugu´ ees.
Cette fois, des oscillations non amorties se produisent dans la suite q
(k)
et la m´ ethode de la puissance ne converge pas (voir [Wil65], Chapitre 9,
Section 12).
Pour l’impl´ ementation de (5.17), il est bon de noter que le fait de normaliser
le vecteur q
(k) ` a 1 permet d’´ eviter les probl` emes d’overflow (quand |λ 1 | > 1)
ou d’underflow (quand |λ 1 | < 1) dans (5.20). Indiquons aussi que la condition
α 1 = 0 (qui est a priori impossible ` a remplir quand on ne dispose d’aucune
information sur le vecteur propre x 1 ) n’est pas essentielle pour la convergence
effective de l’algorithme. En effet, bien qu’on puisse prouver qu’en arithm´ etique exacte la suite (5.17) converge vers le couple (λ 2 , x 2 ) si α 1 = 0 (voir
Exercice 8), les in´ evitables erreurs d’arrondi font qu’en pratique le vecteur
q
(k) contient aussi une composante non nulle dans la direction de x 1 . Ceci
permet ` a la valeur propre λ 1 d’ˆ etre “visible” et ` a la m´ ethode de la puissance
de converger rapidement vers elle.
5 Approximation des valeurs propres et des vecteurs propres
posteriori suivante de l’erreur d’approximation sur λ m
|λ m − σ
(k)
| |
r
(k)
2
|(
w (k) ) ∗ q (k) |
,
k≥ 1,
(5.29)
o` u r
(k) = Aq
(k)
− σ
(k) q
(k) et o` u
w
(k) est la k-i` eme it´ er´ ee de la m´ ethode de la
puissance inverse pour approcher le vecteur propre `
a gauche associ´ e ` a λ m .
5.3.3 Impl´ ementations
L’analyse de convergence de la Section 5.3.1 montre que l’efficacit´ e de la m´ ethode de la puissance d´ epend fortement des valeurs propres dominantes. Plus
pr´ ecis´ ement, la m´ ethode est d’autant plus efficace que les valeurs dominantes
sont bien s´ epar´ ees, i.e. |λ 2 |/|λ 1 | | 1. Analysons `
a pr´ esent le comportement
des it´ erations (5.17) quand il y a deux valeurs propres dominantes de mˆ eme
module (c’est-` a-dire quand |λ 2 | = |λ 1 |). On doit distinguer trois cas :
1. λ 2 = λ 1 : les deux valeurs propres dominantes co¨ ıncident. La m´ ethode est
encore convergente, puisque pour k assez grand, (5.20) implique
A
k q
(0)
λ
k
1 (α 1 x 1 + α 2 x 2 )
qui est un vecteur propre de A. Pour k → ∞, la suite ˜
q
(k) (convenablement red´ efinie) converge vers un vecteur appartenant `
a l’espace engendr´ e
par x 1 et x 2 . La suite ν
(k) converge encore vers λ 1 .
2. λ 2 = −λ 1 : les deux valeurs propres dominantes sont oppos´ ees. Dans
ce cas, la valeur propre de plus grand module peut ˆ etre approch´ ee en
appliquant la m´ ethode de la puissance `
a la matrice A
2 . En effet, pour
i = 1, . . ., n, λ i (A
2 ) = [λ i (A)]
2 , donc λ
2
1 = λ
2
2 et on est ramen´ e au cas
pr´ ec´ edent avec la matrice A
2 .
3. λ 2 = λ 1 : les deux valeurs propres dominantes sont complexes conjugu´ ees.
Cette fois, des oscillations non amorties se produisent dans la suite q
(k)
et la m´ ethode de la puissance ne converge pas (voir [Wil65], Chapitre 9,
Section 12).
Pour l’impl´ ementation de (5.17), il est bon de noter que le fait de normaliser
le vecteur q
(k) ` a 1 permet d’´ eviter les probl` emes d’overflow (quand |λ 1 | > 1)
ou d’underflow (quand |λ 1 | < 1) dans (5.20). Indiquons aussi que la condition
α 1 = 0 (qui est a priori impossible ` a remplir quand on ne dispose d’aucune
information sur le vecteur propre x 1 ) n’est pas essentielle pour la convergence
effective de l’algorithme. En effet, bien qu’on puisse prouver qu’en arithm´ etique exacte la suite (5.17) converge vers le couple (λ 2 , x 2 ) si α 1 = 0 (voir
Exercice 8), les in´ evitables erreurs d’arrondi font qu’en pratique le vecteur
q
(k) contient aussi une composante non nulle dans la direction de x 1 . Ceci
permet ` a la valeur propre λ 1 d’ˆ etre “visible” et ` a la m´ ethode de la puissance
de converger rapidement vers elle.