TP 4- Valeurs propres

Analyse Numérique Matricielle

Polytech SU, 2023-2024

In [94]:
import numpy as np
import matplotlib.pyplot as plt

On rappelle l'algorithme de recherche de la plus grande valeur propre de $A\in M_n(\mathbb{C})$. On pose $x_0\in\mathbb{C}^n$ puis $$x_{k+1}=\frac{Ax_k}{\Vert A x_{k}\Vert_2}.$$ Quand on arrête le processus à $k_0$, on pose alors $x_1=\frac{x_{k_0}}{\Vert x_{k_0}\Vert_2}$ et $$\lambda_1=\frac{\langle Ax_{k_0},x_{k_0}\rangle}{\Vert x_{k_0}\Vert_2^2}.$$

Exercice 1:

On considère la matrice $$A=\begin{pmatrix} 2&-1&0& 0&\ldots&0\\ -1&2&-1 &0&\ddots&\vdots\\ 0&\ddots&\ddots&\ddots&\ddots&0\\ 0&\ddots&\ddots&\ddots&\ddots&0\\ \vdots&\ddots&0&-1 &2&-1\\ 0&\dots&0&0&-1&2 \end{pmatrix}.$$

  1. Construire une fonction dépendant de $n$ pour construire la matrice $A\in M_n(\mathbb{R})$.
In [95]:
### Construction de A
  1. On choisit $n=10$. Utiliser la commande eig pour trouver une approximation des valeurs propres $\lambda_1>\dots>\lambda_n$ de la matrice $A$. Recopier $\lambda_1$ et $\lambda_n$.
In [96]:
###valeurs propres de A
  1. On choisit $w=(1,\dots,n)^T\in \mathbb{R}^n$ et $x^{(0)}=\frac{w}{\Vert w\Vert}$. Implémenter la méthode de la puissance pour le calcul de la plus grande valeur propre (en valeur absolue) de la matrice $A$. Recopier la valeur propre trouvée, ainsi que le nombre d'itérations nécessaire pour satisfaire la tolérance $tol=10^{-6}$ dans le critère d'arrêt de la méthode.
In [97]:
####méthode de la puissance
  1. Reprendre la question précédente en prenant $w=(\sin(2j\pi/(n+1)))_{1\leq j\leq n}$ et $x^{(0)}=\frac{w}{\Vert w\Vert}$. Que remarquez vous ?
In [98]:
###autre initialisation
  1. Pour $w=(1,\dots,n)^T\in \mathbb{R}^n$ et $x^{(0)}=\frac{w}{\Vert w\Vert}$ et $n=5,10,\ldots,100$, calculer le nombre d'itération nécessaires pour atteindre $tol=10^{-6}$. Afficher ce nombre en fonction de $n$ et le comparer à $\vert\lambda_1/\lambda_2\vert$.
In [99]:
####Evolution du temps de calculs en fonction de n
  1. On s'intéresse au calcul de la plus petite valeur propre $\lambda_n$ de $A$. Comme $\lambda_n^{-1}$ est alors la plus grande valeur propre de $A^{-1}$, on introduit la méthode itérative suivante : $$\left\lbrace\begin{aligned} x_0&\in \mathbb{R}^n\\ A\tilde{x}_{k+1}&=x_k\\ x_{k+1}&=\frac{\tilde{x}_{k+1}}{\Vert \tilde{x}_{k+1}\Vert} \end{aligned}\right..$$

Pourquoi cet algorithme doit permettre de trouver $\lambda_n$ ? Reprendre la question 3. pour calculer $\lambda_n$ en implémentant l'algorithme précédent.

In [100]:
###méthode de la pusisance inverse
  1. Ecrire un code permettant d'obtenir une matrice $\tilde{A}$, de taille $n$, telle que $\tilde{a}_{ij}=\frac{1/2}{n-i-j+3/2}$.
In [101]:
###matrice customisée

8.Reprendre les questions 3, 5 et 6 avec cette matrice. Pourquoi le nombre d'itérations est-il plus élevé ? (Comparer par exemple les valeurs propres de cette matrice par rapport à celle de la question 3.).

In [102]:
## Question 3. 5 et 6

Exercice 2:

On revient maintenant sur l matrice $$A=\begin{pmatrix} 2&-1&0& 0&\ldots&0\\ -1&2&-1 &0&\ddots&\vdots\\ 0&\ddots&\ddots&\ddots&\ddots&0\\ 0&\ddots&\ddots&\ddots&\ddots&0\\ \vdots&\ddots&0&-1 &2&-1\\ 0&\dots&0&0&-1&2 \end{pmatrix},$$ avec $n=10$. On souhaite estimer l'ensemble des valeurs propre de $A$. Pour cela on remarquera que comme $A$ est symétrique, ses vecteurs propres forment une base orthonormée. Ainsi, on peut facilement montrer que, en notant $v_{1} , \ldots , v_{n}$ des vecteurs propres unitaires asociés à $\lambda_{1}> ...> \lambda_{n}$, la matrice $$ A^{(1)} = A - \lambda_{1} v_{1}v_{1}^{T} $$ a $0 , \lambda_{2} , \ldots , \lambda_{n}$ comme valeurs propres, et $v_{1} , \ldots v_{n}$ comme vecteurs propres associés. De manière générale, la matrice $$ A^{(\ell)} = A - \sum_{i=1}^{\ell}\lambda_{i} v_{i}v_{i}^{T} = A^{(\ell-1)} - \lambda_{\ell}v_{\ell}v_{\ell}^{T} $$ a pour valeurs propres $0 , \ldots , 0 , \lambda_{\ell +1} , \ldots , \lambda_{n}$ et pour vecteurs propres $v_{1} , \ldots v_{n}$. Estimer toutes les valeurs propres. Pour assurer que l'intialisation vérifie les bonnes propriétés, on prendra $x_{0}= w/\|w\|$ avec $w$ tiré selon une loi normale grâce à la fonction np.random.normal. On pourra également utiliser la fonction np.outer pour le produit de vecteurs. Enfin, on pourra utiliser la fonction suivante:

In [1]:
def pow_method(A, x0, tol=1e-6, max_iter=1000):
    x = x0
    for i in range(max_iter):
        Ax = np.dot(A, x)
        xnew = Ax / np.linalg.norm(Ax)
        if np.linalg.norm(xnew -   x) < tol:
            break
        x=xnew
    lambda_max = np.dot(x, A @ x)/np.linalg.norm(x)**2
    return lambda_max, xnew/np.linalg.norm(xnew)
In [ ]: