Maîtrise de Mathématiques

Analyse Numérique Janvier 2002

Durée 3h

Document autorisé : polycopié analyse numérique

Pour des matrices de très grande taille les méthodes classiques de calcul de valeurs propres sont dificilement applicables en pratique. On calcule alors une approximation des valeurs propres à l'aide d'une matrice auxiliaire de taille plus petite, comme dans la méthode de Lanczos étudiée ici.

On note $\{e_1,\dots,e_n\}$ la base canonique de $\mathbb{R}^n$, $(v_1\dots v_n)$ la matrice dont les colonnes sont les vecteurs $v_1,\dots,v_n$ et $[v_1,\dots,v_n]$ le sous-espace vectoriel engendré par les vecteurs $v_1,\dots,v_n$.

Soit $A$ une matrice symétrique $n\times n$, de valeurs propres simples, et $u_1\ne 0$ un vecteur fixé.

On définit un ensemble de vecteurs $\{u_j\}_{j=1,\dots,n}$ par $u_1$ et la relation de récurrence $u_{j+1}=Au_j$.

On suppose qu'on a un ensemble de vecteurs $\{q_j\}_{j=1,\dots,n}$ avec les propriétés suivantes :

• $q_1=u_1$
• les $q_j$ sont orthonormés (la matrice associée $Q=(q_1\dots q_n)$ est orthogonale)
• si on note $T=Q^tAQ$, alors $T$ est tridiagonale :
  
  $$T=\left( \begin{array}{cccc} \alpha_1 & \beta_1 & &\\ \beta... ...dots &\ddots\\ & & \beta_{n-1} & \alpha_n \end{array}\right)$$
  
  

1) Montrer que $u_{j+1}=QT^je_1$.

On écrit matriciellement

$$R=(e_1\ Te_1\ T^2e_1\dots T^{n-1}e_1)\quad (u_1\dots u_n)=QR$$

Quelle propriété a la matrice $R$ ?

En déduire que

$$[u_1,\dots,u_j]=[q_1,\dots,q_j]\quad j=1,\dots,n$$

2) Expliciter la colonne $j$ de la relation $AQ=QT$. En déduire une relation entre $q_{j-1},\ q_j,\ q_{j+1}$. Montrer que $\alpha_j$ s'exprime en fonction de $q_j$ seulement.

3) On pose $r_j=(A-\alpha_j I)q_j -\beta_{j-1}q_{j-1}$.

Exprimer $q_{j+1}$ en fonction de $r_j$ seulement.

4) Si $q_1=u_1$ est vecteur propre de $A$ pour une valeur propre $\lambda$ que vaut $r_1$ ? Que peut-on en conclure ?

.../...

5) Soient $\{\lambda_1,\dots,\lambda_n\}$ les valeurs propres de $A$ et $\{v_1,\dots,v_n\}$ les vecteurs propres orthonormés correspondants.

On note

$$T_j=\pmatrix{\alpha_1 & \beta_1\cr \beta_1 & \alpha_2 &\beta... ...ha_j\cr} {\rm et}\ Sp(T_j)=\{\theta_1,\dots,\theta_j\}\quad j<n$$

A l'aide du théorème de Courant-Fisher montrer que $\theta_1\le\lambda_1$.

6) On note ${\cal P}_k$ l'ensemble des polynômes de degré $\le k\}$.

Montrer que $[q_1,\dots,q_j]=\{p(A)q_1;p \in{\cal P}_{j-1}\}$.

7) On développe $q_1$ sur la base $\{v_i;i=1,\dots,n\}$ : $$q_1=\sum_{i=1}^n x_iv_i$$.

Montrer que

$$\theta_1=\max_{p \in{\cal P}_{j-1}} \frac{(p(A)q_1\vert Ap(A)... ...2\lambda_i p(\lambda_i)^2} {\sum_{i=1}^{n}x_i^2p(\lambda_i)^2}$$

En déduire l'estimation

$$\theta_1\ge \lambda_1-(\lambda_1-\lambda_n) \frac{\sum_{i=2}^{n}x_i^2p(\lambda_i)^2} {\sum_{i=1}^{n}x_i^2p(\lambda_i)^2}$$

Que devient cette estimation si $q_1\perp v_1$ ?