- 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
est la suivante : si 
est un vecteur et 
, alors 
.Si
est la décomposition en valeurs propres de , alors 
.Pour des valeurs de
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, 
converge vers la plus grande valeur propre et 
au vecteur propre correspondant.Dans le cas où il y a plusieurs valeurs propres maximales,
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
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
est la seule opération de grande ampleur.Voir aussi
Articles connexes
Références
- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Lanczos algorithm » (voir la liste des auteurs)
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 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.
Wikimedia Foundation. 2010.
