Matriz tridiagonal

En álgebra lineal se denomina matriz tridiagonal a una matriz cuyos elementos son solo distintos de cero en la diagonal principal y las diagonales adyacentes por encima y por debajo de esta.

Sea ejemplo

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

Este tipo de matrices dispersas son habituales en álgebra lineal numérica y en la resolución de problemas de física computacional al aproximarse mediante diferencias finitas ecuaciones diferenciales (ecuación de Poisson, ecuación del calor, ecuación de onda...), particularmente en problemas unidimensionales. Dada su particularidad existen algoritmos y reglas específicas para operar con ellas con mayor eficiencia que con una matriz genérica.

De forma general, cualquier matriz hermitiana puede convertirse en una matriz tridiagonal mediante una transformación ortogonal usando el algoritmo de Lanczos. Así, también se emplean estas matrices como pasos intermedios en otros algoritmos matemáticos.

Propiedades

El determinante de una matriz tridiagonal es el continuante de sus elementos,^[1]​ algo de significado en el contexto de las fracciones continuas.

Una matriz tridiagonal es al mismo tiempo una matriz de Hessenberg superior e inferior.^[2]​ En particular, una matriz triangular es la suma directa de p 1-a-1 y q 2-a-2 matrices tales que p + q/2 = n (la dimensión de la tridiagonal).

Aunque una matriz tridiagonal no tiene necesariamente que ser simétrica o hermitiana, suelen serlo en el contexto de los problemas que las originan. Más aún, si una matriz tridiagonal A satisface a_k,k+1 a_k+1,k > 0, de forma que el signo de sus elementos es simétrico es semejante a una hermitiana y por tanto sus valores propios son todos reales. Esta afirmación sigue siendo cierta si se reemplaza la condición por a_k,k+1 a_k+1,k > 0 by a_k,k+1 a_k+1,k ≥ 0.

El conjunto de todas las matrices n × n tridiagonales forma un espacio vectorial de dimensión 3n-2.

Determinante

Artículo principal: Continuante (matemáticas)

El determinante de una matriz tridiagonal A de orden n satisface una recurrencia de tres términos.^[3]​ Siendo f₁ = |d₁| = d₁ y

${\displaystyle f_{n}={\begin{vmatrix}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{vmatrix}}}$ 

lo se puede definir la siguiente relación de recurrencia para definir el continuante:

${\displaystyle f_{n}=a_{n}f_{n-1}-c_{n-1}b_{n-1}f_{n-2}}$ 

con valores iniciales f₀ = 1 y f_-1 = 0. El coste computacional de esta forma es ${\displaystyle \theta (n)}$  frente a ${\displaystyle \theta (n^{3})}$  para una matriz genérica.

Inversión

La inversa de una matriz no singular T:

${\displaystyle T={\begin{pmatrix}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{pmatrix}}}$ 

es dada por:

${\displaystyle (T^{-1})_{ij}={\begin{cases}(-1)^{i+j}b_{i}\cdots b_{j-1}\theta _{i-1}\phi _{j+1}/\theta _{n}&{\text{ if }}i\leq j\\(-1)^{i+j}c_{j}\cdots c_{i-1}\theta _{j-1}\phi _{i+1}/\theta _{n}&{\text{ if }}i>j\\\end{cases}}}$ 

Donde los términos θ_i satisfacen la siguiente relación de recurrencia:

${\displaystyle \theta _{i}=a_{i}\theta _{i-1}-b_{i-1}c_{i-1}\theta _{i-2}\quad {\text{ for }}i=2,3,\ldots ,n}$ 

con condiciones iniciales θ₀ = 1, θ₁ = a₁ y ϕ_i satisface

${\displaystyle \phi _{i}=a_{i}\phi _{i+1}-b_{i}c_{i}\phi _{i+2}\quad {\text{ for }}i=n-1,\ldots ,1}$ 

con condiciones iniciales ϕ_n+1 = 1 and ϕ_n = a_n.^[4]​^[5]​

Existen formas cerradas para casos como el de matrices simétricas^[6]​ o el de matrices de Toeplitz.^[7]​

Resolución de sistemas de ecuaciones

Artículo principal: Algoritmo para matrices tridiagonales

Artículo principal: Teorema de Ostrowski y Reich

Un sistema de ecuaciones ${\displaystyle Ax=b}$  con ${\displaystyle b\in \mathbb {R} ^{n}}$  y A tridiagonal puede ser resuelto de forma eficiente con una variante de la eliminación gaussiana. Este algoritmo (a veces llamado Algoritmo de Thomas) requiere solo ${\displaystyle O(n)}$  operaciones, frente a las ${\displaystyle O(n^{3})}$  que requiere una matriz genérica.^[8]​

Esta optimización se puede lograr también mediante métodos iterativos. Existen variantes del método de Gauss-Seidel que usan un factor de relajación ${\displaystyle \omega }$  para acelerar la convergencia del método. El caso de una matriz tridiagonal es una de las pocas para las que se puede demostrar la existencia de un valor óptimo para ${\displaystyle \omega }$ . Según el Teorema de Ostrowski y Reich, este valor viene dado por:

${\displaystyle w={\dfrac {2}{1+{\sqrt {1-\rho (T)}}}}\,}$ 

siendo ${\displaystyle \rho (T)}$  el radio espectral de la matriz de transformación del método de Gauss-Seidel asociado al sistema en cuestión.

Implementación en ordenador

Una matriz tridiagonal puede ser almacenada de forma más eficiente mediante esquemas específicos. Por ejemplo la librería LAPACK usada en el lenguaje Fortran lo almacena como tres vectores unidimensionales: uno de longitud n para la diagonal principal y dos vectores de longitud n − 1 para las adyacentes.

Aplicaciones

Una transformación que reduce una matriz general a una matriz de Hessenberg reducirá una matriz Hermítica a una matriz tridiagonal. Es por ello que muchos algoritmos para el cálculo de autovalores cuando se aplican a una matriz Hermítica, reducen previamente la matriz Hermítica a una matriz tridiagonal.

Notas

1. Thomas Muir (1960). A treatise on the theory of determinants. Dover Publications. pp. 516–525. 
2. Horn, Roger A.; Johnson, Charles R. (1985). Matrix Analysis. Cambridge University Press. p. 28. ISBN 0521386322. 
3. El-Mikkawy, M. E. A. (2004). «On the inverse of a general tridiagonal matrix». Applied Mathematics and Computation 150 (3): 669-679. doi:10.1016/S0096-3003(03)00298-4. 
4. Da Fonseca, C. M. (2007). «On the eigenvalues of some tridiagonal matrices». Journal of Computational and Applied Mathematics 200: 283-286. doi:10.1016/j.cam.2005.08.047. 
5. Usmani, R. A. (1994). «Inversion of a tridiagonal jacobi matrix». Linear Algebra and its Applications. 212-213: 413-414. doi:10.1016/0024-3795(94)90414-6. 
6. Hu, G. Y.; O'Connell, R. F. (1996). «Analytical inversion of symmetric tridiagonal matrices». Journal of Physics A: Mathematical and General 29 (7): 1511. doi:10.1088/0305-4470/29/7/020. 
7. Huang, Y.; McColl, W. F. (1997). «Analytical inversion of general tridiagonal matrices». Journal of Physics A: Mathematical and General 30 (22): 7919. doi:10.1088/0305-4470/30/22/026. 
8. Golub, Gene H.; Van Loan, Charles F. (1996). Matrix Computations (3rd ed. edición). The Johns Hopkins University Press. ISBN 0-8018-5414-8. 

Enlaces externos

• Tridiagonal and Bidiagonal Matrices in the LAPACK manual.
• Moawwad El-Mikkawy, Abdelrahman Karawia (2006). . Applied Mathematics Letters 19 (8): 712-720. doi:10.1016/j.aml.2005.11.012. Archivado desde el original el 20 de julio de 2011. 
• High performance algorithms for reduction to condensed (Hessenberg, tridiagonal, bidiagonal) form

•   Datos: Q1755277