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=(b1c10c1⋱⋱⋱⋱cn−10cn−1bn)

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𝖳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 A1=S, une suite de matrices (Ak) telle que Ak+1=Hk𝖳AkHk, où Hk est une matrice orthogonale.

Les matrices Ak sont de la forme :

Ak=(TkLk𝖳LkMk)

où

  • Tk est une matrice tridiagonale symétrique de taille k
  • Lk une matrice rectangulaire dont seule la dernière colonne est non nulle.
  • Mk une matrice de taille n−k

Ak est donc de la forme :

Ak=(b1c1(0)c1⋱⋱(0)⋱⋱ck−1(0)ck−1bkl1…ln−kl1(0)⋮(Mk)ln−k)

Si S est de taille n, on construit ainsi (n−2) matrices orthogonales Hk telles que H𝖳SH soit tridiagonale symétrique, où H=H1H2…Hn−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 :
Hk=(𝟏0⋯⋯00−cos⁡θ⋮sin⁡θ⋮⋮⋮𝟏⋮⋮⋮sin⁡θ⋯cos⁡θ00⋯⋯⋯𝟏)
  • la méthode de Givens est similaire, à la différence que les matrices (Hk) seront des matrices de rotation (Gk).
Gk=(𝟏0⋯⋯00cos⁡θ⋮−sin⁡θ⋮⋮⋮𝟏⋮⋮⋮sin⁡θ⋯cos⁡θ00⋯⋯⋯𝟏)

On pourra aussi utiliser l'algorithme de Lanczos.

Voir aussi

Articles connexes