dimanche 31 mai 2015

Valeurs et vecteurs propres par la méthode QR

Calculer les valeurs/vecteurs propres d'une matrice est un des problèmes les plus importants en mathématiques, il possède des applications dans de nombreux problème de physique aussi bien qu'en informatique (comme le calcul du PageRank !). La méthode classique du calcul exact des valeurs/vecteurs propres utilisant  le calcul du polynôme caractéristique est en pratique inutilisable dès que la taille des matrices augmente,  dans ce cas on doit se tourner vers des méthodes itérative  qui ne calculent qu'une approximation des valeurs/vecteurs propres. Parmi ces méthodes l'une des plus efficaces  est la méthode QR .  Son implémentation est très simple, à tel point que son  fonctionnement peut paraître relever de la magie ! C'est  typiquement le genre de résultat mathématique où une visualisation "dynamique"  de l'algorithme peut permettre de mieux en comprendre les mécanismes.  
Méthode QR appliquée à une matrice 10x10
Pour comprendre ce que  cette animation permet de visualiser il faut d'abord  expliquer l'algorithme de la méthode QR :
$\epsilon=$ seuil de précision
A_0=A (matrice réelle de taille nxn)
$\tilde{Q}_0=Id_n$
tant que $\max_{i>j}|(A_n)_{i,j}|>\epsilon $
              calculer la décomposition QR de $A_n$ : $A_{n}=Q_nR_n$
              puis calculer $A_{n+1}=R_nQ_n$
              $\tilde{Q}_{n+1}=Q_n\tilde{Q}_n$
Pour obtenir l'animation on affiche à chaque étape  la matrice $A_n$  comme  si c'était une image :
  • chaque case (i,j) de la matrice A correspond à un pixel  de l'image en position i-ième ligne j-ième colonne
  • le pixel (i,j) est colorié avec une palette de couleurs en fonction de la valeur  de $\vert A_{i,j}\vert $  donnée par l'échelle à droite  (de 0 pour le noir-bleu  à plus de 100  pour le rouge-blanc)
On voit bien sur l'animation que tous les coefficients  de la matrice $A_n$ qui sont  "sous" la diagonale tendent vers 0 assez rapidement  : c'est la clé du fonctionnement de cet algorithme.  La démonstration de ce résultat  est en général très compliquée et il faut au préalable rappeler  ce qu'est la décomposition QR  d'une matrice :
théorème (décomposition QR)  
Soit $A$ une matrice à coefficients réels alors on peut décomposer $A=QR$ avec :
  • $Q$  une matrice orthogonale $~^tQQ=Id$
  • $R$ une matrice triangulaire supérieure
La décomposition QR d'une matrice peut s'obtenir par la méthode de Householder , ou plus simplement en appliquant le procédé de Gram-Schmidt aux vecteurs colonnes de $A$  (pour le produit scalaire usuel de ${\mathbb R}^n$). À partir de là il est assez facile de montrer que :

  • les matrices $A_n$ sont semblable à la matrice $A$ 
    $$A_{n+1}=R_nQ_n=~^tQ_nA_nQ_n=\dots= ~^t\tilde{Q}_{n}AQ\tilde{Q}_n$$
    c'est pour cette raison que les différentes matrices ont le même spectre et si elles tendent vers une matrice triangulaire supérieurs  les valeurs propres sont les valeurs sur la diagonale.
  •  par récurrence on montre aussi la relation :
    $$A^n=(Q_1\dots Q_n)(R_n\dots R_1)=\tilde{Q}_n(R_n\dots R_1)$$
    c'est à partir de cette formule qu'on peut montrer que la méthode QR utilise les mêmes principe que l'algorithme de la puissance itérée, pour calculer des approximations de chaque valeur/vecteur propre.
je ne connais pas de  démonstration de la convergence de la méthode QR,  celles que j'ai pu voir sont assez longues  et nécessitent des hypothèses restrictives. Elles montrent que si on classe les valeurs propres par module décroissant :
$$\vert \lambda_1 \vert\geq \vert \lambda_2 \vert\geq \dots \vert \lambda_p \vert 
~~~~  a= \min_{i=1,\dots,p-1}\left\vert{\lambda_{i+1}\over\lambda_i}\right\vert$$
alors l'erreur commise sur les vecteurs/valeurs propres à la n-ième étape  est en $O\left(a^n\right)$. La méthode QR marchera donc d'autant mieux que les valeurs propres sont "bien séparées". Cette estimation permet aussi de comprendre les cas d'échecs de la méthode QR :
  • s'il y a une valeur propre multiple on a alors $\left\vert{\lambda_{i+1}\over\lambda_i}\right\vert=1$  donc $a^n\not\to 0$  et la convergence de la méthode n'est pas assurée
  • s'il y a une valeur propre nulle $\left\vert{\lambda_{i+1}\over\lambda_i}\right\vert$  n'est même pas défini, et la décomposition QR dans ce cas est un peu ambiguë .
  • s'il y a des valeurs propres complexes, elles sont nécessairement conjuguées deux à deux et pour ces deux valeurs propres on a $\left\vert{\lambda_{i+1}\over\lambda_i}\right\vert=1$ ce qui pose le même problème que pour une valeur propre multiple

Il y a un cas particulier où la méthode QR  va converger: celui des matrices symétriques, en effet dans ce cas on sait que la matrice est diagonalisable (même si elle a des valeurs propres multiples)
théorème spectral Soit $A$ une matrice carrée nxn à coefficients réels et symétrique  $~^tA=A$  alors
  • toutes les valeurs propres de $A$ sont réelles 
  • on peut construire une base orthonormée de vecteurs propres de $A$
en d'autres termes $A$ est diagonalisable dans une base de vecteurs propres orthonormés :  $D=Q^{-1}AQ=~^tQAQ$  est diagonale.

Dans ce cas  il n'y a donc pas d'obstacle à la convergence de la méthode QR et on a même que
  • la suite de matrices $A_n$ converge vers une matrice diagonale composée des valeurs propres de $A$ 
  •  la suite $\tilde{Q}_n$ converge vers une matrice orthogonale correspondant aux vecteurs propres de $A$
En affichant les étapes de la méthode QR  pour une matrice réelle symétrique  on voit bien la convergence  vers une matrice triangulaire :
    On peut aussi remarquer que l'algorithme QR  trie les valeurs propres sur la diagonale dans l'ordre décroissant .

    Aucun commentaire:

    Enregistrer un commentaire

    Pour écrire des formules mathématiques vous pouvez utiliser la syntaxe latex en mettant vos formules entre des "dollars" $ \$....\$ $ par exemple :
    - $\sum_{n=1}^\infty {1\over n^2}={\pi^2\over 6}$ s'obtient avec \sum_{n=1}^\infty {1\over n^2}={\pi^2\over 6}
    - $\mathbb R$ s'obtient avec {\mathbb R} et $\mathcal D$ s'obtient avec {\mathcal D}
    - pour les crochets $\langle .,. \rangle$ dans les commentaires utilisez \langle .,. \rangle
    vous pouvez écrire du html dans les commentaires :
    - italique <i> ... </i> gras <b> ... </b>
    - lien <a href="http://adresse "> .... </a>