Метод прогонки

Система уравнений ${\displaystyle ~Ax=F}$  равносильна соотношению

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

Метод прогонки основывается на предположении, что искомые неизвестные связаны рекуррентным соотношением:

${\displaystyle x_{i}=\alpha _{i+1}x_{i+1}+\beta _{i+1},\,\!}$  где ${\displaystyle ~i=n-1,n-2,\dots ,1.\qquad \qquad (2)}$ 

Используя это соотношение, выразим x_i-1 и x_i через x_i+1 и подставим в уравнение (1):

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

где F_i — правая часть i-го уравнения. Это соотношение будет выполняться независимо от решения, если потребовать

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

Отсюда следует:

${\displaystyle {\begin{cases}\alpha _{i+1}={\frac {-B_{i}}{A_{i}\alpha _{i}+C_{i}}}\\\beta _{i+1}={\frac {F_{i}-A_{i}\beta _{i}}{A_{i}\alpha _{i}+C_{i}}}\end{cases}}}$ 

Из первого уравнения получим:

${\displaystyle {\begin{cases}\alpha _{2}={\frac {-B_{1}}{C_{1}}}\\\beta _{2}={\frac {F_{1}}{C_{1}}}\end{cases}}}$ 

После нахождения прогоночных коэффициентов ${\displaystyle \alpha }$  и ${\displaystyle \beta }$ , используя уравнение (2), получим решение системы. При этом,

${\displaystyle x_{i}={\alpha _{i+1}x_{i+1}+\beta _{i+1}},\!}$  ${\displaystyle i=n-1..1\,\!}$ 

${\displaystyle x_{n}={\frac {F_{n}-A_{n}\beta _{n}}{C_{n}+A_{n}\alpha _{n}}}}$ 

Другим способом объяснения существа метода прогонки, более близким к терминологии конечно-разностных методов и объясняющим происхождение его названия, является следующий: преобразуем уравнение (1) к эквивалентному ему уравнению

${\displaystyle ~A'x=F'\qquad \qquad (1')}$ 

c надиагональной (наддиагональной) матрицей

${\displaystyle A'={\begin{pmatrix}C_{1}'&B_{1}&0&0&\cdots &0&0\\0&C_{2}'&B_{2}&0&\cdots &0&0\\0&0&C_{3}'&B_{3}&\cdots &0&0\\\cdots &\cdots &\cdots &\cdots &\cdots &\cdots &\cdots \\\cdots &\cdots &\cdots &\cdots &\cdots &\cdots &\cdots \\\cdots &\cdots &\cdots &\cdots &0&C'_{n-1}&B_{n-1}\\0&0&0&0&\cdots &0&C_{n}'\end{pmatrix}}}$ .

Вычисления проводятся в два этапа. На первом этапе вычисляются компоненты матрицы ${\displaystyle ~C_{i}'}$  и вектора ${\displaystyle ~F'}$ , начиная с ${\displaystyle ~i=2}$  до ${\displaystyle ~i=n:}$ 

${\displaystyle ~C'_{1}=C_{1};}$ 

${\displaystyle C'_{i}=C_{i}-{\frac {A_{i}}{C'_{i-1}}}B_{i-1},}$ 

и

${\displaystyle ~F'_{1}=F_{1};}$ 

${\displaystyle F'_{i}=F_{i}-{\frac {A_{i}}{C'_{i-1}}}F'_{i-1}.}$ 

На втором этапе, для ${\displaystyle i=n,n-1,\dots ,1}$  вычисляется решение:

${\displaystyle x_{n}={\frac {F'_{n}}{C'_{n}}};}$ 

${\displaystyle x_{i}={\frac {F'_{i}-B_{i}x_{i+1}}{C'_{i}}}.}$ 

Такая схема вычисления объясняет также английский термин этого метода «shuttle».

Для применимости формул метода прогонки достаточно свойства строгого диагонального преобладания у матрицы A.

• Пример решения  (рус.)
• P. Ahuja. 1.1 Tridiagonal matrix algorithm (TDMA) // Introduction to Numerical Methods in Chemical Engineering. — PHI Learning Pvt. Ltd., 2010. — ISBN 9788120340183.  (англ.)
• А. А. Абрамов, В. Б. Андреев. О применении метода прогонки к нахождению периодических решений дифференциальных и разностных уравнений // Ж. вычисл. матем. и матем. физ.. — 1963. — Т. 3:2. — С. 377–381.
• The Thomas Algorithm  (англ.)