Algorithme de lanczos

Algorithme de lanczos

Algorithme de Lanczos

En mathématiques, il existe deux algorithmes portant le nom d’algorithme de Lanczos.

En théorie des nombres, l’algorithme de Lanczos est une méthode courante permettant de trouver un vecteur nul en effectuant un crible quadratique ou de factoriser les fractions continues. Il est utilisé dans de nombreux domaines, et se révèle l'une des méthodes les plus efficaces.

En algèbre linéaire, l’algorithme de Lanczos, est une procédure itérative qui permet de trouver les valeurs et vecteurs propres d'une matrice carrée, ou la décomposition en valeurs singulières d'une matrice rectangulaire. Il est particulièrement pratique pour déterminer la décomposition de très grandes matrices, en météorologie ou en traitement des langues naturelles, où les matrices peuvent compter des centaines de milliers de termes.

Tous les deux tirent leur nom du physicien et mathématicien hongrois Cornelius Lanczos.

Sommaire

Description de l'algorithme

Méthode naïve

Une méthode pour trouver la plus grande valeur propre d'une matrice A\, est la suivante : si x_0\, est un vecteur et x_{n+1} = A x_n\,, alors x_n = A^n x_0\,.

Si A = U \operatorname{diag}(\sigma_i) U' \, est la décomposition en valeurs propres de A\,, alors A^n = U \operatorname{diag}(\sigma_i^n) U'.

Pour des valeurs de n\, très grandes, la matrice diagonale des valeurs propres sera dominée par la plus grande d'entre elles - à l'exception du cas où il y a deux plus grandes valeurs égales. Alors, |x_{n+1}| / |x_{n}|\, converge vers la plus grande valeur propre et x_n / |x_n|\, au vecteur propre correspondant.

Dans le cas où il y a plusieurs valeurs propres maximales, x_n \, converge vers un vecteur dans le sous-espace engendré par les vecteurs propres associés à ces valeurs. Après avoir déterminé le premier, on peut successivement restreindre l'algorithme au noyau des vecteurs propres connus pour déterminer les autres.

En pratique, cet algorithme ne fonctionne pas très bien à cause d'erreurs d'arrondi, et d'une vitesse de convergence parfois trop faible.

Algorithme de Lanczos

L'algorithme de Lanczos est une amélioration de la méthode proposée ci-dessus, dans laquelle chaque u\, est restreint à l'orthogonal de toutes les valeurs précédentes. Lors de la construction de ces vecteurs, les constantes de normalisation sont regroupées dans une matrice tridiagonale dont les valeurs propres les plus significatives convergent, rapidement, vers les valeurs propres de la matrice de départ.

L'intérêt de cette méthode est que la multiplication par A\, est la seule opération de grande ampleur.

Voir aussi

Articles connexes

Références

  • (en) Cet article est partiellement ou en totalité issu d’une traduction de l’article de Wikipédia en anglais intitulé « Lanczos algorithm ».

Liens externes

  • (en) Calcul matriciel : explications et preuves ;
  • (en) Analyse des liens, vecteurs propres et stabilité : comparaison des méthodes de classement HITS et PageRank (l’algorithme de Google) et de de leur convergence et la stabilité des vecteurs propres face aux changements des ensembles de liens organisé par les moteurs de recherche, par Andrew Ng et al. ;
  • (en) Méthode de Lanczos, B. A. LaMacchia et A. M. Odlyzko.
  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Algorithme de Lanczos ».

Wikimedia Foundation. 2010.

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

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • Algorithme De Lanczos — En mathématiques, il existe deux algorithmes portant le nom d’algorithme de Lanczos. En théorie des nombres, l’algorithme de Lanczos est une méthode courante permettant de trouver un vecteur nul en effectuant un crible quadratique ou de… …   Wikipédia en Français

  • Algorithme de Lanczos — En mathématiques, il existe deux algorithmes portant le nom d’algorithme de Lanczos. En théorie des nombres, l’algorithme de Lanczos est une méthode courante permettant de trouver un vecteur nul en effectuant un crible quadratique ou de… …   Wikipédia en Français

  • Cornelius Lanczos — ((hu) Lánczos Kornél) (né Kornél Löwy le 2 février 1893 à Székesfehérvár – 25 juin 1974 à Budapest) était un mathématicien et physicien hongrois. Sommaire 1 Biographie 2 Annexes …   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

  • Decomposition en valeurs singulieres — Décomposition en valeurs singulières En mathématiques, le procédé d algèbre linéaire de décomposition en valeurs singulières (ou SVD, de l anglais : Singular Value Decomposition) d une matrice est un outil important de factorisation des… …   Wikipédia en Français

  • Décomposition En Valeurs Singulières — En mathématiques, le procédé d algèbre linéaire de décomposition en valeurs singulières (ou SVD, de l anglais : Singular Value Decomposition) d une matrice est un outil important de factorisation des matrices rectangulaires réelles ou… …   Wikipédia en Français

  • Décomposition en valeurs singulières — En mathématiques, le procédé d algèbre linéaire de décomposition en valeurs singulières (ou SVD, de l anglais : Singular Value Decomposition) d une matrice est un outil important de factorisation des matrices rectangulaires réelles ou… …   Wikipédia en Français

  • Factorisation De Dixon — Pour les articles homonymes, voir Dixon. En arithmétique modulaire, la méthode de factorisation de Dixon (aussi connue comme l algorithme de Dixon) est un algorithme de décomposition en produit de facteurs premiers à but général. Le crible… …   Wikipédia en Français

  • Factorisation de Dixon — Pour les articles homonymes, voir Dixon. En arithmétique modulaire, la méthode de factorisation de Dixon (aussi connue comme l algorithme de Dixon) est un algorithme de décomposition en produit de facteurs premiers à but général. Le crible… …   Wikipédia en Français

Share the article and excerpts

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