Algorithme de Lanczos

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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

En théorie des nombres, l’algorithme de Lanczos, méthode courante, permet de trouver un vecteur nul en effectuant un crible quadratique ou de factoriser les fractions continues. Utilisé dans plusieurs[Quoi ?] domaines, il s'y révèle d'une excellente efficacité.

En algèbre linéaire, l’algorithme de Lanczos 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ù ces matrices peuvent compter des centaines de milliers de termes.

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

Description de l'algorithme[modifier | modifier le code]

Méthode naïve[modifier | modifier le code]

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 possède deux inconvénients : une vulnérabilité aux erreurs d'arrondi, et une vitesse de convergence parfois trop faible.

Algorithme de Lanczos[modifier | modifier le code]

L'algorithme de Lanczos améliore la méthode précédente, 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.

La multiplication par A\, est alors la seule opération de grande ampleur, ce qui fait l'intérêt de la méthode.

Usage en informatique[modifier | modifier le code]

L'algorithme de Lanczos a été introduit très rapidement pour traiter les zooms dans des logiciels de traitement d'image comme IrfanView. Fin 2012, il fut incorporé dans LibreOffice 3.6 également pour assurer des changements de taille de bonne qualité, les puissances des machines le permettant sans pénalité excessive.

Références[modifier | modifier le code]

Liens externes[modifier | modifier le code]

  • (en) Andrew Y. Ng, Alice X. Zheng et Michael I. Jordan, « Link Analysis, Eigenvectors and Stability », dans IJCAI-01,‎ 2001 (lire en ligne), p. 903-910 : 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
  • (en) Brian A. LaMacchia et Andrew M. Odlyzko, « Solving Large Sparse Linear Systems over Finite Fields », dans Proceeding CRYPTO '90, p. 109-133, § 3 : Lanczos and conjugate gradient methods