Algorithme de Lanczos

Un article de Wikipédia, l'encyclopédie libre.

Cet article est une ébauche concernant les mathématiques.

Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

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

1 Description de l'algorithme
- 1.1 Méthode naïve
- 1.2 Algorithme de Lanczos
2 Voir aussi

[modifier] Description de l'algorithme

[modifier] 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.

[modifier] 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.