Algorithme de Faddeev

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(XInM) 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 PM.

On définit par récurrence la suite finie de matrice (M_k)_{0 \leq k \leq n - 1} par :

M0 = 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}

Complexité de l'algorithme de Faddeev

Les coefficients du polynôme caractéristique s'expriment en termes 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

  1. Cf. par exemple The Theory of Matrices in Numerical Analysis (éd. Dover) par A. S. Householder.
  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Algorithme de Faddeev-Leverrier ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme de Faddeev de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • 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… …   Wikipédia en Français

  • 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… …   Wikipédia en Français

  • 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… …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • Le Verrier — Urbain Le Verrier Urbain Le Verrier Urbain Jean Joseph Le Verrier (Saint Lô, 11 mars 1811 Paris, 23 septembre 1877) était un astronome et mathématicien français spécialisé en mécanique céleste …   Wikipédia en Français

  • U. J. J. Le Verrier — Urbain Le Verrier Urbain Le Verrier Urbain Jean Joseph Le Verrier (Saint Lô, 11 mars 1811 Paris, 23 septembre 1877) était un astronome et mathématicien français spécialisé en mécanique céleste …   Wikipédia en Français

  • Urbain J. J. Le Verrier — Urbain Le Verrier Urbain Le Verrier Urbain Jean Joseph Le Verrier (Saint Lô, 11 mars 1811 Paris, 23 septembre 1877) était un astronome et mathématicien français spécialisé en mécanique céleste …   Wikipédia en Français

  • Urbain Jean Joseph Le Verrier — Urbain Le Verrier Urbain Le Verrier Urbain Jean Joseph Le Verrier (Saint Lô, 11 mars 1811 Paris, 23 septembre 1877) était un astronome et mathématicien français spécialisé en mécanique céleste …   Wikipédia en Français

  • Urbain Le Verrier — Naissance 11 mars 1811 Saint Lô ( …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”