Algorithme de Faddeev-Le Verrier

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

Présentation du problème

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 $\det(XI_{n}-M)$, est extrêmement lourd sur le plan de la complexité algorithmique : comme il s'agit d'un déterminant, sa définition comme somme de n! termes, où n désigne la taille de la matrice M, est impraticable ; même la méthode du pivot, qui permet de ramener ce calcul à un temps d'ordre O(n³), devient difficile à mettre en œuvre pour des matrices de taille relativement modeste (n de l'ordre de quelques dizaines).

Description de l'algorithme

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 matrices $(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 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}$

Complexité de l'algorithme de Faddeev

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 relativement faciles à calculer, 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 en 1975 ; elle montre que cet algorithme est dans la classe de complexité NC.

Article connexe

Algorithme de Samuelson-Berkowitz (de)