Méthode de la puissance itérée

En mathématiques, la méthode de la puissance itérée[1] 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[2].

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

On considère la somme directen=EFE est le sous-espace caractéristique de A associé à la valeur propre λ1, et F est le sous-espace caractéristique de A associé aux autres valeurs propres.

Alors si w(0)F, la suite de vecteurs (w(n)) définie par la relation de récurrence

vérifie

  • w(n)≠0 pour tout n∈ℕ.
  • lorsque n→∞.
  • lorsque n→∞, où v est un vecteur unitaire de A associé à la valeur propre λ1.
  • Si j est une composante non nulle du vecteur v, alors lorsque n→∞.

Convergence

Lorsque les multiplicités algébriques et géométriques associées à la valeur propre λ1 sont égales, le taux de convergence de l'algorithme se comporte en , où λ1 et λ2 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 en général[2].

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[3] en évitant de former le déterminant séculaire. A. Stodola s'en est servi dans son traité sur les turbines[4] pour calculer les premières fréquences propres des arbres des machines tournantes[5].

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[1].

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)[1].

Notes et références

  1. a b et c Bernard Philippe et Yousef Saad, « Calcul des valeurs propres », sur UMR Irisa.
  2. a et b Denis Serre, Les matrices : théorie et pratique, Paris, Dunod, , 168 p. (ISBN 2-10-005515-1, OCLC 491560333)
  3. « Graphische Untersuchung der Knickfestigkeit gerader Stäbe », Zeitschrift des Vereines deutscher Ingenieure, vol. 42, no 52,‎ , p. 1436–1443.
  4. Die Dampfturbinen und ihre Aussichten als Wärmekraftmaschinen und über die Gasturbine (1903).
  5. Timoshenko, History of strength of materials, McGraw-Hill Book Co., (réimpr. 1983, éd. Dover), 452 p., « Theory of Elasticity during the period 1900-1950 », p. 418