Tridiagonalisation d'une matrice symétrique

Cet article est une ébauche concernant l’algèbre.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Consultez la liste des tâches à accomplir en page de discussion.

Le théorème spectral affirme que toute matrice symétrique réelle ${\displaystyle 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 :

${\displaystyle 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, ${\displaystyle S}$ et ${\displaystyle T}$ ayant les mêmes valeurs propres, la tridiagonalisation est souvent la première étape du calcul des valeurs propres de ${\displaystyle S}$.

La démonstration est constructive^[1],[2] 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 ${\displaystyle k}$
• ${\displaystyle L_{k}}$ une matrice rectangulaire dont seule la dernière colonne est non nulle.
• ${\displaystyle M_{k}}$ une matrice de taille ${\displaystyle 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}}}$

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

Si ${\displaystyle S}$ est de taille ${\displaystyle n}$, on construit ainsi ${\displaystyle (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}}$.

On pourra choisir différents types de matrices orthogonales.

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

${\displaystyle 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 ${\displaystyle (H_{k})}$ seront des matrices de rotation ${\displaystyle (G_{k})}$.

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

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

• Diagonalisation
• Trigonalisation

• Portail des mathématiques