Utilisateur:CetaGM/Brouillon2

En algèbre linéaire, l’algorithme de Lanczos (ou méthode de Lanczos) est un algorithme itératif de tridiagonalisation d'une matrice symétrique. Il est très efficace dans le cas de matrices creuses. Il est principalement utilisé pour déterminer les valeurs et vecteurs propres d'une matrice hermitienne. Par extension, il est aussi très utilisé pour la décomposition en valeurs singulières d'une matrice rectangulaire.

Cet algorithme n'a pas de lien avec le fenêtrage de Lanczos (utilisé par exemple pour le redimensionnement d'images), si ce n'est que tous les deux tirent leur nom du même inventeur, le physicien et mathématicien hongrois Cornelius Lanczos.

Description de l'algorithme

Principe général

L'algorithme de Lanczos prend en entrée une matrice symétrique $A$ et un vecteur initial $q$. Il réalise une tridiagonalisation de $A$ de sorte que

$A=QTQ^{*}$

où $Q$ est une matrice orthogonale et $T$ est une matrice tridiagonale symétrique :

$T={\begin{pmatrix}\alpha _{1}&\beta _{1}&&&&\\\beta _{1}&\ddots &\ddots &&0&\\&\ddots &\ddots &\ddots &&\\&&\ddots &\ddots &\ddots &\\&0&&\ddots &\ddots &\beta _{n-1}\\&&&&\beta _{n-1}&\alpha _{n}\end{pmatrix}}$ et $Q={\begin{pmatrix}\vdots &\vdots &&\vdots \\q_{1}&q_{2}&\cdots &q_{n}\\\vdots &\vdots &&\vdots \end{pmatrix}}$

Pour tout $\lambda$ valeur propre de $T$ et $v$ vecteur propre associé, $\lambda$ est aussi valeur propre de $A$ et $Qv$ est vecteur propre associé.

De plus, si on prend la tridiagonalisation partielle :

$T_{k}={\begin{pmatrix}\alpha _{1}&\beta _{1}&&&&\\\beta _{1}&\ddots &\ddots &&0&\\&\ddots &\ddots &\ddots &&\\&&\ddots &\ddots &\ddots &\\&0&&\ddots &\ddots &\beta _{k-1}\\&&&&\beta _{k-1}&\alpha _{k}\end{pmatrix}}$ et $Q_{k}={\begin{pmatrix}\vdots &\vdots &&\vdots \\q_{1}&q_{2}&\cdots &q_{k}\\\vdots &\vdots &&\vdots \end{pmatrix}}$

alors les valeurs propres extrémales (les plus grandes et les plus petites) $\lambda$ des $T_{k}$ convergent très vite vers les valeurs propres extrémales de $A$ et si $v$ est le vecteur propre associé à l'une de ces valeurs propre de $T_{k}$, alors $Qv$ converge vers le vecteur propre de $A$ associé à la même valeur propre.

Exécution de l'algorithme

En transformant $A=QTQ^{*}$ en $AQ=QT$, on voit que

$\forall i,Aq_{i}=\beta _{i-1}q_{i-1}+\alpha _{i}q_{i}+\beta _{i}q_{i+1}$

(Il faut considérer que $\beta _{0}q_{0}$ et $beta_{n}q_{n+1}$ sont égaux au vecteur nul, pour gérer les cas aux bords).

Sachant que les $q_{i}$ sont orthogonaux entre eux et de norme 1 (car $Q$ est une matrice orthogonale), alors

$\forall i,{\begin{cases}\alpha _{i}=q_{i}^{*}Aq_{i}\\\beta _{i}q_{i+1}=Aq_{i}-\beta _{i-1}q_{i-1}-\alpha _{i}q_{i}\end{cases}}$

L'algorithme est alors :

Entrées : $A$ la matrice à tridiagonaliser, $q$ le vecteur initial, $k_{max}$ le nombre d'itérations maximum souhaité

$r_{0}=q$, $k=1$, $\beta _{0}=||r_{0}||_{2}$
Tant que $k\leq k_{max}$ et $\beta _{k-1}>0$ :
    $q_{i}={\frac {1}{\beta _{i-1}}}r_{i-1}$
    $\alpha _{i}=q_{i}^{*}Aq_{i}$
    $r_{i}=Aq_{i}-\beta _{i-1}q_{i-1}-\alpha _{i}q_{i}$
    $\beta _{i}=||r_{i}||_{2}$
    $k=k+1$

Si on recherche les valeurs et vecteurs propres, il est alors possible d'utiliser un algorithme de décomposition en valeurs propres adapté aux matrices tridiagonales symétriques, par exemple l'algorithme diviser-pour-régner (en), pour trouver la décomposition de $T_{k}$ et en déduire les valeurs et vecteurs propres extrémaux de $A$

Théorie

Les vecteurs $q_{1},q_{2},\dots ,q_{k}$ qui composent la matrice $Q_{k}$ forment une base orthonormale du sous-espace de Krylov d'ordre k associé à $A$ et $q$.

Convergence vers les valeurs propres

À toute étape $k$, la plus grande valeur propre de $T_{k}$ est égale au maximum du quotient de Rayleigh de $A$ sur le sous-espace de Krylov d'ordre $k$, et elle est donc plus petite que la plus grande valeur propre de $A$. De plus, la plus grande valeur propre est croissante d'une étape sur l'autre. Le même raisonnement peut être fait pour la plus petite valeur propre.

Démonstration

Notons que la plus grande et la plus petite valeur propre de la matrice hermitienne $A$ sont le maximum et le minimum du quotient de Rayleigh sur $\mathbb {R} ^{n}$.

Par construction, on a $Q_{k}T_{k}=AQ_{k}+r_{k}e_{k}$ (où $e_{k}$ est le $k$^ième vecteur de la base canonique). On a alors. $T_{k}=Q_{k}^{*}AQ_{k}+Q_{k}^{*}r_{k}e_{k}$. Mais $Q_{k}^{*}r_{k}=Q_{k}^{*}Aq_{k}-\beta _{k-1}Q^{*}q_{k}-\alpha _{k}q_{k}$, et par définition, $Q_{k}^{*}Aq_{k}={\begin{pmatrix}0\\\vdots \\0\\\beta _{k-1}\\\alpha _{k}\end{pmatrix}}$. Ainsi, $Q_{k}^{*}r_{k}$ est le vecteur nul et $T_{k}=Q_{k}^{*}AQ_{k}$.

Donc pour tout vecteur $x$, le quotient de Rayleigh est $R(T_{k},x)={\frac {x^{*}Q_{k}^{*}AQ_{k}x}{x^{*}x}}={\frac {x^{*}Q_{k}^{*}AQ_{k}x}{x^{*}Q_{k}^{*}Q_{k}x}}=R(A,Q_{k}x)$. Donc les plus grandes et les plus petites valeurs propre de $T_{k}$ et leur vecteur propres associés sont les maxima et minima du quotient de Rayleigh de A dans le sous-espace de Krylov d'ordre $k$, ${\mathcal {K}}_{k}(A,q)$.

Le gradient de $R(A,x)$ est $\nabla R(A,x)={\frac {2}{x^{*}x}}(Ax-R(A,x)x)$ donc pour tout point $x$ du sous-espace de Krylov d'ordre k, le gradient $\nabla R(A,x)$ est dans le sous-espace de Krylov d'ordre k+1.

Nommons $\lambda _{1},\lambda _{2},\dots \lambda _{n}$ les valeurs propres de $A$ en ordre décroissant, et $u_{1},u_{2},\dots u_{n}$ les vecteurs propres associés. Notons aussi $\theta _{1},\theta _{2},\dots \theta _{k}$ les valeurs propres décroissantes de la matrice $T_{k}$. On a alors le théorème suivant :

Théorème de convergence de Kaniel-Page — 

$\lambda _{1}\geq \theta _{1}\geq \lambda _{1}-{\frac {(\lambda _{1}-\lambda _{n})\tan(\phi _{1})^{2}}{(c_{k-1}(1+2\rho _{1}))^{2}}}$ et $\lambda _{n}\leq \theta _{k}\leq \lambda _{n}-{\frac {(\lambda _{1}-\lambda _{n})\tan(\phi _{n})^{2}}{(c_{k-1}(1+2\rho _{n}))^{2}}}$

où $\cos(\phi _{i}){=}|qu_{i}|$, $\rho _{1}{=}(\lambda _{1}-\lambda _{2})/(\lambda _{2}-\lambda _{n})$, $\rho _{n}{=}(\lambda _{n-1}-\lambda _{n})/(\lambda _{1}-\lambda _{n-1})$ et $c_{i}$ est le polynôme de Tchebychev de degré $i$

Démonstration du théorème de convergence de Kaniel-Page

Le sous-espace de Krylov d'ordre $k$ associé à A et q est engendré par les vecteurs $q,Aq,A^{2}q,\dots A^{k-1}q$. On peut donc reformuler le quotient de Rayleigh à l'étape $k$ par $\theta _{1}=\max _{p\in {\mathcal {P}}_{k-1}}{\frac {q^{*}p(A)Ap(A)q}{q^{*}p(A)^{2}q}}$, où ${\mathcal {P}}_{k-1}$ est l'ensemble des polynômes de degrés inférieur ou égal à $k-1$.

Notons $A=U\Lambda U^{*}$ la décomposition en valeurs singulières de $A$. $A$ étant une matrice hermitienne, les vecteurs singuliers à droite et à gauche sont identiques et correspondent aux vecteurs propres de $A$, les valeurs singulières étant les valeurs propres.

On a alors $\forall i\in \mathbb {N} ,A^{i}=U\Lambda ^{i}U^{*}$. Soit $d=U^{*}q$, on a alors $\theta _{1}=\max _{p\in {\mathcal {P}}_{k-1}}{\frac {d^{*}p(\Lambda )\Lambda p(\Lambda )d}{d^{*}p(\Lambda )^{2}d}}=\max _{p\in {\mathcal {P}}_{k-1}}{\frac {\sum _{i=1}^{n}d_{i}^{2}p(\lambda _{i})^{2}\lambda _{i}}{\sum _{i=1}^{n}d_{i}^{2}p(\lambda _{i})^{2}}}$

${\begin{array}{ll}{\frac {\sum _{i=1}^{n}d_{i}^{2}p(\lambda _{i})^{2}\lambda _{i}}{\sum _{i=1}^{n}d_{i}^{2}p(\lambda _{i})^{2}}}&\geq {\frac {\lambda _{1}d_{1}^{2}p(\lambda _{1})^{2}+\sum _{i=2}^{n}d_{i}^{2}p(\lambda _{i})^{2}(\lambda _{n}+\lambda _{1}-\lambda _{1})}{\sum _{i=1}^{n}d_{i}^{2}p(\lambda _{i})^{2}}}\\&\geq {\frac {(\lambda _{1}d_{1}^{2}p(\lambda _{1})^{2}+\sum _{i=2}^{n}d_{i}^{2}p(\lambda _{i})^{2}\lambda _{1})+\sum _{i=2}^{n}d_{i}^{2}p(\lambda _{i})^{2}(\lambda _{n}-\lambda _{1})}{\sum _{i=1}^{n}d_{i}^{2}p(\lambda _{i})^{2}}}\\&\geq \lambda _{1}-(\lambda _{1}-\lambda _{n}){\frac {\sum _{i=2}^{n}d_{i}^{2}p(\lambda _{i})^{2}}{\sum _{i=1}^{n}d_{i}^{2}p(\lambda _{i})^{2}}}\end{array}}$

$\theta _{1}$ est donc supérieur à cette valeur pour tout polynôme $p$ de degré au plus $k+1$. Cependant, un choix opportun est un polynôme qui est grand pour $\lambda _{1}$ et petit pour les autres valeurs propres, tel qu'un polynome de Tchebychev. Pour avoir la propriété souhaitée, on fixe $p(x)=c_{k-1}{\Big (}-1+2{\frac {x-\lambda _{n}}{\lambda _{2}-\lambda _{n}}}{\Big )}$.

On a alors $\forall i\geq 2,|p(\lambda _{i})|\leq 1$ et $p(\lambda _{n})=c_{k-1}(1+2\rho _{1})$

Donc $\sum _{i=2}^{n}d_{i}^{2}p(\lambda _{i})\leq \sum _{i=2}^{n}d_{i}^{2}$. On suppose que $||q||_{2}=1$ (on peut le supposer car $q$ est normalisé au début de l’exécution). Alors $\sum _{i=2}^{n}d_{i}^{2}=1-d_{1}^{2}$.

On a donc $\theta _{1}\geq \lambda _{1}-(\lambda _{1}-\lambda _{n}){\frac {1-d_{i}^{2}}{d_{1}^{2}c_{k-1}(1+2\rho _{1})+\sum _{i=2}^{n}d_{i}^{2}p(\lambda _{i})^{2}}}\geq \lambda _{1}-(\lambda _{1}-\lambda _{n}){\frac {1-d_{i}^{2}}{d_{1}^{2}c_{k-1}(1+2\rho _{1})}}$

De plus, puisque $U$ est une matrice orthogonale, alors $U^{*}u_{1}=e_{1}$ (le premier vecteur de la base canonique de $\mathbb {R} ^{n}$). Donc $d_{1}=e_{1}^{*}d=e_{1}^{*}UU^{*}d=u_{1}^{*}q=u_{1}\cdot q=\cos(\phi _{1})$. On a donc ${\frac {1-d_{1}^{2}}{d_{1}^{2}}}={\frac {\sin(\phi _{1})^{2}}{\cos(\phi _{1})^{2}}}=\tan(\phi _{1})^{2}$, ce qui conclut la preuve pour $\theta _{1}$.

La preuve pour $theta_{k}$ peut être obtenue de la même façon, en remplaçant $A$ par $-A$ dans la preuve.

Complexité

On suppose que la matrice $A$ comporte $l$ éléments non-nuls, avec $l>n$. Alors l'opération la plus coûteuse de l'exécution est la multiplication $Aq_{i}$ qui a un coût asymptotique de ${\mathcal {O}}(l)$. La complexité temporelle de l'algorithme est alors ${\mathcal {O}}(lk_{max})$

De plus, les seules données à stocker sont les vecteurs $q_{i}$ et les valeurs $\alpha _{i}$ et $\beta _{i}$. La complexité spatiale est donc de ${\mathcal {O}}(nk_{max})$

Comparaison avec la méthode de la puissance itérée

La méthode de la puissance itérée recherche le vecteur propre associé à la plus grande valeur propre en multipliant itérativement le vecteur initial $q$ par la matrice $A$. On peut donc considérer qu'à une étape $k$, la méthode consiste à rechercher le vecteur associé à la plus grande valeur propre dans l'espace vectoriel de dimension $1$ engendré par le vecteur $A^{k}q$.

L'algorithme de Lanczos améliore ce processus en recherchant, à une étape $k$, le vecteur associé à la plus grande valeur propre dans l'espace vectoriel de dimension $k$ engendré par l'ensemble des vecteurs des itérations précédentes, c'est à dire les vecteurs $q,Aq,A^{2}q,\dots A^{k-1}q$.

Avantages et inconvénients

L'opération la plus coûteuse effectuée par l'algorithme de Lanczos est la multiplication d'un vecteur par la matrice $A$. Lorsque $A$ est une matrice creuse, l'algorithme est donc très efficace par rapport aux autres algorithmes de tridiagonalisation tel que les transformations de Householder. Il est même possible de calculer les valeurs propres d'une matrice $A$ qui n'est pas connue explicitement, mais telle qu'on dispose d'une fonction $f$ telle que $\forall v\in \mathbb {R} ^{n},f(v)=Av$.

Dans le cadre de la recherche de valeurs propres, c'est également un des rares algorithmes de recherche de valeur propre qui permettent de trouver les plus petites valeurs propres d'une matrice hermitienne sans réaliser sa décomposition complète.

Par contre, l'algorithme n'est pas stable numériquement. En effet, même si les calculs donnent des résultat de la meilleur précision possible, il reste un résidu d'erreur. Lorsque les coefficients $\beta _{i}$ sont petits, cela condition à une perte de l'orthogonalité de la matrice $Q$, ce qui complique grandement la déduction des vecteurs propres de $A$ à partir de ceux de $T$. Plusieurs méthodes existent pour pallier ce problème, telles que l'orthogonalisation de chaque nouveau vecteur $q_{i}$ par rapport à l'ensemble des vecteurs déjà calculés, ou encore l'orthogonalisation de $q$ à la fin de l'exécution de l'algorithme.

Applications

Recherche de valeurs singulières

Soit un matrice $B$. Si $\sigma$ est une valeur singulière de $B$ et $v$ le vecteur singulier associé à droite, alors $\sigma ^{2}$ est une valeur propre de $B^{*}B$ et $v$ est le vecteur propre associé. Il est donc possible de réaliser une décomposition en valeurs propres de $B^{*}B$, et d'en déduire la décomposition en valeurs singulières de $B$

Applications pratiques

L'algorithme de Lanczos est particulièrement pratique pour déterminer la décomposition de très grandes matrices creuses, en météorologie ou en traitement des langues naturelles, où ces matrices peuvent compter des centaines de milliers de termes.

Variantes

L'algorithme de Lanczos se généralise en l'algorithme d'Arnoldialgorithme d'Arnoldi pour les matrices non symétriques.

Une variante de cet algorithme est utilisée pour la résolution de systèmes linéaires (en particulier pour les systèmes linéaires creux) et la recherche d'éléments du noyau d'une matrice. Sous cette forme, il est fréquemment utilisé dans le cadre d'algorithmes comme le crible quadratique ou le crible algébrique pour la factorisation d'entiers ou la méthode de l'index pour le problème du logarithme discret. Il est apparenté à la méthode du gradient conjugué.

Voir aussi

Articles connexes

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

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

Liens externes

• (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|mathématiques|informatique théorique}} [[Catégorie:Algorithme|Lanczos]] [[Catégorie:Matrice]]