5.3 La m´ ethode de la puissance
175
Cela revient `
a supposer que la valeur propre λ m qui est la plus proche de µ a
une multiplicit´ e ´ egale ` a 1. De plus, (5.27) montre que ξ m est la valeur propre
de M
−1
µ de plus grand module ; en particulier, si µ = 0, λ m est la valeur propre
de A de plus petit module.
Etant donn´ e un vecteur initial arbitraire q
(0)
∈ C
n de norme euclidienne
´ egale ` a 1, on construit pour k = 1, 2, . . . la suite d´ efinie par
(A − µI) z
(k) = q
(k−1) ,
q
(k) = z
(k) /z
(k)
2 ,
σ
(k) = (q
(k) )
∗ Aq
(k) .
(5.28)
Remarquer que les vecteurs propres de M µ sont les mˆ emes que ceux de A
puisque M µ = X (Λ − µI n ) X
−1 , o` u Λ = diag(λ 1 , . . . , λ n ). Pour cette raison, on
calcule directement le quotient de Rayleigh dans (5.28) `
a partir de la matrice
A (et non `
a partir de M
−1
µ ). La diff´ erence principale par rapport `
a (5.17)
est qu’on doit r´ esoudre ` a chaque it´ eration k un syst` eme lin´ eaire de matrice
M µ = A − µI. D’un point de vue num´ erique, la factorisation LU de M µ est
calcul´ ee une fois pour toute quand k = 1, de mani` ere ` a n’avoir `
a r´ esoudre ` a
chaque it´ eration que deux syst` emes triangulaires, pour un coˆ ut de l’ordre de
n
2 flops.
Bien qu’´ etant plus coˆ uteuse que la m´ ethode de la puissance (5.17), la
m´ ethode de la puissance inverse a l’avantage de pouvoir converger vers n’importe quelle valeur propre de A (la plus proche de µ). Les it´ erations inverses
se prˆ etent donc bien au raffinement de l’approximation µ d’une valeur propre
de A. Cette approximation peut ˆ etre par exemple obtenue en appliquant les
techniques de localisation introduites `
a la Section 5.1. Les it´ erations inverses
peuvent aussi ˆ etre utilis´ ees efficacement pour calculer le vecteur propre associ´ e
` a une valeur propre (approch´ ee) donn´ ee.
En vue de l’analyse de convergence des it´ erations (5.28), supposons A diagonalisable et d´ ecomposons q
(0) sous la forme (5.19). En proc´ edant de la mˆ eme
mani` ere que pour la m´ ethode de la puissance, on a
˜
q
(k) = x m +
n
i=1,i =m
α i
α m
ξ i
ξ m
k
x i ,
o` u les x i sont les vecteurs propres de M
−1
µ (et donc aussi ceux de A), et les
α i sont comme en (5.19). Par cons´ equent, en rappelant la d´ efinition des ξ i et
en utilisant (5.27), on obtient
lim
k→∞
˜
q
(k) = x m ,
lim
k→∞
σ
(k) = λ m .
La convergence sera d’autant plus rapide que µ est proche de λ m . Sous les
mˆ emes hypoth` eses que pour prouver (5.26), on peut obtenir l’estimation a
175
Cela revient `
a supposer que la valeur propre λ m qui est la plus proche de µ a
une multiplicit´ e ´ egale ` a 1. De plus, (5.27) montre que ξ m est la valeur propre
de M
−1
µ de plus grand module ; en particulier, si µ = 0, λ m est la valeur propre
de A de plus petit module.
Etant donn´ e un vecteur initial arbitraire q
(0)
∈ C
n de norme euclidienne
´ egale ` a 1, on construit pour k = 1, 2, . . . la suite d´ efinie par
(A − µI) z
(k) = q
(k−1) ,
q
(k) = z
(k) /z
(k)
2 ,
σ
(k) = (q
(k) )
∗ Aq
(k) .
(5.28)
Remarquer que les vecteurs propres de M µ sont les mˆ emes que ceux de A
puisque M µ = X (Λ − µI n ) X
−1 , o` u Λ = diag(λ 1 , . . . , λ n ). Pour cette raison, on
calcule directement le quotient de Rayleigh dans (5.28) `
a partir de la matrice
A (et non `
a partir de M
−1
µ ). La diff´ erence principale par rapport `
a (5.17)
est qu’on doit r´ esoudre ` a chaque it´ eration k un syst` eme lin´ eaire de matrice
M µ = A − µI. D’un point de vue num´ erique, la factorisation LU de M µ est
calcul´ ee une fois pour toute quand k = 1, de mani` ere ` a n’avoir `
a r´ esoudre ` a
chaque it´ eration que deux syst` emes triangulaires, pour un coˆ ut de l’ordre de
n
2 flops.
Bien qu’´ etant plus coˆ uteuse que la m´ ethode de la puissance (5.17), la
m´ ethode de la puissance inverse a l’avantage de pouvoir converger vers n’importe quelle valeur propre de A (la plus proche de µ). Les it´ erations inverses
se prˆ etent donc bien au raffinement de l’approximation µ d’une valeur propre
de A. Cette approximation peut ˆ etre par exemple obtenue en appliquant les
techniques de localisation introduites `
a la Section 5.1. Les it´ erations inverses
peuvent aussi ˆ etre utilis´ ees efficacement pour calculer le vecteur propre associ´ e
` a une valeur propre (approch´ ee) donn´ ee.
En vue de l’analyse de convergence des it´ erations (5.28), supposons A diagonalisable et d´ ecomposons q
(0) sous la forme (5.19). En proc´ edant de la mˆ eme
mani` ere que pour la m´ ethode de la puissance, on a
˜
q
(k) = x m +
n
i=1,i =m
α i
α m
ξ i
ξ m
k
x i ,
o` u les x i sont les vecteurs propres de M
−1
µ (et donc aussi ceux de A), et les
α i sont comme en (5.19). Par cons´ equent, en rappelant la d´ efinition des ξ i et
en utilisant (5.27), on obtient
lim
k→∞
˜
q
(k) = x m ,
lim
k→∞
σ
(k) = λ m .
La convergence sera d’autant plus rapide que µ est proche de λ m . Sous les
mˆ emes hypoth` eses que pour prouver (5.26), on peut obtenir l’estimation a