Calcul de valeurs et de vecteurs propres

In [9]:
%pylab inline

Populating the interactive namespace from numpy and matplotlib

1. Méthode de la puissance

Soit $A$ une matrice carrée diagonalisable de taille n dont la valeur propre la plus grande en module est simple, i.e. $$ |\lambda_1|>|\lambda_2|\geq\dots\geq|\lambda_n|. $$ La méthode de la puissance est une méthode itérative pour approcher $\lambda_1$ et son vecteur propre associé, noté $\vec{v}_1$. Elle consiste en l'algorithme suivant.

  • $\textbf{Initialisation:}$ choisir $\vec{q}_0\in\mathbb{C}^n$ tel que $\Vert\vec{q}_0\Vert_2=1$,
  • $\textbf{Itérations:}$ pour $k\geq 0$, $\vec{z}_{k+1}=A\vec{q}_k$, $\mu_{k+1}=\vec{q}^T_{k}\vec{z}_{k+1}$, $\displaystyle\vec{q}_{k+1}=\frac{\vec{z}_{k+1}}{\Vert\vec{z}_{k+1}\Vert_2}$.

En supposant que le vecteur $\vec{q}_0^T\vec{v}_1\neq0$, $$ \vec{q}_k \to_{k\to\infty} \vec{v}_1 \quad\text{et} \quad \mu_k \to_{k\to\infty} \lambda_1 $$ et la vitesse de convergence dépend du quotient $\vert\lambda_2/\lambda_1\vert$. Plus celui-ci sera petit, plus la convergence sera rapide.

(a) Proposer un critère d'arrêt pour les itérations de l'algorithme de la méthode de la puissance introduit plus haut.

(b) Écrire une fonction $\texttt{[lambda,v,nIter]=puissance(A,q0,eps,nmax)}$ qui approche les valeurs $\lambda_1$ et $v_1$ de la matrice $A$ par la méthode de la puissance. L'algorithme itère jusqu'à ce que le critère d'arrêt devienne inférieur à $\texttt{eps}$ ou bien lorqu'on a fait plus de nmax itérations. La fonction doit aussi renvoyer $\texttt{nIter}$, i.e. le nombre d'itérations effectuées dans la boucle.

(c) On considère la matrice $$ A=\begin{pmatrix}15&-2&2\\1&10&-3\\-2&1&0\end{pmatrix}. $$

  • Utiliser la fonction $\texttt{puissance}$ pour approcher les quantités $\lambda_1$ et $v_1$ de cette matrice. Prendre $\vec{q}_0=\begin{pmatrix}1&1&1\end{pmatrix}^T/\sqrt{3}$ comme initialisation et une tolérance $eps=10^{-8}$ pour le critère d'arrêt.
  • Valider le résultat obtenu en utilisant la commande Python $\texttt{eig(A)}$.

(d) On souhaite à présent évaluer l'influence de la condition initiale sur la convergence de la méthode. On considère pour cela la matrice réelle symétrique $$ B=\begin{pmatrix} 0,5172&0,5473&-1,224&0,8012\\ 0,5473&1,388&1,353&-1,112\\ -1,224&1,353&0,03642&2,893\\ 0,8012&-1,112&2,893&0,05827 \end{pmatrix}. $$

  • Pour chacune des trois initialisations qui suivent, tracer sur une même figure les termes de la suite $\|\vec{z}_k\|_2$ en fonction de $k$: $\vec{q}^{(0)}=\begin{pmatrix}1&0&0&0\end{pmatrix}^T$, $\begin{pmatrix}1&1&1&1\end{pmatrix}^T/\sqrt{4}$ et $\begin{pmatrix}1&1&0&0\end{pmatrix}^T/\sqrt{2}$.
  • Utiliser la commande \texttt{eig} pour obtenir les valeurs propres de $B$. Commenter alors les trois courbes obtenues à la question précédente en tentant de donner des explications.
In [ ]:

Méthode de la puissance inverse

La méthode de la puissance inverse permet d'obtenir une approximation de la valeur propre d'une matrice $A$ la plus proche d'un nombre $t\in\mathbb{C}$ (où l'on suppose que $t\not\in\sigma(A)$). Ceci se fait en appliquant la méthode de la puissance à la matrice ${M_t}^{-1}=(A-t I)^{-1}$. Cet algorithme est cependant plus coûteux que la méthode de la puissance classique appliqué à A car il nécessite la résolution d'un système linéaire à chaque itération de l'algorithme. Pour ce faire, en pratique on calcule une fois pour toutes la factorisation LU de $M_t$, ce qui permet par la suite de ne résoudre que deux systèmes triangulaires à chaque itération de la méthode.

  • Sur le modèle de la fonction $\texttt{puissance}$ de l'exercice précédent, écrire une fonction $\texttt{[lambda,v,nIter]= puissanceinv(A,q0,t,eps,nmax)}$ mettant en oeuvre la méthode de la puissance inverse, le paramètre d'entrée $\texttt{t}$ étant l'approximation initiale de la valeur propre que l'on souhaite approcher. On utilisera la commande $\texttt{lu}$ pour calculer la factorisation LU de la matrice $M_t$ et, pour résoudre les systèmes triangulaires associés à cette factorisation.

  • Utiliser la fonction $\texttt{puissanceinv}$ pour calculer la valeur propre de plus petit module de la matrice $A$ de l'exercice précédent, en prenant $\vec{q}_0=\begin{pmatrix}1&1&1\end{pmatrix}^T/\sqrt{3}$ comme initialisation et une tolérance $\texttt{eps}=10^{-8}$ pour le critère d'arrêt.

In [ ]: