Tridiagonalisation d'une matrice symétrique
# 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={\begin{pmatrix}b_{1}&c_{1}&&0\\c_{1}&\ddots &\ddots &\\&\ddots &\ddots &c_{n-1}\\0&&c_{n-1}&b_{n}\end{pmatrix}}$

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

Théorème — Pour toute matrice symétrique réelle $S$ il existe une matrice orthogonale $H$ telle que $H^{\mathsf {T}}SH$ soit tridiagonale symétrique.

La démonstration est constructive et est donnée dans le paragraphe suivant.

## 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}^{\mathsf {T}}A_{k}H_{k}$, où $H_{k}$ est une matrice orthogonale.

Les matrices $A_{k}$ sont de la forme :

    $A_{k}={\begin{pmatrix}T_{k}&L_{k}^{\mathsf {T}}\\L_{k}&M_{k}\end{pmatrix}}$

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}={\begin{pmatrix}b_{1}&c_{1}&&(0)\\c_{1}&\ddots &\ddots &&&(0)\\&\ddots &\ddots &c_{k-1}\\(0)&&c_{k-1}&b_{k}&l_{1}&\ldots &l_{n-k}\\&&&l_{1}&\\&(0)&&\vdots &&(M_{k})\\&&&l_{n-k}&\\\end{pmatrix}}$

Si $S$ est de taille n, on construit ainsi (n-2) matrices orthogonales $H_{k}$ telles que $H^{\mathsf {T}}SH$ soit tridiagonale symétrique, où $H=H_{1}H_{2}\ldots H_{n-2}$.

## Méthode de Lanczos

Voir l’algorithme de Lanczos.

