174
5 Approximation des valeurs propres et des vecteurs propres
o` u cos(θ 0 ) = |x
T
1 q
(0)
| = 0. L’in´ egalit´ e (5.23) montre que la convergence de
la suite ν
(k) vers λ 1 est quadratique par rapport `
a |λ 2 /λ 1 | (voir Section 5.3.3
pour des r´ esultats num´ eriques).
Nous concluons cette section en proposant un crit` ere d’arrˆ et pour les it´ erations (5.17). Introduisons pour cela le r´ esidu `
a l’´ etape k
r
(k) = Aq
(k)
− ν
(k) q
(k) ,
k≥ 1,
et, pour ε > 0, la matrice εE
(k) = −r
(k)
q
(k)
∗ ∈ C
n×n avec E
(k)
2 = 1.
Puisque
εE
(k) q
(k) = −r
(k) ,
k≥ 1,
(5.24)
on obtient
A + εE
(k)
q
(k) = ν
(k) q
(k) . Ainsi, `
a chaque ´ etape de la m´ ethode
de la puissance ν
(k) est une valeur propre de la matrice perturb´ ee A + εE
(k) .
D’apr` es (5.24) et (1.20), ε = r
(k)
2 pour k = 1, 2, . . .. En utilisant cette
identit´ e dans (5.10) et en approchant la d´ eriv´ ee partielle dans (5.10) par le
quotient |λ 1 − ν
(k)
|/ε, on obtient
|λ 1 − ν
(k)
| |
(k)
2
| cos(θ λ )|
,
k ≥ 1,
(5.25)
o` u θ λ est l’angle entre les vecteurs propres ` a droite et `
a gauche, x 1 et y 1 ,
associ´ es ` a λ 1 . Remarquer que si A est hermitienne, alors cos(θ λ ) = 1 et (5.25)
conduit `
a une estimation analogue `
a (5.13).
En pratique, pour pouvoir utiliser les estimations (5.25), il est n´ ecessaire
de remplacer ` a chaque ´ etape | cos(θ λ )| par le module du produit scalaire des
deux approximations q
(k) et w
(k) de x 1 et y 1 calcul´ ees par la m´ ethode de la
puissance. On obtient alors l’estimation a posteriori suivante
|λ 1 − ν
(k)
| |
(k)
2
|(w (k) ) ∗ q (k) |
,
k≥ 1.
(5.26)
Des exemples d’applications de (5.26) seront donn´ es ` a la Section 5.3.3.
5.3.2 M´ ethode de la puissance inverse
Dans cette section, nous recherchons une approximation de la valeur propre
d’une matrice A ∈ C
n×n la plus proche d’un nombre µ ∈ C donn´ e, avec
µ ∈ σ(A). On peut pour cela appliquer la m´ ethode de la puissance (5.17) `
a
la matrice (M µ )
−1 = (A − µI)
−1 , ce qui conduit `
a la m´ ethode des it´ erations
inverses ou m´ ethode de la puissance inverse. Le nombre µ est appel´ e shift en
anglais.
Les valeurs propres de M
−1
µ sont ξ i = (λ i − µ)
−1 ; supposons qu’il existe
un entier m tel que
|λ m − µ| < |λ i − µ|,
∀i = 1, . . . , n
et i = m.
(5.27)
5 Approximation des valeurs propres et des vecteurs propres
o` u cos(θ 0 ) = |x
T
1 q
(0)
| = 0. L’in´ egalit´ e (5.23) montre que la convergence de
la suite ν
(k) vers λ 1 est quadratique par rapport `
a |λ 2 /λ 1 | (voir Section 5.3.3
pour des r´ esultats num´ eriques).
Nous concluons cette section en proposant un crit` ere d’arrˆ et pour les it´ erations (5.17). Introduisons pour cela le r´ esidu `
a l’´ etape k
r
(k) = Aq
(k)
− ν
(k) q
(k) ,
k≥ 1,
et, pour ε > 0, la matrice εE
(k) = −r
(k)
q
(k)
∗ ∈ C
n×n avec E
(k)
2 = 1.
Puisque
εE
(k) q
(k) = −r
(k) ,
k≥ 1,
(5.24)
on obtient
A + εE
(k)
q
(k) = ν
(k) q
(k) . Ainsi, `
a chaque ´ etape de la m´ ethode
de la puissance ν
(k) est une valeur propre de la matrice perturb´ ee A + εE
(k) .
D’apr` es (5.24) et (1.20), ε = r
(k)
2 pour k = 1, 2, . . .. En utilisant cette
identit´ e dans (5.10) et en approchant la d´ eriv´ ee partielle dans (5.10) par le
quotient |λ 1 − ν
(k)
|/ε, on obtient
|λ 1 − ν
(k)
| |
(k)
2
| cos(θ λ )|
,
k ≥ 1,
(5.25)
o` u θ λ est l’angle entre les vecteurs propres ` a droite et `
a gauche, x 1 et y 1 ,
associ´ es ` a λ 1 . Remarquer que si A est hermitienne, alors cos(θ λ ) = 1 et (5.25)
conduit `
a une estimation analogue `
a (5.13).
En pratique, pour pouvoir utiliser les estimations (5.25), il est n´ ecessaire
de remplacer ` a chaque ´ etape | cos(θ λ )| par le module du produit scalaire des
deux approximations q
(k) et w
(k) de x 1 et y 1 calcul´ ees par la m´ ethode de la
puissance. On obtient alors l’estimation a posteriori suivante
|λ 1 − ν
(k)
| |
(k)
2
|(w (k) ) ∗ q (k) |
,
k≥ 1.
(5.26)
Des exemples d’applications de (5.26) seront donn´ es ` a la Section 5.3.3.
5.3.2 M´ ethode de la puissance inverse
Dans cette section, nous recherchons une approximation de la valeur propre
d’une matrice A ∈ C
n×n la plus proche d’un nombre µ ∈ C donn´ e, avec
µ ∈ σ(A). On peut pour cela appliquer la m´ ethode de la puissance (5.17) `
a
la matrice (M µ )
−1 = (A − µI)
−1 , ce qui conduit `
a la m´ ethode des it´ erations
inverses ou m´ ethode de la puissance inverse. Le nombre µ est appel´ e shift en
anglais.
Les valeurs propres de M
−1
µ sont ξ i = (λ i − µ)
−1 ; supposons qu’il existe
un entier m tel que
|λ m − µ| < |λ i − µ|,
∀i = 1, . . . , n
et i = m.
(5.27)