En álgebra lineal , una matriz tridiagonal es una matriz de bandas que tiene elementos distintos de cero en la diagonal principal , la primera diagonal debajo de esta y la primera diagonal solo sobre la diagonal principal.
Por ejemplo, la siguiente matriz es tridiagonal:
El determinante de una matriz tridiagonal viene dado por el continuo de sus elementos. [1]
Se puede realizar una transformación ortogonal de una matriz simétrica (o hermitiana) a forma tridiagonal con el algoritmo de Lanczos .
Propiedades
Una matriz tridiagonal es una matriz que es tanto la matriz de Hessenberg superior como la inferior . [2] En particular, una matriz tridiagonal es una suma directa de p 1-a-1 y q 2-por-2 matrices tales que p + q / 2 = n - la dimensión de la tridiagonal. Aunque una matriz tridiagonal general no es necesariamente simétrica o hermitiana , muchas de las que surgen al resolver problemas de álgebra lineal tienen una de estas propiedades. Además, si una matriz tridiagonal real A satisface a k , k +1 a k +1, k > 0 para todo k , de modo que los signos de sus entradas son simétricos, entonces es similar a una matriz hermitiana, por un cambio diagonal de matriz base. Por tanto, sus valores propios son reales. Si reemplazamos la desigualdad estricta por a k , k +1 a k +1, k ≥ 0, entonces, por continuidad, se garantiza que los valores propios son reales, pero la matriz ya no necesita ser similar a una matriz hermitiana. [3]
El conjunto de todas las matrices tridiagonales n × n forma un espacio vectorial dimensional 3n-2 .
Muchos algoritmos de álgebra lineal requieren un esfuerzo computacional significativamente menor cuando se aplican a matrices diagonales, y esta mejora a menudo se traslada también a matrices tridiagonales.
Determinante
El determinante de una matriz tridiagonal A de orden n se puede calcular a partir de una relación de recurrencia de tres términos . [4] Escriba f 1 = | a 1 | = a 1 (es decir, f 1 es el determinante de la matriz de 1 por 1 que consta solo de a 1 ), y sea
La secuencia ( f i ) se llama continuante y satisface la relación de recurrencia
con valores iniciales f 0 = 1 y f −1 = 0. El costo de calcular el determinante de una matriz tridiagonal usando esta fórmula es lineal en n , mientras que el costo es cúbico para una matriz general.
Inversión
La inversa de una matriz tridiagonal no singular T
es dado por
donde el θ i satisfago la relación de recurrencia
con condiciones iniciales θ 0 = 1, θ 1 = a 1 y el ϕ i satisfago
con condiciones iniciales ϕ n +1 = 1 y ϕ n = a n . [5] [6]
Las soluciones de forma cerrada se pueden calcular para casos especiales tales como matrices simétricas con todos los elementos diagonales y fuera de la diagonal iguales [7] o matrices de Toeplitz [8] y también para el caso general. [9] [10]
En general, la inversa de una matriz tridiagonal es una matriz semiseparable y viceversa. [11]
Solución de sistema lineal
Un sistema de ecuaciones Ax = b para se puede resolver mediante una forma eficiente de eliminación gaussiana cuando A es tridiagonal llamado algoritmo de matriz tridiagonal , que requiere operaciones O ( n ). [12]
Autovalores
Cuando una matriz tridiagonal también es Toeplitz , existe una solución simple de forma cerrada para sus valores propios, a saber: [13] [14]
Una matriz tridiagonal simétrica real tiene valores propios reales, y todos los valores propios son distintos (simples) si todos los elementos fuera de la diagonal son distintos de cero. [15] Existen numerosos métodos para el cálculo numérico de los valores propios de una matriz tridiagonal simétrica real con precisión finita arbitraria, que normalmente requieren operaciones para una matriz de tamaño , aunque existen algoritmos rápidos que (sin cálculo paralelo) requieren sólo . [dieciséis]
Como nota al margen, una matriz tridiagonal simétrica no reducida es una matriz que contiene elementos fuera de la diagonal distintos de cero de la tridiagonal, donde los valores propios son distintos mientras que los vectores propios son únicos hasta un factor de escala y son mutuamente ortogonales. [17]
Para matrices tridiagonales asimétricas, se puede calcular la descomposición propia utilizando una transformación de similitud .
Similitud con la matriz tridiagonal simétrica
Dada una matriz no simétrica tridiagonal real
dónde .
Suponga que cada producto de las entradas fuera de la diagonal es estrictamente positivo y definir una matriz de transformación por
La transformación de la similitud produce una matriz tridiagonal simétrica [18] por
Tenga en cuenta que y tienen los mismos valores propios.
Programación de computadoras
Una transformación que reduce una matriz general a la forma de Hessenberg reducirá una matriz hermitiana a una forma tridiagonal . Por lo tanto, muchos algoritmos de valores propios , cuando se aplican a una matriz hermitiana, reducen la matriz hermitiana de entrada a una forma tridiagonal (simétrica real) como primer paso.
Una matriz tridiagonal también se puede almacenar de manera más eficiente que una matriz general mediante el uso de un esquema de almacenamiento especial . Por ejemplo, el paquete LAPACK Fortran almacena una matriz tridiagonal asimétrica de orden n en tres matrices unidimensionales, una de longitud n que contiene los elementos diagonales y dos de longitud n - 1 que contienen los elementos subdiagonal y superdiagonal .
Ver también
- Matriz pentadiagonal
Notas
- ^ Thomas Muir (1960). Un tratado sobre la teoría de los determinantes . Publicaciones de Dover . págs. 516–525 .
- ^ Horn, Roger A .; Johnson, Charles R. (1985). Análisis matricial . Prensa de la Universidad de Cambridge. pag. 28. ISBN 0521386322.
- ^ Horn & Johnson, página 174
- ^ El-Mikkawy, MEA (2004). "En el inverso de una matriz tridiagonal general". Matemática Aplicada y Computación . 150 (3): 669–679. doi : 10.1016 / S0096-3003 (03) 00298-4 .
- ^ Da Fonseca, CM (2007). "Sobre los valores propios de algunas matrices tridiagonales" . Revista de Matemática Computacional y Aplicada . 200 : 283-286. doi : 10.1016 / j.cam.2005.08.047 .
- ^ Usmani, RA (1994). "Inversión de una matriz jacobi tridiagonal" . Álgebra lineal y sus aplicaciones . 212–213: 413–414. doi : 10.1016 / 0024-3795 (94) 90414-6 .
- ^ Hu, GY; O'Connell, RF (1996). "Inversión analítica de matrices tridiagonales simétricas". Revista de Física A: Matemática y General . 29 (7): 1511. doi : 10.1088 / 0305-4470 / 29/7/020 .
- ^ Huang, Y .; McColl, WF (1997). "Inversión analítica de matrices tridiagonales generales". Revista de Física A: Matemática y General . 30 (22): 7919. doi : 10.1088 / 0305-4470 / 30/22/026 .
- ^ Mallik, RK (2001). "La inversa de una matriz tridiagonal" . Álgebra lineal y sus aplicaciones . 325 : 109-139. doi : 10.1016 / S0024-3795 (00) 00262-7 .
- ^ Kılıç, E. (2008). "Fórmula explícita para la inversa de una matriz tridiagonal por fracciones continuas hacia atrás". Matemática Aplicada y Computación . 197 : 345–357. doi : 10.1016 / j.amc.2007.07.046 .
- ^ Raf Vandebril; Marc Van Barel; Nicola Mastronardi (2008). Cálculos matriciales y matrices semiseparables. Volumen I: Sistemas lineales . Prensa JHU. Teorema 1.38, pág. 41. ISBN 978-0-8018-8714-7.
- ^ Golub, Gene H .; Van Loan, Charles F. (1996). Cálculos matriciales (3ª ed.). Prensa de la Universidad Johns Hopkins. ISBN 0-8018-5414-8.
- ^ Noschese, S .; Pasquini, L .; Reichel, L. (2013). "Matrices tridiagonales de Toeplitz: propiedades y aplicaciones novedosas". Álgebra lineal numérica con aplicaciones . 20 (2): 302. doi : 10.1002 / nla.1811 .
- ^ Esto también se puede escribir como porque , como se hace en: Kulkarni, D .; Schmidt, D .; Tsui, SK (1999). "Autovalores de matrices tridiagonales pseudo-Toeplitz" (PDF) . Álgebra lineal y sus aplicaciones . 297 : 63. doi : 10.1016 / S0024-3795 (99) 00114-7 .
- ^ Parlett, BN (1980). El problema del valor propio simétrico . Prentice Hall, Inc.
- ^ Coakley, ES; Rokhlin, V. (2012). "Un algoritmo rápido de divide y vencerás para calcular los espectros de matrices tridiagonales simétricas reales" . Análisis Armónico Computacional y Aplicado . 34 (3): 379–414. doi : 10.1016 / j.acha.2012.06.003 .
- ^ Dhillon, Inderjit Singh. Un nuevo algoritmo O (n 2) para el problema de autovalor / autovector tridiagonal simétrico (PDF) . pag. 8.
- ^ "www.math.hkbu.edu.hk conferencia de matemáticas" (PDF) .
enlaces externos
- Matrices Tridiagonales y Bidiagonales en el manual LAPACK.
- Moawwad El-Mikkawy, Abdelrahman Karawia (2006). "Inversión de matrices tridiagonales generales" (PDF) . Letras de matemáticas aplicadas . 19 (8): 712–720. doi : 10.1016 / j.aml.2005.11.012 . Archivado desde el original (PDF) el 20 de julio de 2011.
- Algoritmos de alto rendimiento para la reducción a forma condensada (Hessenberg, tridiagonal, bidiagonal)
- Solucionador de sistema lineal tridiagonal en C ++