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. Modèle:Théorème

Convergence

Lorsque les multiplicités algébriques et géométriques associées à la valeur propre λModèle:Ind sont égales, le taux de convergence de l'algorithme se comporte en $O(|{\lambda }_2/{\lambda }_1{|}^n)$, où λModèle:Ind et λModèle:Ind 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(1/n)$ 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 peu denses 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'Modèle:Lien (basé sur la décomposition QR).