Méthode de la puissance itérée

En mathématiques, la méthode de la puissance itérée ou méthode des puissances est un algorithme pour calculer la valeur propre dominante d'une matrice. Bien que cet algorithme soit simple à mettre en œuvre et populaire, il ne converge pas très vite.

Calcul de valeurs propres

Étant donné une matrice A, on cherche une valeur propre de plus grand module et un vecteur propre associé. Le calcul de valeurs propres n'est en général pas possible directement (par une expression analytique) : on utilise alors des méthodes itératives, et la méthode des puissances est la plus simple d'entre elles.

Algorithme

La méthode repose sur le théorème suivant, s'appuyant sur la réduction de Jordan.

Théorème — Soit A une matrice carrée d'ordre n et (λ₁,λ₂,...,λ_n) ses valeurs propres. On suppose :

$|\lambda _{1}|>\max \left(|\lambda _{2}|,...,|\lambda _{n}|\right).$

On considère la somme directe ℂ_n=E⊕F où E est le sous-espace caractéristique de A associé à la valeur propre λ₁, et F est le sous-espace caractéristique de A associé aux autres valeurs propres.

Alors si w⁽⁰⁾∉F, la suite de vecteurs (w⁽ⁿ⁾) définie par la relation de récurrence

$\forall n\in \mathbb {N} ,\ w^{(n+1)}={\frac {1}{||Aw^{(n)}||}}Aw^{(n)}$

vérifie

• w⁽ⁿ⁾≠0 pour tout n∈ℕ.
• $||Aw^{(n)}||\longrightarrow |\lambda _{1}|$ lorsque n→∞.
• $\left({\frac {\overline {\lambda _{1}}}{|\lambda _{1}|}}\right)^{n}w^{(n)}\longrightarrow v$ lorsque n→∞, où v est un vecteur unitaire de A associé à la valeur propre λ₁.
• Si j est une composante non nulle du vecteur v, alors ${\frac {(Aw^{(n)})_{j}}{w_{j}^{(n)}}}\longrightarrow \lambda _{1}$ lorsque n→∞.

Convergence

Lorsque les multiplicités algébriques et géométriques associées à la valeur propre λ₁ sont égales, le taux de convergence de l'algorithme se comporte en $O\left(|\lambda _{2}/\lambda _{1}|^{n}\right)$, où λ₁ et λ₂ sont la plus grande et la seconde plus grande valeurs propres (en valeur absolue). La convergence est bien plus lente dans le cas contraire, et se comporte comme $O\left(1/n\right)$ en général.

Historique

Cette méthode numérique a été imaginée par l'ingénieur italien L. Vianello pour le calcul de la charge critique de flambement des treillis élastiques en évitant de former le déterminant séculaire. A. Stodola s'en est servi dans son traité sur les turbines pour calculer les premières fréquences propres des arbres des machines tournantes.

Cet algorithme est utilisé dans les contextes où le fait de n'utiliser la matrice qu'à travers des produits est un avantage, par exemple pour les très grandes matrices utilisées dans PageRank.

Autres méthodes

Parmi les autres méthodes de calcul de valeurs propres, on compte la méthode de la puissance inverse, l'algorithme de Lanczos, l'itération de Rayleigh, la méthode de Givens, LOBPCG et l'algorithme QR (en) (basé sur la décomposition QR).