Matrice tridiagonale
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 :
Définition
modifierUne matrice , dont on note les coefficients ai,j, est dite tridiagonale si :
- ai,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
modifierSi 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 l'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 n + 2(n – 1) = 3n – 2 (le nombre de coefficients non nuls).
Inversion
modifierL'inverse d'une matrice tridiagonale inversible,
est
où les coefficients θi satisfont la relation de récurrence
de termes initiaux θ0 = 1, θ1 = a1, tandis que les coefficients ϕi satisfont la relation de récurrence
de termes initiaux ϕn+1 = 1 and ϕn = an[1],[2].
En général, l'inverse d'une matrice tridiagonale est une matrice semiséparable et réciproquement[3]. L'inverse d'une matrice tridiagonale symétrique est une matrice factorisable de la forme[4],[5]
où avec
Utilisation
modifierAlgorithmes
modifierDe 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 :
- ,
où l'on note det [A]{1,...,k} le k-ième mineur dominant, 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 n3 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
modifierUne 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
modifierMéthode numérique pour résoudre un système tridiagonal
modifierSi l'on considère un système linéaire de la forme Ax = d où A 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[6]. Pour ce faire, on représente la matrice par :
On construit alors les coefficients de proche en proche :
- .
Une fois ces coefficients formés, on peut trouver la solution x = (x1,...,xn) :
- .
Matrices de Toeplitz tridiagonales
modifierSoit une matrice de Toeplitz tridiagonale d'ordre n à coefficients complexes,
- ,
telle que bc = d2 ≠ 0. Les valeurs propres de T sont les λk = a + 2d coskπn + 1 pour k = 1, 2, … , n, un vecteur propre xk associé à λk ayant pour composantes xk,j = (db) j sinj k πn + 1 (j = 1, 2, … , n)[7].
Si a, b et c sont réels et bc > 0, T est donc diagonalisable non seulement sur ℂ mais sur ℝ.
Applications
modifierLes 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 :
peut être résolu au travers d'algorithmes spécifiques, qui nécessitent O(n) opérations[8].
Notes et références
modifier- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Tridiagonal matrix » (voir la liste des auteurs).
- C. M. Da Fonseca, « On the eigenvalues of some tridiagonal matrices », Journal of Computational and Applied Mathematics, vol. 200, , p. 283–286 (DOI 10.1016/j.cam.2005.08.047 )
- R. A. Usmani, « Inversion of a tridiagonal jacobi matrix », Linear Algebra and its Applications, vol. 212-213, , p. 413–414 (DOI 10.1016/0024-3795(94)90414-6 )
- Raf Vandebril, Marc Van Barel et Nicola Mastronardi, Matrix Computations and Semiseparable Matrices. Volume I: Linear Systems, JHU Press, (ISBN 978-0-8018-8714-7), Theorem 1.38, p. 41
- Gérard Meurant, « A review on the inverse of symmetric tridiagonal and block tridiagonal matrices », SIAM Journal on Matrix Analysis and Applications, vol. 13, no 3, , p. 707-728 (DOI 10.1137/0613045, lire en ligne)
- Sébastien Bossu, « Tridiagonal and single-pair matrices and the inverse sum of two single-pair matrices », Linear Algebra and its Applications, vol. 699, , p. 129-158 (DOI 10.1016/j.laa.2024.06.018, lire en ligne)
- (en) Carnahan, Luther et Wilkes, Applied Numerical Methods.[réf. incomplète]
- (en) Albrecht Böttcher et Sergei M. Grudsky, Spectral Properties of Banded Toeplitz Matrices, SIAM, , 411 p. (ISBN 978-0-89871-785-3, lire en ligne), p. 35.
- (en) Gene H. Golub et Charles F. Van Loan, Matrix Computations, Johns Hopkins University Press, , 3e éd., 694 p. (ISBN 978-0-8018-5414-9, lire en ligne).
Voir aussi
modifierArticles connexes
modifier- Matrice bande
- Continuant (en)
- Matrice bidiagonale (en)
- Algorithme de Thomas
- Tridiagonalisation d'une matrice symétrique
Bibliographie
modifier(en) Roger A. Horn (en) et Charles R. Johnson, Matrix Analysis, Cambridge University Press, , 561 p. (ISBN 978-0-521-38632-6, lire en ligne)
Lien externe
modifier(en) Tridiagonal and Bidiagonal Matrices dans le manuel de LAPACK