Método de barrido

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 23 de noviembre de 2021; la verificación requiere 1 edición .

El método de barrido ( ing. algoritmo de matriz tridiagonal ) o el algoritmo de Thomas ( ing. algoritmo de Thomas ) se utiliza para resolver sistemas de ecuaciones lineales de la forma , donde es una matriz tridiagonal . Es una variante del método de eliminación secuencial de incógnitas [1] . El método de barrido fue propuesto por I. M. Gelfand y O. V. Lokutsievskii (en 1952 [2] ; publicado en 1960 [3] y 1962 [4] ), así como de forma independiente por otros autores [5] . $Ax=F$ $A$

Descripción del método

El sistema de ecuaciones es equivalente a la relación $Ax=F$

A_{i}x_{i-1}+B_{i}x_{i}+C_{i}x_{i+1}=F_{i}.\qquad \qquad (1)

El método de barrido se basa en la suposición de que las incógnitas requeridas están relacionadas por la relación recursiva:

x_{i}=\alpha _{i+1}x_{i+1}+\beta _{i+1},

dónde

i=n-1,n-2,\dots,1.\qquad \qquad (2)

Usando esta relación, expresamos y reemplazamos en la ecuación (1): $x_{{i-1}}$ $x_{yo}$ $x_{{i+1}}$

\left(A_{i}\alpha _{i}\alpha _{i+1}+B_{i}\alpha _{i+1}+C_{i}\right)x_{i+1 }+A_{i}\alpha _{i}\beta _{i+1}+A_{i}\beta _{i}+B_{i}\beta _{i+1}-F_{i}= 0

donde F i es el lado derecho de la i -ésima ecuación. Esta relación se mantendrá independientemente de la solución, si necesita

{\begin{casos}A_{i}\alpha _{i}\alpha _{i+1}+B_{i}\alpha _{i+1}+C_{i}=0\\A_ {i}\alpha _{i}\beta _{i+1}+A_{i}\beta _{i}+B_{i}\beta _{i+1}-F_{i}=0\end {casos}}

Esto implica:

{\begin{casos}\alpha _{i+1}={\dfrac {-C_{i}}{A_{i}\alpha _{i}+B_{i}}}\\\beta _{i+1}={\dfrac {F_{i}-A_{i}\beta_{i}}{A_{i}\alpha_{i}+B_{i}}}\end{casos} }

De la primera ecuación obtenemos:

{\begin{casos}\alpha _{2}=-C_{1}/B_{1}\\\beta _{2}=F_{1}/B_{1}\end{casos})

Luego de encontrar los coeficientes de barrido y , usando la ecuación (2), obtenemos la solución del sistema. Donde, $\alfa$ $\beta$

x_{i}={\alpha _{i+1}x_{i+1}+\beta _{i+1)),

i=n-1\ldots 1

x_{n}={\frac {F_{n}-A_{n}\beta _{n}}{B_{n}+A_{n}\alpha _{n}}}

Otra forma de explicar la esencia del método de barrido, más cercana a la terminología de los métodos de diferencias finitas y explicando el origen de su nombre, es la siguiente: transformamos la ecuación (1) en su ecuación equivalente

A'x=F'\qquad \qquad (1')

con una matriz sobrediagonal (overdiagonal)

A'={\begin{pmatrix}B_{1}'&C_{1}&0&0&\puntos &0&0\\0&B_{2}'&C_{2}&0&\puntos &0&0\\0&0&B_{3}'&C_{3 }&\puntos &0&0\\\puntos &\puntos &\puntos &\puntos &\puntos &\puntos &\puntos \\\puntos &\puntos &\puntos &\puntos &\puntos &\puntos &\puntos \ \\puntos &\puntos &\puntos &\puntos &0&B'_{n-1}&C_{n-1}\\0&0&0&0&\puntos &0&B_{n}'\end{pmatrix}}

Los cálculos se realizan en dos etapas. En la primera etapa, se calculan los componentes de la matriz y el vector , comenzando de a $B_{i}'$ $F'$ $yo=2$ ${\ estilo de visualización i = n:}$

B'_{1}=B_{1};

B'_{i}=B_{i}-{\frac {A_{i}}{B'_{i-1}}}C_{i-1},

F'_{1}=F_{1};

F'_{i}=F_{i}-{\frac {A_{i}}{B'_{i-1}}}F'_{i-1}.

En la segunda etapa, para la solución se calcula: $i=n, n-1, \puntos, 1$

x_{n}={\frac{F'_{n}}{B'_{n}}};

x_{i}={\frac{F'_{i}-C_{i}x_{i+1}}{B'_{i}}}.

Este esquema de cálculo también explica el término en inglés para este método[ aclarar ] "lanzadera" .

Para que las fórmulas del método de barrido sean aplicables, es suficiente la propiedad de dominancia diagonal de la matriz A.

Ejemplo de uso

Las matrices tridiagonales, para las que se utiliza el método de barrido simple, suelen surgir al resolver ecuaciones diferenciales de dos variables independientes mediante el método de diferencias finitas . Considere, por ejemplo, la solución de una ecuación de calor unidimensional lineal :

${\frac {\parcial u}{\parcial t}}-a^{2}{\frac {\parcial ^{2}u}{\parcial x^{2}}}=f(x, t),$

donde es una constante positiva (el número es la difusividad térmica ) y es una función de las fuentes de calor [6] . La función deseada establece la temperatura en el punto con la coordenada en el momento del tiempo . $a$ $un ^ 2$ $f(x,t)$ ${\ estilo de visualización u = u (x, t)}$ $X$ $t$

Discreticemos esta ecuación en una cuadrícula uniforme con un paso espacial y un paso de tiempo . En este caso, las funciones continuas y se reemplazan por sus contrapartes discretas y , y las derivadas espaciales y temporales se reemplazan por diferencias finitas: $h$ $\tau$ $tu(x, t)$ $f(x,t)$ $u_{i}^{j}=u(x_{i},t_{j})$ $f_{i}^{j}=f(x_{i},t_{j})$

$\left.{\frac {\parcial u}{\parcial t))\right|_{t=t_{j))\to {\frac {u(x,t_{j+1})- u(x,t_{j})}{\tau )),$

$\left.{\frac {\parcial ^{2}u}{\parcial x^{2}}}\right|_{x=x_{i}}\to {\frac {u(x_{ i+1},t)-2u(x_{i},t)+u(x_{i-1},t)}{h^{2}}}.$

Se considerarán conocidos los valores de cantidades sobre la capa (obtenidos como resultado de la discretización de las condiciones iniciales, o de la solución de la ecuación en el paso de tiempo anterior). Consideremos además una aproximación implícita en el tiempo, en la que los valores de las fuentes de calor y los flujos de calor se toman de la siguiente capa de tiempo . El correspondiente sistema de ecuaciones algebraicas lineales para valores desconocidos tiene la forma ${\ estilo de visualización t^{j}}$ ${\ estilo de visualización t^{j+1}}$ $u_{i}^{j+1}$

${\frac {u_{i}^{j+1}-u_{i}^{j}}{\tau }}-a^{2}{\frac {u_{i+1}^{ j+1}-2u_{i}^{j+1}+u_{i-1}^{j+1}}{h^{2}}}=f_{i}^{j+1}.$

Pasando las cantidades conocidas al lado derecho, multiplicando por y agrupando los coeficientes, llevamos la SLAE a la forma final $\tau$

${\frac {-a^{2}\tau }{h^{2}}}u_{i-1}^{j+1}+\left(1+2{\frac {a^{ 2}\tau }{h^{2}}}\right)u_{i}^{j+1}+{\frac {-a^{2}\tau }{h^{2}}}u_{ i+1}^{j+1}=u_{i}^{j}+\tau f_{i}^{j+1}.$

La forma de la matriz de coeficientes para los puntos finales de la cuadrícula de diferencia está determinada por las condiciones de contorno y se deriva por separado. La presencia de dominancia diagonal en la matriz de coeficientes garantiza la estabilidad del método de barrido a la hora de resolver esta SLAE.

Generalización del método de barrido

A. A. Abramov en 1963 propuso el llamado método de barrido periódico, que permite resolver SLAE con una matriz en la que todos los elementos de esquina , , , son distintos de cero . Para resolver la SLAE, los coeficientes de barrido directo se calculan en el primer paso: ${\ estilo de visualización A_ {11}}$ ${\ estilo de visualización A_ {1N}}$ ${\ estilo de visualización A_ {N1}}$ $A_{NN}$

$\alpha _{1}=c_{0}/b_{0},\;\beta _{1}=-\varphi _{0}/b_{0},\;\gamma _{1} =a_{0}/b_{0};$

$\alpha _{k+1}={\dfrac {c_{k}}{b_{k}-\alpha _{k}a_{k}}},\;\beta _{k+1} ={\dfrac {a_{k}\beta_{k}-f_{k}}{b_{k}-\alpha_{k}a_{k}}},\;\gamma_{k+1} ={\dfrac {a_{k}\gamma _{k}}{b_{k}-\alpha _{k}a_{k}}}.$

A continuación, se realiza un barrido hacia atrás (de derecha a izquierda) para obtener los coeficientes

$\mu _{N}=-{\dfrac {c_{N}}{a_{N}(\alpha _{N}+\gamma _{N})-b_{N}}},\; \nu _{N}={\dfrac {f_{N}-a_{N}\beta _{N}}{a_{N}(\alpha _{N}+\gamma _{N})-b_{ NORTE}}};$

$\mu _{n-1}=\alpha _{n}\mu _{n}+\gamma _{n}\mu _{N},\;\nu _{n-1}=\ beta _{n}+\alfa _{n}\nu _{n}+\gamma _{n}\nu _{N}.$

A continuación, el valor deseado del vector se calcula mediante las fórmulas . ${\vec{y}}$

$y_{0}={\dfrac {\nu _{0}}{1-\mu _{0}}};$

$y_{n-1}=\alpha _{n}(\mu _{n}y_{0}+\nu _{n})+\beta _{n}+\gamma _{n}( \mu _{N}y_{0}+\nu _{N}).$

Enlaces

Ejemplo de solución
P. Ahuja. 1.1 Algoritmo de matriz tridiagonal (TDMA) // Introducción a los Métodos Numéricos en Ingeniería Química. — PHI Learning Pvt. Ltd., 2010. - ISBN 9788120340183 . (Inglés)
A. A. Abramov, V. B. Andreev. Sobre la aplicación del método de barrido para encontrar soluciones periódicas de ecuaciones diferenciales y en diferencias // Zh. Vychisl. Matemáticas. y estera física.- 1963.- T. 3:2 . - S. 377-381 .
El algoritmo de Thomas
Fedorenko R. P. Introducción a la Física Computacional / Ed. A. I. Lobanova. - Dolgoprudny: Intellect Publishing House, 2008. - 504 p. - ISBN 978-5-91559-011-2 .
Berezin IS , Zhidkov N.P. Métodos de cálculo. - M. : Fizmatlit, 1960. - T. 2. - 620 p.
Samarsky A.A. , Gulin A.V. Métodos numéricos. — M .: Nauka, 1989. — 432 p. — ISBN 5-02-013996-3 .
Godunov S. K. , Ryabenky V.S. Introducción a la teoría de la diferencia de esquemas. — M .: Fizmatgiz, 1962.

Notas

↑ "El método de barrido... es una variante del método de eliminación secuencial de incógnitas" (Samarsky, Gulin, p. 45).
↑ "El barrido, como método estable para resolver problemas de valores límite con una gran cantidad de parámetros, fue presentado y estudiado por I. M. Gelfand y O. V. Lokutsievskii en 1952" (Fedorenko, pág. 500).
↑ Berezin, Zhidkov, pág. 387, 506 (con referencia a un manuscrito inédito de Gelfand y Lokutsievskii).
↑ Apéndice del libro de Godunov y Ryabenky.
↑ “El barrido fue “descubierto” por I. M. Gelfand y O. V. Lokutsievskii en 1952 precisamente como una aplicación del algoritmo establecido en el libro de texto escolar de álgebra. Su mérito es el establecimiento de la estabilidad y el uso del algoritmo en la resolución de problemas complejos. Aproximadamente al mismo tiempo, en relación con un trabajo similar, otros autores propusieron el barrido” (Fedorenko, p. 501).
↑ Tikhonov A.N., Samarsky A.A. Ecuaciones de física matemática. - cap. III, § 1. - Cualquier edición.

Métodos para resolver SLAE
Métodos directos	método matricial método de Gauss Método de Gauss-Jordan método Cramer descomposición LU Descomposición de Cholesky método de barrido
Métodos iterativos	método jacobi Método de Gauss-Seidel método de iteración método de relajación método de gradiente conjugado Método de gradiente biconjugado Método de gradiente biconjugado estabilizado
General	matriz inversa Métodos de proyección para resolver SLAE preacondicionamiento