Algorithme de Faddeev-Leverrier

Infos
L' algorithme de Faddeev-Leverrier est une méthode permettant de calculer le polynôme caractéristique d'une matrice. Il porte le nom du mathématicien russe Dmitrii Konstantinovich Faddeev. Publié pour la première fois par Urbain Jean Joseph Le Verrier (1840), il fut re-découvert à de nombreuses reprises : Horst (1935), Souriau (1948), Frame (1949), Faddeev et Sorminskii (1949).
Algorithme de Faddeev-Leverrier

L' algorithme de Faddeev-Leverrier est une méthode permettant de calculer le polynôme caractéristique d'une matrice. Il porte le nom du mathématicien russe Dmitrii Konstantinovich Faddeev. Publié pour la première fois par Urbain Jean Joseph Le Verrier (1840), il fut re-découvert à de nombreuses reprises : Horst (1935), Souriau (1948), Frame (1949), Faddeev et Sorminskii (1949).

Présentation

Calculer le polynôme caractéristique d'une matrice carré M d'ordre n revêt une importance pratique fondamentale, puisque c'est un moyen d'accéder aux valeurs propres de M. Cependant, ce problème est hautement calculatoire, et l'algorithme naïf, qui consisterait à calculer directement le déterminant \det (XI_n - M) est extrêmement lourd sur le plan de la complexité algorithmique : il s'agit d'un déterminant, qui s'écrit comme somme de n! termes, où n désigne la taille de la matrice M. L'algorithme de Faddeev s'inscrit dans une démarche d'efficacité. Partons de la matrice M, dont on cherche le polynôme caractéristique P_M. On définit par récurrence la suite finie de matrice (M_k)_0 \leq k \leq n - 1 par : :: M_0 = M :: M_k = M \Big( M_ - \frac \mathrm(M_)I_n \Big) pour 1 \leq k \leq n - 1 Alors on montreCf. par exemple The Theory of Matrices in Numerical Analysis (éd. Dover) par A. S. Householder. que le polynôme caractéristique de M vaut : :: P_M = \det (XI_n- M) = X^n - \sum_^n \frac \mathrm(M_)X^

Complexité de l'algorithme de Faddeev

Les coefficients du polynôme caractéristique s'expriment en terme de traces, de produits et de somme de matrices, ce qui les rend facilement calculables, tout du moins pour une machine. La complexité de l'algorithme de Faddeev est polynomiale, tandis que la complexité de l'algorithme naïf (calcul direct du déterminant de X In - M) est factorielle.

Notes

Catégorie:Algèbre linéaire
Sujets connexes
Complexité algorithmique   Déterminant   Jean-Marie Souriau   Matrice (mathématiques)   Polynôme caractéristique   Valeur propre  
#
Accident de Beaune   Amélie Mauresmo   Anisocytose   C3H6O   CA Paris   Carole Richert   Catherinettes   Chaleur massique   Championnat de Tunisie de football D2   Classement mondial des entreprises leader par secteur   Col du Bonhomme (Vosges)   De viris illustribus (Lhomond)   Dolcett   EGP  
^