Matrice tridiagonale

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématiques, en algèbre linéaire, une matrice tridiagonale est une matrice dont tous les coefficients qui ne sont ni sur la diagonale principale, ni sur la diagonale juste au-dessus, ni sur la diagonale juste en dessous, sont nuls.

Par exemple, la matrice suivante est tridiagonale :

\begin{pmatrix}
1 & 4 & 0 & 0 \\
3 & 4 & 1 & 0 \\
0 & 2 & 3 & 4 \\
0 & 0 & 1 & 3 \\
\end{pmatrix}

Définition[modifier | modifier le code]

Une matrice A\in \mathcal{M}_n \left(K\right), dont on note les coefficients a_{i,j}, est dite tridiagonale si :

a_{i,j} = 0 \, pour tous (i, j) tels que |i-j| > 1~,

autrement dit si c'est une matrice de Hessenberg à la fois supérieure et inférieure.

Propriétés[modifier | modifier le code]

Si une matrice réelle tridiagonale A vérifie ak,k+1 × ak+1,k > 0 pour k = 1, 2, ..., n — c’est-à-dire si les signes de ses coefficients sont symétriques — alors elle est semblable à une matrice hermitienne, et donc toutes ses valeurs propres sont réelles. Cette dernière propriété est conservée si on considère plutôt la condition ak,k+1 × ak+1,k ≥ 0.

L'ensemble de toutes les matrices tridiagonales n × n est un espace vectoriel de dimension 3n-2.

Utilisation[modifier | modifier le code]

Algorithmes[modifier | modifier le code]

De nombreux algorithmes d'algèbre linéaire nécessitent bien moins d'opérations lorsqu'on les exécute sur des matrices diagonales. Il est courant que ce gain se propage aux matrices tridiagonales.

Par exemple, le déterminant d'une matrice tridiagonale A n×n peut être calculé par la formule récursive suivante :

 \det A = a_{n,n} \det \, [A]_{\{1,\ldots,n-1\}} - a_{n,n-1} a_{n-1,n} \det \, [A]_{\{1,\ldots,n-2\}} \, ,\,

où l'on note \det [A]_{\{1,\ldots,k\}} le k-ième mineur, c'est-à-dire le déterminant de la matrice obtenue en ne gardant que les k premières lignes et colonnes de A. Le calcul du déterminant par cette méthode est linéaire en n pour les matrices tridiagonales, alors qu'il est en dans le cas général.

Une transformation qui réduit une matrice quelconque à une matrice de Hessenberg réduira une matrice hermitienne à une matrice tridiagonale. Ainsi, de nombreux algorithmes de calcul des valeurs propres utilisent une étape de réduction sous la forme d'une matrice tridiagonale s'ils travaillent sur des matrices hermitiennes.

Mémoire[modifier | modifier le code]

Une matrice tridiagonale peut être stockée de façon optimisée en utilisant une représentation particulière. Par exemple, la bibliothèque LAPACK enregistre une matrice non symétrique sous la forme de trois tableaux unidimensionnels, l'un contenant les coefficients diagonaux et les deux autres les éléments respectivement au-dessus et au-dessous de la diagonale.

Mathématiques[modifier | modifier le code]

Les matrices tridiagonales sont courantes dans l'étude des splines cubiques. Elles sont également souvent des solutions au problème de Sturm-Liouville.

D'autre part, un système linéaire impliquant une matrice tridiagonale, de la forme :

A \cdot X = B \in \reals^n

peut être résolu au travers d'algorithmes spécifiques, qui nécessitent O(n) opérations (Golub et Van Loan).

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

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Lien externe[modifier | modifier le code]

(en) Matrices bi- et tridiagonales dans le manuel de LAPACK.