Matrice tridiagonale

Modèle:Ébauche En mathématiques, en algèbre linéaire, une matrice tridiagonale (ou trigonale) est une matrice dont tous les coefficients qui ne sont ni sur la diagonale principale, ni sur la diagonale juste au-dessus, ni celle juste en dessous, sont nuls.

Par exemple, la matrice suivante est tridiagonale :

$\left(\begin{array}{cccc}1& 4& 0& 0\\ 3& 4& 1& 0\\ 0& 2& 3& 4\\ 0& 0& 1& 3\end{array}\right)$

Définition

Une matrice $A\in {ℳ}_n\left(K\right)$, dont on note les coefficients Modèle:Mvar, est dite tridiagonale si :

Modèle:Math pour tous Modèle:Math tels que Modèle:Math,

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

Propriétés

Si une matrice réelle tridiagonale Modèle:Mvar vérifie Modèle:Math pour Modèle:Math — 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 l'on considère plutôt la condition Modèle:Math.

L'ensemble de toutes les matrices tridiagonales Modèle:Math est un espace vectoriel de dimension Modèle:Math (le nombre de coefficients non nuls).

Inversion

L'inverse d'une matrice tridiagonale inversible,

$T=\left(\begin{array}{cc}{a}_1& b_1\\ c_1& a_2& b_2\\ & c_2& \ddots & \ddots \\ & & \ddots & \ddots & b_{n-1}\\ & & & c_{n-1}& a_n\end{array}\right),$

est

$(T^{-1}{)}_{ij}=\{\begin{array}{cc}(-1{)}^{i+j}{b}_i\cdots b_{j-1}{\theta }_{i-1}{\varphi }_{j+1}/{\theta }_n,& i<j\\ {\theta }_{i-1}{\varphi }_{j+1}/{\theta }_n,& i=j\\ (-1{)}^{i+j}{c}_j\cdots c_{i-1}{\theta }_{j-1}{\varphi }_{i+1}/{\theta }_n,& i>j\end{array}$

où les coefficients θ_i satisfont la relation de récurrence

${\theta }_i=a_i{\theta }_{i-1}-b_{i-1}{c}_{i-1}{\theta }_{i-2}i=2,3,\dots ,n$

de termes initiaux θ₀ = 1, θ₁ = a₁, tandis que les coefficients ϕ_i satisfont la relation de récurrence

${\varphi }_i=a_i{\varphi }_{i+1}-b_i{c}_i{\varphi }_{i+2}i=n-1,\dots ,1$

de termes initiaux ϕ_n+1 = 1 and ϕ_n = a_nModèle:,.

En général, l'inverse d'une matrice tridiagonale est une matrice semiséparable et réciproquement. L'inverse d'une matrice tridiagonale symétrique est une matrice factorisable de la formeModèle:,

${\left(\begin{array}{cc}{\alpha }_1& -{\beta }_1\\ -{\beta }_1& {\alpha }_2& -{\beta }_2\\ & \ddots & \ddots & \ddots & \\ & & \ddots & \ddots & -{\beta }_{n-1}\\ & & & -{\beta }_{n-1}& {\alpha }_n\end{array}\right)}^{-1}=\left(\begin{array}{cccc}{a}_1{b}_1& a_1{b}_2& \cdots & a_1{b}_n\\ a_1{b}_2& a_2{b}_2& \cdots & a_2{b}_n\\ ⋮& ⋮& \ddots & ⋮\\ a_1{b}_n& a_2{b}_n& \cdots & a_n{b}_n\end{array}\right)=\left(a_{\min (i,j)}{b}_{\max (i,j)}\right)$

où $\{\begin{array}{c}{a}_i=\frac{{\beta }_i\cdots {\beta }_{n-1}}{{\delta }_i\cdots {\delta }_n{b}_n}\\ b_i=\frac{{\beta }_1\cdots {\beta }_{i-1}}{d_1\cdots d_i}\end{array}$ avec $\{\begin{array}{cc}{d}_n={\alpha }_n,d_{i-1}={\alpha }_{i-1}-\frac{{\beta }_{i-1}^2}{d_i},& i=n,n-1,\cdots ,2,\\ {\delta }_1={\alpha }_1,{\delta }_{i+1}={\alpha }_{i+1}-\frac{{\beta }_i^2}{{\delta }_i},& i=1,2,\cdots ,n-1.\end{array}$

Utilisation

Algorithmes

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 Modèle:Mvar Modèle:Math peut être calculé par la formule récursive suivante :

$\det A=a_{n,n}\det [A{]}_{\{1,\dots ,n-1\}}-a_{n,n-1}{a}_{n-1,n}\det [A{]}_{\{1,\dots ,n-2\}}$,

où l'on note Modèle:Math le Modèle:Mvar-ième mineur dominant, c'est-à-dire le déterminant de la matrice obtenue en ne gardant que les Modèle:Mvar premières lignes et colonnes de Modèle:Mvar. Le calcul du déterminant par cette méthode est linéaire en Modèle:Mvar pour les matrices tridiagonales, alors qu'il est en Modèle:Math 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

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.

Méthodes de résolution

Méthode numérique pour résoudre un système tridiagonal

Si l'on considère un système linéaire de la forme Modèle:Math où Modèle:Mvar est une matrice tridiagonale, il est possible d'appliquer une méthode simplifiée reposant sur la décomposition LU sans stockage des matrices de la décomposition pour le résoudre numériquement. Pour ce faire, on représente la matrice par :

$A=\left(\begin{array}{cccccc}{a}_1& b_1& 0& \dots & \dots & 0\\ c_2& a_2& b_2& \ddots & & ⋮\\ 0& c_3& a_3& b_3& \ddots & ⋮\\ ⋮& \ddots & \ddots & \ddots & \ddots & 0\\ ⋮& & \ddots & \ddots & \ddots & b_{n-1}\\ 0& \dots & \dots & 0& c_n& a_n\end{array}\right)$

On construit alors les coefficients de proche en proche :

${\alpha }_1=a_1,{\beta }_1=\frac{d_1}{{\alpha }_1}$

$\mathrm{\forall }i\in \{2,...,n\},{\alpha }_i=a_i-\frac{c_i{b}_{i-1}}{{\alpha }_{i-1}},{\beta }_i=\frac{d_i-c_i{\beta }_{i-1}}{{\alpha }_i}$.

Une fois ces coefficients formés, on peut trouver la solution Modèle:Math :

$x_n={\beta }_n,\mathrm{\forall }i\in \{n-1,...,1\},x_i={\beta }_i-\frac{b_i{x}_{i+1}}{{\alpha }_i}$.

Matrices de Toeplitz tridiagonales

Soit une matrice de Toeplitz tridiagonale d'ordre Modèle:Mvar à coefficients complexes,

$T=\left(\begin{array}{ccccc}a& b& 0& 0& 0\\ c& \ddots & \ddots & 0& 0\\ 0& \ddots & \ddots & \ddots & 0\\ 0& 0& \ddots & \ddots & b\\ 0& 0& 0& c& a\end{array}\right)$,

telle que Modèle:Math. Les valeurs propres de Modèle:Mvar sont les Modèle:Math pour Modèle:Math, un vecteur propre Modèle:Mvar associé à Modèle:Math ayant pour composantes Modèle:Math (Modèle:Math).

Si Modèle:Mvar, Modèle:Mvar et Modèle:Mvar sont réels et Modèle:Math, Modèle:Mvar est donc diagonalisable non seulement sur ℂ mais sur ℝ.

Applications

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 :

$Ax=b\in {ℝ}^n$

peut être résolu au travers d'algorithmes spécifiques, qui nécessitent Modèle:Math opérations.

Voir aussi

Articles connexes

• Matrice bande
• Modèle:Lien
• Modèle:Lien
• Algorithme de Thomas
• Tridiagonalisation d'une matrice symétrique

Lien externe

Modèle:En Tridiagonal and Bidiagonal Matrices dans le manuel de LAPACK