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.

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}^{\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}$.

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}={\begin{pmatrix}\mathbf {1} &0&\cdots &\cdots &0\\0&-\cos \theta &\vdots &\sin \theta &\vdots \\\vdots &\vdots &\mathbf {1} &\vdots &\vdots \\\vdots &\sin \theta &\cdots &\cos \theta &0\\0&\cdots &\cdots &\cdots &\mathbf {1} \end{pmatrix}}$

• la méthode de Givens est similaire, à la différence que les matrices $(H_{k})$ seront des matrices de rotation $(G_{k})$.

$G_{k}={\begin{pmatrix}\mathbf {1} &0&\cdots &\cdots &0\\0&\cos \theta &\vdots &-\sin \theta &\vdots \\\vdots &\vdots &\mathbf {1} &\vdots &\vdots \\\vdots &\sin \theta &\cdots &\cos \theta &0\\0&\cdots &\cdots &\cdots &\mathbf {1} \end{pmatrix}}$

On pourra aussi utiliser l'algorithme de Lanczos.

Voir aussi

Bibliographie

Grégoire Allaire, Analyse numérique et optimisation, Éditions de l'École polytechnique, 2005, 459 p. (ISBN 2-7302-1255-8, lire en ligne)

Articles connexes

• Diagonalisation
• Trigonalisation