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

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

${\displaystyle A_{i}x_{i-1}+B_{i}x_{i}+C_{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)}$

Используя это соотношение, выразим ${\displaystyle x_{i-1}}$ и ${\displaystyle x_{i}}$ через ${\displaystyle x_{i+1}}$ и подставим в уравнение (1):

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle B'_{1}=B_{1};}$

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

и

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

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

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

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

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

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

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

Трёхдиагональные матрицы, для обращения которых применяется метод простой прогонки, нередко возникают при решении дифференциальных уравнений двух независимых переменных методом конечных разностей. Рассмотрим для примера решение линейного одномерного уравнения теплопроводности:

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

где ${\displaystyle a}$ — положительная константа (число ${\displaystyle a^{2}}$ является коэффициентом температуропроводности) и ${\displaystyle f(x,t)}$ — функция тепловых источников[6]. Искомая функция ${\displaystyle u=u(x,t)}$ задает температуру в точке с координатой ${\displaystyle x}$ в момент времени ${\displaystyle t}$.

Проведём дискретизацию этого уравнения на равномерной сетке с пространственным шагом ${\displaystyle h}$ и временным ${\displaystyle \tau }$. При этом непрерывные функции ${\displaystyle u(x,t)}$ и ${\displaystyle f(x,t)}$ заменяются на их дискретные аналоги ${\displaystyle u_{i}^{j}=u(x_{i},t_{j})}$ и ${\displaystyle f_{i}^{j}=f(x_{i},t_{j})}$, а пространственная и временная производная — на конечные разности:

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

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

Значения величин на слое ${\displaystyle t^{j}}$ будем считать известными (полученными в результате дискретизации начальных условий, либо решения уравнения на предыдущем временном шаге). Рассмотрим далее неявную по времени аппроксимацию, в которой значения источников тепла и тепловых потоков берутся со следующего временного слоя ${\displaystyle t^{j+1}}$. Соответствующая система линейных алгебраических уравнений для неизвестных значений ${\displaystyle u_{i}^{j+1}}$ имеет вид

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

Перенеся известные величины в правую часть, домножив на ${\displaystyle \tau }$ и сгруппировав коэффициенты, приведём СЛАУ к окончательному виду

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

Вид матрицы коэффициентов для конечных точек разностной сетки определяется граничными условиями и выводится отдельно. Наличие диагонального преобладания у матрицы коэффициентов гарантирует устойчивость метода прогонки при решении им данной СЛАУ.

• Пример решения
• 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 (англ.)
• Федоренко Р.П. Введение в вычислительную физику / Под ред. А.И.Лобанова. — Долгопрудный: Издательский дом «Интеллект», 2008. — 504 с. — ISBN 978-5-91559-011-2.
• Березин И.С., Жидков Н.П. Методы вычислений. — М.: Физматлит, 1960. — Т. 2. — 620 с.
• Самарский А.А., Гулин А.В. Численные методы. — М.: Наука, 1989. — 432 с. — ISBN 5-02-013996-3.
• Годунов С.К., Рябенький В.С. Введение в теорию разностных схем. — М.: Физматгиз, 1962.