Algoritmo de solución de sistemas tridiagonales

El sistema de ecuaciones se puede escribir más sintéticamente de la siguiente manera: a Me x Me − 1 + b Me x Me + c Me x Me + 1 = d Me , {\displaystyle a_{I}x_{i-1} + b_{i}x_{i} + c_{I}x_{i + 1} = d_{I},\,\! } Donde a 1 = c y = 0 {\displaystyle a_{1} = c_{n}=0} este tipo de Matriz aparece comúnmente en la discretización de ecuaciones de Poisson 1D e interpolaciones Spline En álgebra lineal numérica, el algoritmo de solución de los sistemas tridiagonali, también conocido como el algoritmo de Thomas (por Llewellyn Thomas), es un método más eficiente de eliminación de Gauss que se puede utilizar para la solución de sistemas de ecuaciones en la forma A x = b {\displaystyle Ax = b} donde la matriz A {\displaystyle A} es tridiagonal.

Para estos sistemas, puede obtener la solución en O ( y ) {\displaystyle O (n)} operaciones en lugar de en O ( y 3 ) {\displaystyle O (n^{3})} del método de eliminación de Gauss. Un primer paso elimina la necesidad de a Me {\displaystyle a_{i}} y luego una sustitución hacia atrás acortada devuelve la solución. El algoritmo de Thomas no goza de estabilidad numérica en el caso general, pero esto se puede demostrar para varios casos especiales, como cuando la matriz es diagonalmente dominante (por fila o por columna) o definida como simétrica positiva. Para una discusión más precisa de la estabilidad del algoritmo de Thomas, ver Higham, teorema 9. 12. Si, en el caso general, se requiere estabilidad, es preferible la eliminación de acuerdo con Gauss con pivote parcial (GEPP).

El paso adelante es cambiar los coeficientes c Me {\displaystyle c_{i}} y d Me {\displaystyle d_{i}} de la siguiente manera (los nuevos coeficientes se denotan por el ápice): el segundo y último paso es la sustitución hacia atrás: el algoritmo en el lenguaje VBA se presenta aquí en una versión que sobrescribe los vectores de los coeficientes.

En algunos casos es necesario resolver una versión ligeramente diferente del sistema tridiagonal: en este caso, la fórmula de Sherman - Morrison permite evitar operaciones adicionales del algoritmo de Gauss y usar también en este caso el algoritmo de Thomas. El método requiere que corrija una versión modificada y no cíclica del sistema, tanto para la entrada como para un vector de corrección dispersa, y luego combine las soluciones. Calcular las dos soluciones al mismo tiempo es particularmente eficiente, ya que la parte delantera del algoritmo puede ser compartida por las dos operaciones. En otros casos, el sistema de ecuaciones podría ser tridiagonal en bloque (ver matriz de bloques), con submatrices más pequeñas dispuestas como elementos individuales del sistema matricial descrito anteriormente (por ejemplo en ecuaciones de Poisson 2D). Se han desarrollado algoritmos eficientes para llevar a cabo la eliminación de Gauss incluso para estos casos. El libro de texto de matemáticas numéricas de Quarteroni, Sacco y Saleri muestra una versión del algoritmo que reemplaza algunas de las divisiones con multiplicaciones, con el fin de mejorar la eficiencia del algoritmo en algunas arquitecturas de computación. Se han publicado solucionadores de sistemas tridiagonales paralelos para diferentes arquitecturas, incluidas las GPU. Para una extensa discusión de los Algoritmos de solución paralela de sistemas tridiagonales y tridiagonales de bloques, ver Gallopoulos et al.

Álgebra lineal numérica

Español de Gerschgorin

En matemáticas, los teoremas de Gershgorin son algunos teoremas sobre la localización de valores propios de una matriz en el campo complejo. Su nombre se debe a...

Matriz dispersa

En matemáticas, especialmente en análisis numérico, una matriz dispersa es una matriz cuyos valores son casi todos iguales a cero. Conceptualmente, sparsity se ...

Teorema

Combinatoria

Matriz

Esta página se basa en el artículo de Wikipedia: Fuente, Autores, Licencia Creative Commons Reconocimiento-CompartirIgual.
This page is based on the Wikipedia article: Source, Authors, Creative Commons Attribution-ShareAlike License.
contactos
Política de privacidad , Descargos de responsabilidad