Matriz tridiagonal

Matriz con elementos distintos de cero en la diagonal principal y las diagonales superiores e inferiores

En álgebra lineal , una matriz tridiagonal es una matriz de bandas que tiene elementos distintos de cero solo en la diagonal principal , la subdiagonal/diagonal inferior (la primera diagonal debajo de esta) y la supradiagonal/diagonal superior (la primera diagonal sobre la diagonal principal). Por ejemplo, la siguiente matriz es tridiagonal :

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

El determinante de una matriz tridiagonal está dado por el continuo de sus elementos. ^[1]

Una transformación ortogonal de una matriz simétrica (o hermítica) a una forma tridiagonal se puede realizar con el algoritmo de Lanczos .

Propiedades

Una matriz tridiagonal es una matriz que es tanto matriz de Hessenberg superior como inferior . ^[2] En particular, una matriz tridiagonal es una suma directa de matrices p 1 por 1 y q 2 por 2 tales que p + q /2 = n — la dimensión de la tridiagonal. Aunque una matriz tridiagonal general no es necesariamente simétrica o hermítica , 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 hermítica, por una matriz de cambio de base diagonal. Por lo tanto, sus valores propios son reales. Si reemplazamos la desigualdad estricta por a _{k , k +1} a _{k +1, k} ≥ 0, entonces por continuidad, los valores propios todavía están garantizados como reales, pero la matriz ya no necesita ser similar a una matriz hermítica. ^[3]

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

Muchos algoritmos de álgebra lineal requieren significativamente menos esfuerzo computacional 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 ₁  = | a ₁ | =  a ₁ (es decir, f ₁ es el determinante de la matriz 1 por 1 que consta solo de a ₁ ), y sea

${\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}}.}$

La secuencia ( f _i ) se llama continua y satisface la relación de recurrencia.

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

con valores iniciales f ₀  = 1 y f ₋₁  = 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

${\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}}}$

viene dado 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<j\\\theta _{i-1}\phi _{j+1}/\theta _{n}&{\text{ if }}i=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 θ _i satisfacen la relación de recurrencia

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

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

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

con condiciones iniciales ϕ _{n +1}  = 1 y ϕ _n  =  a _n . ^{[5] [6]}

Se pueden calcular soluciones en forma cerrada para casos especiales, como matrices simétricas con todos los elementos diagonales y no diagonales 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] La inversa de una matriz tridiagonal simétrica se puede escribir como una matriz de un solo par (también conocida como matriz semiseparable representable por generador ) de la forma ^{[12] [13]}

${\displaystyle {\begin{pmatrix}\alpha _{1}&-\beta _{1}\\-\beta _{1}&\alpha _{2}&-\beta _{2}\\&\ddots &\ddots &\ddots &\\&&\ddots &\ddots &-\beta _{n-1}\\&&&-\beta _{n-1}&\alpha _{n}\end{pmatrix}}^{-1}={\begin{pmatrix}a_{1}b_{1}&a_{1}b_{2}&\cdots &a_{1}b_{n}\\a_{1}b_{2}&a_{2}b_{2}&\cdots &a_{2}b_{n}\\\vdots &\vdots &\ddots &\vdots \\a_{1}b_{n}&a_{2}b_{n}&\cdots &a_{n}b_{n}\end{pmatrix}}=\left(a_{\min(i,j)}b_{\max(i,j)}\right)}$

donde con ${\displaystyle {\begin{cases}\displaystyle a_{i}={\frac {\beta _{i}\cdots \beta _{n-1}}{\delta _{i}\cdots \delta _{n}\,b_{n}}}\\\displaystyle b_{i}={\frac {\beta _{1}\cdots \beta _{i-1}}{d_{1}\cdots d_{i}}}\end{cases}}}$ ${\displaystyle {\begin{cases}d_{n}=\alpha _{n},\quad d_{i-1}=\alpha _{i-1}-{\frac {\beta _{i-1}^{2}}{d_{i}}},&i=n,n-1,\cdots ,2,\\\delta _{1}=\alpha _{1},\quad \delta _{i+1}=\alpha _{i+1}-{\frac {\beta _{i}^{2}}{\delta _{i}}},&i=1,2,\cdots ,n-1.\end{cases}}}$

Solución de sistema lineal

Un sistema de ecuaciones Ax  =  b para  puede resolverse mediante una forma eficiente de eliminación gaussiana cuando A es tridiagonal llamada algoritmo de matriz tridiagonal , que requiere O ( n ) operaciones. ^[14] ${\displaystyle b\in \mathbb {R} ^{n}}$

Valores propios

Cuando una matriz tridiagonal también es Toeplitz , existe una solución simple en forma cerrada para sus valores propios, a saber: ^{[15] [16]}

${\displaystyle a-2{\sqrt {bc}}\cos \left({\frac {k\pi }{n+1}}\right),\qquad k=1,\ldots ,n.}$

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. ^[17] 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 solo . ^[18] ${\displaystyle O(n^{2})}$ ${\displaystyle n\times n}$ ${\displaystyle O(n\log n)}$

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. ^[19]

Similitud con matriz tridiagonal simétrica

Para matrices tridiagonales asimétricas o no simétricas, se puede calcular la descomposición propia mediante una transformación de similitud. Dada una matriz tridiagonal real no simétrica

${\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}}}$

donde . Suponga que cada producto de las entradas fuera de la diagonal es estrictamente positivo y defina una matriz de transformación mediante ^[20] ${\displaystyle b_{i}\neq c_{i}}$ ${\displaystyle b_{i}c_{i}>0}$ ${\displaystyle D}$

${\displaystyle D:=\operatorname {diag} (\delta _{1},\dots ,\delta _{n})\quad {\text{for}}\quad \delta _{i}:={\begin{cases}1&,\,i=1\\{\sqrt {\frac {c_{i-1}\dots c_{1}}{b_{i-1}\dots b_{1}}}}&,\,i=2,\dots ,n\,.\end{cases}}}$

La transformación de similitud produce una matriz tridiagonal simétrica mediante: ^{[21] [20]} ${\displaystyle D^{-1}TD}$ ${\displaystyle J}$

${\displaystyle J:=D^{-1}TD={\begin{pmatrix}a_{1}&\operatorname {sgn} b_{1}\,{\sqrt {b_{1}c_{1}}}\\\operatorname {sgn} b_{1}\,{\sqrt {b_{1}c_{1}}}&a_{2}&\operatorname {sgn} b_{2}\,{\sqrt {b_{2}c_{2}}}\\&\operatorname {sgn} b_{2}\,{\sqrt {b_{2}c_{2}}}&\ddots &\ddots \\&&\ddots &\ddots &\operatorname {sgn} b_{n-1}\,{\sqrt {b_{n-1}c_{n-1}}}\\&&&\operatorname {sgn} b_{n-1}\,{\sqrt {b_{n-1}c_{n-1}}}&a_{n}\end{pmatrix}}\,.}$

Tenga en cuenta que y tienen los mismos valores propios. ${\displaystyle T}$ ${\displaystyle J}$

Programación de computadoras

Una transformación que reduce una matriz general a la forma de Hessenberg reducirá una matriz hermítica a la forma tridiagonal. Por lo tanto, muchos algoritmos de valores propios , cuando se aplican a una matriz hermítica, reducen la matriz hermítica de entrada a la forma tridiagonal (real simétrica) como primer paso. ^[22]

Una matriz tridiagonal también se puede almacenar de manera más eficiente que una matriz general mediante un esquema de almacenamiento especial . Por ejemplo, el paquete Fortran LAPACK 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 subdiagonales y superdiagonales .

Aplicaciones

La discretización en el espacio de la ecuación unidimensional de difusión o calor

${\displaystyle {\frac {\partial u(t,x)}{\partial t}}=\alpha {\frac {\partial ^{2}u(t,x)}{\partial x^{2}}}}$

El uso de diferencias finitas centrales de segundo orden da como resultado

${\displaystyle {\begin{pmatrix}{\frac {\partial u_{1}(t)}{\partial t}}\\{\frac {\partial u_{2}(t)}{\partial t}}\\\vdots \\{\frac {\partial u_{N}(t)}{\partial t}}\end{pmatrix}}={\frac {\alpha }{\Delta x^{2}}}{\begin{pmatrix}-2&1&0&\ldots &0\\1&-2&1&\ddots &\vdots \\0&\ddots &\ddots &\ddots &0\\\vdots &&1&-2&1\\0&\ldots &0&1&-2\end{pmatrix}}{\begin{pmatrix}u_{1}(t)\\u_{2}(t)\\\vdots \\u_{N}(t)\\\end{pmatrix}}}$

con constante de discretización . La matriz es tridiagonal con y . Nota: aquí no se utilizan condiciones de contorno. ${\displaystyle \Delta x}$ ${\displaystyle a_{i}=-2}$ ${\displaystyle b_{i}=c_{i}=1}$

Véase también

• Matriz pentadiagonal
• Matriz de Jacobi (operador)

Notas

1. Thomas Muir (1960). Tratado sobre la teoría de los determinantes . Dover Publications . Págs. 516–525.
2. Horn, Roger A.; Johnson, Charles R. (1985). Análisis de matrices . Cambridge University Press. pág. 28. ISBN 0521386322.
3. Horn & Johnson, página 174
4. El-Mikkawy, MEA (2004). "Sobre la inversa de una matriz tridiagonal general". Matemáticas Aplicadas y Computación . 150 (3): 669–679. doi :10.1016/S0096-3003(03)00298-4.
5. 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 .
6. Usmani, RA (1994). "Inversión de una matriz de Jacobi tridiagonal". Álgebra lineal y sus aplicaciones . 212–213: 413–414. doi : 10.1016/0024-3795(94)90414-6 .
7. Hu, GY; O'Connell, RF (1996). "Inversión analítica de matrices tridiagonales simétricas". Journal of Physics A: Mathematical and General . 29 (7): 1511. doi :10.1088/0305-4470/29/7/020.
8. Huang, Y.; McColl, WF (1997). "Inversión analítica de matrices tridiagonales generales". Journal of Physics A: Mathematical and General . 30 (22): 7919. doi :10.1088/0305-4470/30/22/026.
9. 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 .
10. Kılıç, E. (2008). "Fórmula explícita para la inversa de una matriz tridiagonal mediante fracciones continuas hacia atrás". Matemáticas Aplicadas y Computación . 197 : 345–357. doi :10.1016/j.amc.2007.07.046.
11. Raf Vandebril; Marc Van Barel; Nicola Mastronardi (2008). Cálculos matriciales y matrices semiseparables. Volumen I: Sistemas lineales . JHU Press. Teorema 1.38, pág. 41. ISBN 978-0-8018-8714-7.
12. Meurant, Gerard (1992). "Una revisión sobre la inversa de matrices tridiagonales simétricas y tridiagonales en bloque". Revista SIAM sobre análisis de matrices y aplicaciones . 13 (3): 707–728. doi :10.1137/0613045.
13. Bossu, Sebastien (2024). "Matrices tridiagonales y de un solo par y la suma inversa de dos matrices de un solo par". Álgebra lineal y sus aplicaciones . 699 : 129–158. arXiv : 2304.06100 . doi :10.1016/j.laa.2024.06.018.
14. Golub, Gene H. ; Van Loan, Charles F. (1996). Cálculos matriciales (3.ª ed.). Prensa de la Universidad Johns Hopkins. ISBN 0-8018-5414-8.
15. Noschese, S.; Pasquini, L.; Reichel, L. (2013). "Matrices de Toeplitz tridiagonales: propiedades y aplicaciones novedosas". Álgebra lineal numérica con aplicaciones . 20 (2): 302. doi :10.1002/nla.1811.
16. Esto también se puede escribir como porque , como se hace en: Kulkarni, D.; Schmidt, D.; Tsui, SK (1999). "Valores propios de matrices pseudo-Toeplitz tridiagonales" (PDF) . Álgebra lineal y sus aplicaciones . 297 : 63. doi :10.1016/S0024-3795(99)00114-7. ${\displaystyle a+2{\sqrt {bc}}\cos(k\pi /{(n+1)})}$ ${\displaystyle \cos(x)=-\cos(\pi -x)}$
17. Parlett, BN (1997) [1980]. El problema del valor propio simétrico . Clásicos en matemáticas aplicadas. Vol. 20. SIAM. ISBN 0-89871-402-8.OCLC 228147822  .
18. 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 .
19. Dhillon, Inderjit Singh (1997). Un nuevo algoritmo O(n2) para el problema de autovalor/autovector tridiagonal simétrico (PDF) (PhD). Universidad de California, Berkeley. pág. 8. CSD-97-971, ADA637073.
20. Kreer, M. (1994). "Procesos analíticos de nacimiento-muerte: un enfoque del espacio de Hilbert". Procesos estocásticos y sus aplicaciones . 49 (1): 65–74. doi :10.1016/0304-4149(94)90112-0.
21. Meurant, Gérard (octubre de 2008). "Matrices tridiagonales" (PDF) – vía Instituto de Matemática Computacional, Universidad Bautista de Hong Kong.
22. Eidelman, Yuli; Gohberg, Israel; Gemignani, Luca (1 de enero de 2007). "Sobre la reducción rápida de una matriz cuasiseparable a formas de Hessenberg y tridiagonales". Álgebra lineal y sus aplicaciones . 420 (1): 86–101. doi : 10.1016/j.laa.2006.06.028 . ISSN  0024-3795.

Enlaces externos

• Matrices Tridiagonales y Bidiagonales en el manual LAPACK.
• Moawwad El-Mikkawy, Abdelrahman Karawia (2006). "Inversión de matrices tridiagonales generales" (PDF) . Applied Mathematics Letters . 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 reducción a forma condensada (Hessenberg, tridiagonal, bidiagonal)
• Solucionador de sistemas lineales tridiagonales en C++