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 $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[modifier | modifier le code]

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^[1]^,^[2] et est donnée dans le paragraphe suivant.

Construction et preuve[modifier | modifier le code]

Méthode de Householder[modifier | modifier le code]

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}}

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

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[modifier | modifier le code]

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[modifier | modifier le code]

Références[modifier | modifier le code]

↑ (en) Alston S. Householder et Friedrich L. Bauer, « On certain methods for expanding the characteristic polynomial », Numerische Mathematik, vol. 1, n^o 1,‎ 1959, p. 29–37 (DOI 10.1007/BF01386370)
↑ (en) J. H. Wilkinson, « Householder's method for symmetric matrices », Numerische Mathematik,‎ 1962, p. 354–361

Bibliographie[modifier | modifier le code]

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[modifier | modifier le code]

Portail des mathématiques

[1] (en) Alston S. Householder et Friedrich L. Bauer, « On certain methods for expanding the characteristic polynomial », Numerische Mathematik, vol. 1, n^o 1,‎ 1959, p. 29–37 (DOI 10.1007/BF01386370)

[2] (en) J. H. Wilkinson, « Householder's method for symmetric matrices », Numerische Mathematik,‎ 1962, p. 354–361

[1]

[2]