Tridiagonalisation d'une matrice symétrique

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

La méthode de construction de Householder consiste par récurrence à créer, à partir de ${\displaystyle A_{1}=S}$, une suite de matrices ${\displaystyle (A_{k})}$ telle que ${\displaystyle A_{k+1}=H_{k}^{\mathsf {T}}A_{k}H_{k}}$, où ${\displaystyle H_{k}}$ est une matrice orthogonale.

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

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

où

• ${\displaystyle T_{k}}$ est une matrice tridiagonale symétrique de taille k
• ${\displaystyle L_{k}}$ une matrice rectangulaire dont seule la dernière colonne est non nulle.
• ${\displaystyle M_{k}}$ une matrice de taille n-k

${\displaystyle A_{k}}$ est donc de la forme :

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

Voir l’algorithme de Lanczos.