Algorithme de Faddeev-Leverrier

Un article de Wikipédia, l'encyclopédie libre.

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 Konstantinovitch Faddeev (ru). Publié pour la première fois par Urbain Le Verrier (1840)[1], il fut redécouvert à de nombreuses reprises : Horst[2] (1935), Souriau (1948), Frame (1949), Faddeev (en) et Sominskii (1949).

Présentation du problème[modifier | modifier le code]

Calculer le polynôme caractéristique d'une matrice carrée M d'ordre n revêt une importance pratique fondamentale, puisque c'est un moyen d'accéder aux valeurs propres de M ou à un polynôme s'annulant en M (théorème de Cayley-Hamilton). Cependant, ce problème est hautement calculatoire, et l'algorithme naïf, qui consisterait à calculer directement le déterminant , 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 ; cependant, la méthode du pivot permet de ramener ce calcul à un temps d'ordre O(n3).

Description de l'algorithme[modifier | modifier le code]

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 .

On définit par récurrence la suite finie de matrices par :

pour

Alors on montre[3] que le polynôme caractéristique de M vaut :

Complexité de l'algorithme de Faddeev[modifier | modifier le code]

Les coefficients du polynôme caractéristique s'expriment en matière 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, et on peut montrer qu'il est plus efficace dans de nombreux cas que le calcul du déterminant par la méthode du pivot. De plus, une implémentation parallèle rapide de l'algorithme de Faddeev a été obtenue par Lazslo Csanky[4] en 1975 ; elle montre que cet algorithme est dans la classe de complexité NC.

Notes et références[modifier | modifier le code]

  1. Urbain Le Verrier, « Sur les variations séculaires des éléments des orbites pour les sept planètes principales », J. de Math., vol. 1, no 5,‎ , p. 230 (lire en ligne) lire en ligne sur Gallica
  2. Cf. (en) Paul Horst, « A method of determining the coefficients of a characteristic equation », Ann. Math. Stat., no 6,‎ , p. 83-84 (DOI 10.1214/aoms/1177732612).
  3. Cf. par exemple (en) A. S. Householder, The Theory of Matrices in Numerical Analysis, Dover et l'article « Identités de Newton ».
  4. (en) L. Csanky, « Fast parallel matrix inversion algorithms », Foundations of Computer Science, 1975.

Article connexe[modifier | modifier le code]

Algorithme de Samuelson-Berkowitz (de)