Algorithme de Lanczos

La méthode de la puissance itérée pour trouver la plus grande valeur propre d'une matrice carrée symétrique ${\displaystyle A\,}$ d'ordre p est la suivante.

Si ${\displaystyle x_{0}}$ est un vecteur et ${\displaystyle x_{n+1}=Ax_{n}}$, alors ${\displaystyle x_{n}=A^{n}x_{0}}$.

On sait qu'une matrice symétrique est diagonalisable[1]^,[2], et les termes ${\displaystyle \sigma _{i},i=1...p}$ de la matrice diagonale sont les valeurs propres de la matrice. Soit donc

${\displaystyle A=U\cdot {\begin{pmatrix}\sigma _{1}&&&&&0\\&\ddots &&&&\\&&\sigma _{i}&&&\\&&&\ddots &&\\&&\vdots &&\ddots &\\0&&&&&\sigma _{p}\\\end{pmatrix}}\cdot U'=U\cdot \operatorname {diag} (\sigma _{i})\cdot U'}$

la décomposition en valeurs propres de ${\displaystyle A}$, où U est une matrice orthogonale ; alors

${\displaystyle A^{n}=U\operatorname {diag} (\sigma _{i}^{n})U'}$

Pour des valeurs de ${\displaystyle 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 : en effet, soit ${\displaystyle \sigma _{max}}$ la valeur propre de plus grand module.

${\displaystyle \lim _{n\rightarrow \infty }A^{n}=\lim _{n\rightarrow \infty }|\sigma _{max}|^{n}\cdot U\operatorname {diag} ({\frac {\sigma _{i}^{n}}{|\sigma _{max}|^{n}}})U'=U\operatorname {diag} (0...0,\left({\frac {\sigma _{max}}{|\sigma _{max}|}}\right)^{n},0...0)U'}$

Alors, ${\displaystyle |x_{n+1}|/|x_{n}|}$ converge vers la plus grande valeur propre et ${\displaystyle x_{n}/|x_{n}|}$ au vecteur propre correspondant.

Dans le cas où il y a plusieurs valeurs propres maximales, ${\displaystyle 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.

L'algorithme de Lanczos améliore la méthode précédente, dans laquelle chaque ${\displaystyle 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 ${\displaystyle A}$ est alors la seule opération de grande ampleur, ce qui fait l'intérêt de la méthode.

• Algorithme de recherche de valeur propre
• Méthode du gradient conjugué
• Méthode du gradient biconjugué
• Élimination de Gauss-Jordan

• (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).
• (en) Gene H. Golub et Charles F. Van Loan (en), Matrix Computations, JHU Press, 1996, 694 p. (ISBN 978-0-8018-5414-9, présentation en ligne)

• (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

• Portail des mathématiques
• Portail de l'informatique théorique