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
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 ak,k+1 ak+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 ak,k+1 ak+1,k > 0 by ak,k+1 ak+1,k ≥ 0.
El conjunto de todas las matrices n × n tridiagonales forma un espacio vectorial de dimensión 3n-2.
Determinante
El determinante de una matriz tridiagonal A de orden n satisface una recurrencia de tres términos.[3] Siendo f1 = |d1| = d1 y
lo se puede definir la siguiente relación de recurrencia para definir el continuante:
con valores iniciales f0 = 1 y f-1 = 0. El coste computacional de esta forma es frente a para una matriz genérica.
Inversión
La inversa de una matriz no singular T:
es dada por:
Donde los términos θi satisfacen la siguiente relación de recurrencia:
con condiciones iniciales θ0 = 1, θ1 = a1 y ϕi satisface
con condiciones iniciales ϕn+1 = 1 and ϕn = an.[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
Un sistema de ecuaciones con 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 operaciones, frente a las 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 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 . Según el Teorema de Ostrowski y Reich, este valor viene dado por:
siendo 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
- ↑ Muir, Thomas (1960). A treatise on the theory of determinants. Dover Publications. pp. 516–525.
- ↑ Horn, Roger A.; Johnson, Charles R. (1985). Matrix Analysis. Cambridge University Press. p. 28. ISBN 0521386322.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- Module for Tri-Diagonal Linear Systems
- Moawwad El-Mikkawy, Abdelrahman Karawia (2006). «Inversion of general tridiagonal matrices». 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