En álgebra lineal numérica , el algoritmo de matriz tridiagonal , también conocido como algoritmo de Thomas (llamado así por Llewellyn Thomas ), es una forma simplificada de eliminación gaussiana que se puede utilizar para resolver sistemas de ecuaciones tridiagonales . Un sistema tridiagonal para n incógnitas puede escribirse como
dónde y .
Para tales sistemas, la solución se puede obtener en operaciones en lugar de requerido por la eliminación gaussiana . Un primer barrido elimina el's, y luego una sustitución hacia atrás (abreviada) produce la solución. Los ejemplos de tales matrices surgen comúnmente de la discretización de la ecuación de Poisson 1D y la interpolación spline cúbica natural .
El algoritmo de Thomas no es estable en general, pero lo es en varios casos especiales, como cuando la matriz es diagonalmente dominante (ya sea por filas o columnas) o simétrica positiva definida ; [1] [2] para una caracterización más precisa de la estabilidad del algoritmo de Thomas, ver Teorema de Higham 9.12. [3] Si se requiere estabilidad en el caso general, se recomienda en su lugar la eliminación gaussiana con pivote parcial (GEPP). [2]
Método
El barrido hacia adelante consiste en el cálculo de nuevos coeficientes de la siguiente manera, denotando los nuevos coeficientes con primos:
y
Luego, la solución se obtiene mediante sustitución inversa:
El método anterior no modifica los vectores de coeficientes originales, pero también debe realizar un seguimiento de los nuevos coeficientes. Si los vectores de coeficientes pueden modificarse, entonces un algoritmo con menos contabilidad es:
- Para hacer
seguido de la sustitución trasera
La implementación en una subrutina VBA sin preservar los vectores de coeficientes se muestra a continuación
Sub TriDiagonal_Matrix_Algorithm ( N% , A # (), B # (), C # (), D # (), X # ()) Dim i% , W # For i = 2 To N W = A ( i ) / B ( i - 1 ) B ( i ) = B ( i ) - W * C ( i - 1 ) D ( i ) = D ( i ) - W * D ( i - 1 ) Siguiente i X ( N ) = D ( N ) / B ( N ) For i = N - 1 To 1 Step - 1 X ( i ) = ( D ( i ) - C ( i ) * X ( i + 1 )) / B ( i ) Siguiente i End Sub
Derivación
La derivación del algoritmo de matriz tridiagonal es un caso especial de eliminación gaussiana .
Supongamos que las incógnitas son , y que las ecuaciones a resolver son:
Considere modificar el segundo () ecuación con la primera ecuación de la siguiente manera:
que daría:
Tenga en cuenta que ha sido eliminado de la segunda ecuación. Usando una táctica similar con la segunda ecuación modificada en la tercera ecuación, se obtiene:
Esta vez fue eliminado. Si este procedimiento se repite hasta quefila; el (modificado) La ecuación involucrará solo una desconocida, . Esto puede resolverse y luego usarse para resolver el ecuación, y así sucesivamente hasta que se resuelvan todas las incógnitas.
Claramente, los coeficientes de las ecuaciones modificadas se vuelven cada vez más complicados si se expresan explícitamente. Al examinar el procedimiento, los coeficientes modificados (anotados con tildes) pueden definirse de forma recursiva:
Para acelerar aún más el proceso de solución, pueden dividirse (si no hay división por riesgo cero), los coeficientes modificados más nuevos, cada uno anotado con un primo, serán:
Esto da el siguiente sistema con las mismas incógnitas y coeficientes definidos en términos de los originales anteriores:
La última ecuación involucra solo una incógnita. Resolverlo a su vez reduce la siguiente última ecuación a una incógnita, de modo que esta sustitución hacia atrás se puede usar para encontrar todas las incógnitas:
Variantes
En algunas situaciones, particularmente aquellas que involucran condiciones de contorno periódicas , es posible que sea necesario resolver una forma ligeramente perturbada del sistema tridiagonal:
En este caso, podemos utilizar la fórmula de Sherman-Morrison para evitar las operaciones adicionales de eliminación gaussiana y seguir utilizando el algoritmo de Thomas. El método requiere resolver una versión no cíclica modificada del sistema tanto para la entrada como para un vector correctivo disperso, y luego combinar las soluciones. Esto se puede hacer de manera eficiente si ambas soluciones se calculan a la vez, ya que se puede compartir la parte directa del algoritmo de matriz tridiagonal puro.
En otras situaciones, el sistema de ecuaciones puede ser tridiagonal de bloques (ver matriz de bloques ), con submatrices más pequeñas dispuestas como elementos individuales en el sistema de matriz anterior (por ejemplo, el problema de Poisson 2D ). Se han desarrollado formas simplificadas de eliminación gaussiana para estas situaciones. [4]
El libro de texto Numerical Mathematics de Quarteroni, Sacco y Saleri, enumera una versión modificada del algoritmo que evita algunas de las divisiones (utilizando en su lugar multiplicaciones), lo cual es beneficioso en algunas arquitecturas de computadora.
Se han publicado solucionadores tridiagonales paralelos para muchas arquitecturas vectoriales y paralelas, incluidas las GPU [5] [6]
Para un tratamiento extenso de los solucionadores tridiagonales paralelos y tridiagonales en bloque, consulte [7]
Referencias
- ^ Pradip Niyogi (2006). Introducción a la dinámica de fluidos computacional . Pearson Education India. pag. 76. ISBN 978-81-7758-764-7.
- ^ a b Biswa Nath Datta (2010). Álgebra lineal numérica y aplicaciones, segunda edición . SIAM. pag. 162. ISBN 978-0-89871-765-5.
- ^ Nicholas J. Higham (2002). Precisión y estabilidad de algoritmos numéricos: segunda edición . SIAM. pag. 175. ISBN 978-0-89871-802-7.
- ^ Quarteroni, Alfio; Sacco, Riccardo; Saleri, Fausto (2007). "Sección 3.8". Matemáticas numéricas . Springer, Nueva York. ISBN 978-3-540-34658-6.
- ^ Chang, L.-W .; Hwu, W, -M. (2014). "Una guía para implementar solucionadores tridiagonales en GPU". En V. Kidratenko (ed.). Cálculos numéricos con GPU . Saltador. ISBN 978-3-319-06548-9.
- ^ Venetis, IE; Kouris, A .; Sobczyk, A .; Gallopoulos, E .; Sameh, A. (2015). "Un solucionador tridiagonal directo basado en rotaciones Givens para arquitecturas GPU". Computación paralela . 49 : 101-116.
- ^ Gallopoulos, E .; Philippe, B .; Sameh, AH (2016). "Capítulo 5". Paralelismo en cálculos matriciales . Saltador. ISBN 978-94-017-7188-7.
- Conte, SD y deBoor, C. (1972). Análisis numérico elemental . McGraw-Hill, Nueva York. ISBN 0070124469.
- Este artículo incorpora texto del artículo Tridiagonal_matrix_algorithm _-_ TDMA_ (Thomas_algorithm) en CFD-Wiki que está bajo la licencia GFDL .
- Presione, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Sección 2.4" . Recetas numéricas: el arte de la informática científica (3ª ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-88068-8.