Tridiagonalisation d'une matrice symétrique

Le théorème spectral affirme que toute matrice symétrique réelle $S$ est diagonalisable dans une base orthonormée. Cependant, une telle diagonalisation est souvent coûteuse en temps de calcul et il est parfois suffisant de transformer une matrice symétrique en matrice tridiagonale :

$T=\left(\begin{array}{cccc}{b}_1& c_1& & 0\\ c_1& \ddots & \ddots & \\ & \ddots & \ddots & c_{n-1}\\ 0& & c_{n-1}& b_n\end{array}\right)$

De plus, $S$ et $T$ ayant les mêmes valeurs propres, la tridiagonalisation est souvent la première étape du calcul des valeurs propres de $S$.

Lemme de Householder

La démonstration est constructiveModèle:, et est donnée dans le paragraphe suivant.

Construction et preuve

Méthode de Householder

La méthode de construction de Householder consiste par récurrence à créer, à partir de $A_1=S$, une suite de matrices $(A_k)$ telle que $A_{k+1}=H_k^{𝖳}{A}_k{H}_k$, où $H_k$ est une matrice orthogonale.

Les matrices $A_k$ sont de la forme :

$A_k=\left(\begin{array}{cc}{T}_k& L_k^{𝖳}\\ L_k& M_k\end{array}\right)$

où

• $T_k$ est une matrice tridiagonale symétrique de taille $k$
• $L_k$ une matrice rectangulaire dont seule la dernière colonne est non nulle.
• $M_k$ une matrice de taille $n-k$

$A_k$ est donc de la forme :

$A_k=\left(\begin{array}{cccc}{b}_1& c_1& & (0)\\ c_1& \ddots & \ddots & & & (0)\\ & \ddots & \ddots & c_{k-1}\\ (0)& & c_{k-1}& b_k& l_1& \dots & l_{n-k}\\ & & & l_1& \\ & (0)& & ⋮& & (M_k)\\ & & & l_{n-k}& \end{array}\right)$

Modèle:... Si $S$ est de taille $n$, on construit ainsi $(n-2)$ matrices orthogonales $H_k$ telles que $H^{𝖳}SH$ soit tridiagonale symétrique, où $H=H_1{H}_2\dots H_{n-2}$.

Choix des matrices

On pourra choisir différents types de matrices orthogonales.

• la méthode historique de Householder utilise des matrices de symétrie :

$H_k=\left(\begin{array}{ccccc}\mathrm{𝟏}& 0& \cdots & \cdots & 0\\ 0& -\cos \theta & ⋮& \sin \theta & ⋮\\ ⋮& ⋮& \mathrm{𝟏}& ⋮& ⋮\\ ⋮& \sin \theta & \cdots & \cos \theta & 0\\ 0& \cdots & \cdots & \cdots & \mathrm{𝟏}\end{array}\right)$

• la méthode de Givens est similaire, à la différence que les matrices $(H_k)$ seront des matrices de rotation $(G_k)$.

$G_k=\left(\begin{array}{ccccc}\mathrm{𝟏}& 0& \cdots & \cdots & 0\\ 0& \cos \theta & ⋮& -\sin \theta & ⋮\\ ⋮& ⋮& \mathrm{𝟏}& ⋮& ⋮\\ ⋮& \sin \theta & \cdots & \cos \theta & 0\\ 0& \cdots & \cdots & \cdots & \mathrm{𝟏}\end{array}\right)$

On pourra aussi utiliser l'algorithme de Lanczos.

Voir aussi

Articles connexes

• Diagonalisation
• Trigonalisation