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 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).

[modifier] 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(X I 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_{k-1} - \frac{1}{k} \mathrm{tr}(M_{k-1})I_n \Big)$ pour $1 \leq k \leq n - 1$

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

$P_M = \det (XI_n- M) = X^n - \sum_{k=1}^n \frac{1}{k} \mathrm{tr}(M_{k-1})X^{n-k}$

[modifier] 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 I_n - M) est factorielle.