Matriz tridiagonal

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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 a esta.

Sea ejemplo

\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 fisica 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 algortimos matemáticos.

Propiedades[editar]

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[editar]

El determinante de una matriz tridiagonal A de orden n satisface una recurrencia de tres términos.[3] Write f1 = |d1| = d1 and

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:

f_n = a_n f_{n-1} - c_{n-1}b_{n-1}f_{n-2}

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

Inversión[editar]

La inversa de una matriz no singular T:

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:

(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:

\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 θ0 = 1, θ1 = a1 y ϕi satisface

\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 = 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[editar]

Un sistema de ecuaciones Ax=b con b\in \reals^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 O(n) operaciones, frente a las O(n^3) que regiere 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 \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 \omega. Según el Teorema de Ostrowski y Reich, este valor viene dado por:

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

siendo \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[editar]

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[editar]

A transformation that reduces a general matrix to Hessenberg form will reduce a Hermitian matrix to tridiagonal form. So, many eigenvalue algorithms, when applied to a Hermitian matrix, reduce the input Hermitian matrix to tridiagonal form as a first step.

Notas[editar]

  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):  pp. 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:  pp. 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:  pp. 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):  pp. 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):  pp. 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[editar]