6.2 Méthode de la puissance
189
Soit A une matrice carrée d’ordre n. Supposons que ses valeurs
propres soient rangées comme suit
|λ 1 | > |λ 2 | ≥ |λ 3 | ≥ . . . ≥ |λ n |.
(6.5)
Remarquer, en particulier, que |λ 1 | est distinct des autres modules des
valeurs propres de A. Notons x 1 un vecteur propre de norme 1 associé à
λ 1 . Si les vecteurs propres de A sont linéairement indépendants, λ 1 et x 1
peuvent être calculés par la méthode itérative suivante, appelée méthode
de la puissance :
étant donné un vecteur initial arbitraire x
(0)
∈ C
n , poser y
(0) =
x
(0) /x
(0)
, puis calculer
pour k = 1, 2, . . .
x
(k) = Ay
(k−1) , y
(k) =
x
(k)
x (k)
, λ
(k) = (y
(k) )
H Ay
(k)
(6.6)
Remarquer qu’on trouve par récurrence que y
(k) = β
(k) A
k
y
(0) où
β
(k) = (Π
k
i=1 x
(i)
)
−1 pour k ≥ 1. La présence des puissances de A
explique le nom de la méthode.
Dans la section suivante, nous verrons que cette méthode consiste
à construire une suite de vecteurs {y
(k)
} de norme 1 qui, quand k →
∞, s’alignent le long de la direction du vecteur propre x 1 . Les erreurs
y
(k)
− x 1 et |λ
(k)
− λ 1 | sont proportionnelles au rapport |λ 2 /λ 1 |
k dans
le cas d’une matrice quelconque. Si A est réelle et symétrique, on peut
même prouver que |λ
(k)
− λ 1 | est en fait proportionnel à |λ 2 /λ 1 |
2k (voir
[GL96, Chapitre 8]). Dans tous les cas, on a λ
(k)
→ λ 1 pour k → ∞.
Une implémentation de la méthode de la puissance est donnée dans
le Programme 6.1. On stoppe l’algorithme à la première itération k pour
laquelle
|λ
(k)
− λ
(k−1)
| < ε|λ
(k)
|,
où ε est une tolérance fixée. Les paramètres d’entrée sont la matrice A,
la tolérance pour le critère d’arrêt tol, le nombre maximal d’itérations
nmax et le vecteur initial x0. Les paramètres de sortie sont la valeur
propre lambda de plus grand module, un vecteur propre associé et le
nombre d’itérations effectuées.
Programme 6.1. eigpower : méthode de la puissance
function [ lambda ,x , iter ]= eigpower (A , tol , nmax , x0)
% EIGPOWER Evalue n u m é riqu eme nt une valeur propre
% d ’ une matrice
% LAMBDA = EIGPOWER ( A) calcule avec la méthode de la
% p u i ssan ce la valeur propre de A de module maximal
189
Soit A une matrice carrée d’ordre n. Supposons que ses valeurs
propres soient rangées comme suit
|λ 1 | > |λ 2 | ≥ |λ 3 | ≥ . . . ≥ |λ n |.
(6.5)
Remarquer, en particulier, que |λ 1 | est distinct des autres modules des
valeurs propres de A. Notons x 1 un vecteur propre de norme 1 associé à
λ 1 . Si les vecteurs propres de A sont linéairement indépendants, λ 1 et x 1
peuvent être calculés par la méthode itérative suivante, appelée méthode
de la puissance :
étant donné un vecteur initial arbitraire x
(0)
∈ C
n , poser y
(0) =
x
(0) /x
(0)
, puis calculer
pour k = 1, 2, . . .
x
(k) = Ay
(k−1) , y
(k) =
x
(k)
x (k)
, λ
(k) = (y
(k) )
H Ay
(k)
(6.6)
Remarquer qu’on trouve par récurrence que y
(k) = β
(k) A
k
y
(0) où
β
(k) = (Π
k
i=1 x
(i)
)
−1 pour k ≥ 1. La présence des puissances de A
explique le nom de la méthode.
Dans la section suivante, nous verrons que cette méthode consiste
à construire une suite de vecteurs {y
(k)
} de norme 1 qui, quand k →
∞, s’alignent le long de la direction du vecteur propre x 1 . Les erreurs
y
(k)
− x 1 et |λ
(k)
− λ 1 | sont proportionnelles au rapport |λ 2 /λ 1 |
k dans
le cas d’une matrice quelconque. Si A est réelle et symétrique, on peut
même prouver que |λ
(k)
− λ 1 | est en fait proportionnel à |λ 2 /λ 1 |
2k (voir
[GL96, Chapitre 8]). Dans tous les cas, on a λ
(k)
→ λ 1 pour k → ∞.
Une implémentation de la méthode de la puissance est donnée dans
le Programme 6.1. On stoppe l’algorithme à la première itération k pour
laquelle
|λ
(k)
− λ
(k−1)
| < ε|λ
(k)
|,
où ε est une tolérance fixée. Les paramètres d’entrée sont la matrice A,
la tolérance pour le critère d’arrêt tol, le nombre maximal d’itérations
nmax et le vecteur initial x0. Les paramètres de sortie sont la valeur
propre lambda de plus grand module, un vecteur propre associé et le
nombre d’itérations effectuées.
Programme 6.1. eigpower : méthode de la puissance
function [ lambda ,x , iter ]= eigpower (A , tol , nmax , x0)
% EIGPOWER Evalue n u m é riqu eme nt une valeur propre
% d ’ une matrice
% LAMBDA = EIGPOWER ( A) calcule avec la méthode de la
% p u i ssan ce la valeur propre de A de module maximal