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 (λ1,λ2,...,λn) ses valeurs propres. On suppose :
On considère la somme directe ℂn=E⊕F où E 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
- ↑ a b et c Bernard Philippe et Yousef Saad, « Calcul des valeurs propres », sur UMR Irisa.
- ↑ a et b Denis Serre, Les matrices : théorie et pratique, Paris, Dunod, , 168 p. (ISBN 2-10-005515-1, OCLC 491560333)
- ↑ « Graphische Untersuchung der Knickfestigkeit gerader Stäbe », Zeitschrift des Vereines deutscher Ingenieure, vol. 42, no 52, , p. 1436–1443.
- ↑ Die Dampfturbinen und ihre Aussichten als Wärmekraftmaschinen und über die Gasturbine (1903).
- ↑ 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
Portail des mathématiques
Portail de l'informatique théorique