6.3 Généralisation de la méthode de la puissance
193
pour k = 1, 2, . . .
x
(k) = A
−1
y
(k−1) , y
(k) =
x
(k)
x (k)
, μ
(k) = (y
(k) )
H A
−1
y
(k)
(6.7)
Si les vecteurs propres de A sont linéairement indépendants, et s’il
n’y a qu’une valeur propre λ n de module minimal, alors
lim
k→∞
μ
(k) = 1/λ n ,
i.e. (μ
(k) )
−1 tend vers λ n pour k → ∞.
A chaque étape k, on doit résoudre un système linéaire de la forme
Ax
(k) = y
(k−1) . Il est donc commode d’effectuer une factorisation LU
de A (ou une factorisation de Cholesky si A est symétrique définie positive) une fois pour toute, afin de n’avoir à résoudre que deux systèmes
triangulaires à chaque itération.
Rappelons que la commande lu (MATLAB et Octave) peut également effectuer la décomposition LU pour des matrices complexes.
Une autre généralisation de la méthode de la puissance permet de
calculer une approximation de la valeur propre (inconnue) la plus proche
d’un μ donné (réel ou complexe). Notons λ μ une telle valeur propre et
définissons la matrice translatée A μ = A − μI, dont les valeurs propres
sont λ(A μ ) = λ(A) − μ. Pour approcher λ μ , on peut d’abord estimer
λ min (A μ ), valeur propre de plus petite norme de A μ , en appliquant la
méthode de la puissance inverse à A μ , puis calculer λ μ = λ min (A μ ) + μ.
Cette technique est connue sous le nom de méthode de la puissance avec
décalage ou avec translation (shift en anglais), et le nombre μ est appelé
décalage (ou shift ).
Dans le Programme 6.2, on implémente la méthode de la puissance
inverse avec décalage. Le paramètre d’entrée mu est le décalage, les autres
sont identiques à ceux du Programme 6.1. La méthode de la puissance
inverse (sans décalage) est simplement obtenue en prenant μ = 0. Les
paramètres de sortie sont la valeur propre approchée λ μ de A, un vecteur
propre associé x et le nombre d’itérations effectuées.
Programme 6.2. invshift : méthode de la puissance inverse avec décalage
function [ lambda ,x , iter ]= invshift (A ,mu , tol , nmax , x0 )
% INVSHIFT Evalue n u m é riqu eme nt une valeur propre d ’ une
% matrice
% LAMBDA = INVSHIFT (A ) calcule la valeur propre de A
% de module minimum avec la méthode de la p u i s sanc e
% inverse
% LAMBDA = INVSHIFT (A , MU) calcule la valeur propre de A
% la plus proche d ’ un nombre réel ou complexe MU
% LAMBDA = INVSHIFT (A ,MU , TOL , NMAX , X0 ) utilise une
193
pour k = 1, 2, . . .
x
(k) = A
−1
y
(k−1) , y
(k) =
x
(k)
x (k)
, μ
(k) = (y
(k) )
H A
−1
y
(k)
(6.7)
Si les vecteurs propres de A sont linéairement indépendants, et s’il
n’y a qu’une valeur propre λ n de module minimal, alors
lim
k→∞
μ
(k) = 1/λ n ,
i.e. (μ
(k) )
−1 tend vers λ n pour k → ∞.
A chaque étape k, on doit résoudre un système linéaire de la forme
Ax
(k) = y
(k−1) . Il est donc commode d’effectuer une factorisation LU
de A (ou une factorisation de Cholesky si A est symétrique définie positive) une fois pour toute, afin de n’avoir à résoudre que deux systèmes
triangulaires à chaque itération.
Rappelons que la commande lu (MATLAB et Octave) peut également effectuer la décomposition LU pour des matrices complexes.
Une autre généralisation de la méthode de la puissance permet de
calculer une approximation de la valeur propre (inconnue) la plus proche
d’un μ donné (réel ou complexe). Notons λ μ une telle valeur propre et
définissons la matrice translatée A μ = A − μI, dont les valeurs propres
sont λ(A μ ) = λ(A) − μ. Pour approcher λ μ , on peut d’abord estimer
λ min (A μ ), valeur propre de plus petite norme de A μ , en appliquant la
méthode de la puissance inverse à A μ , puis calculer λ μ = λ min (A μ ) + μ.
Cette technique est connue sous le nom de méthode de la puissance avec
décalage ou avec translation (shift en anglais), et le nombre μ est appelé
décalage (ou shift ).
Dans le Programme 6.2, on implémente la méthode de la puissance
inverse avec décalage. Le paramètre d’entrée mu est le décalage, les autres
sont identiques à ceux du Programme 6.1. La méthode de la puissance
inverse (sans décalage) est simplement obtenue en prenant μ = 0. Les
paramètres de sortie sont la valeur propre approchée λ μ de A, un vecteur
propre associé x et le nombre d’itérations effectuées.
Programme 6.2. invshift : méthode de la puissance inverse avec décalage
function [ lambda ,x , iter ]= invshift (A ,mu , tol , nmax , x0 )
% INVSHIFT Evalue n u m é riqu eme nt une valeur propre d ’ une
% matrice
% LAMBDA = INVSHIFT (A ) calcule la valeur propre de A
% de module minimum avec la méthode de la p u i s sanc e
% inverse
% LAMBDA = INVSHIFT (A , MU) calcule la valeur propre de A
% la plus proche d ’ un nombre réel ou complexe MU
% LAMBDA = INVSHIFT (A ,MU , TOL , NMAX , X0 ) utilise une