Метод прогонки ( англ. tridiagonal matrix algorithm ) или алгоритм Томаса ( англ. Thomas algorithm ) используется для решения систем линейных уравнений вида ${\displaystyle Ax=F}$ , где ${\displaystyle A}$ — трёхдиагональная матрица . Представляет собой вариант метода последовательного исключения неизвестных . Метод прогонки был предложен И. М. Гельфандом и О. В. Локуциевским (в 1952 году ; опубликовано в 1960 и 1962 годах), а также независимо другими авторами .

Описание метода

Система уравнений ${\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» ^{[ источник не указан 1213 дней ]} .

Для применимости формул метода прогонки достаточно свойства диагонального преобладания у матрицы 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)}$ — функция тепловых источников . Искомая функция ${\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}.}$

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

Обобщение метода прогонки

А. А. Абрамовым в 1963 году предложен так называемый метод периодической прогонки, который позволяет решать СЛАУ с матрицей, в которой ненулевыми являются все угловые элементы ${\displaystyle A_{11}}$ , ${\displaystyle A_{1N}}$ , ${\displaystyle A_{N1}}$ , ${\displaystyle A_{NN}}$ . Для решения СЛАУ на первом шаге рассчитываются коэффициенты прямой прогонки:

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

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

Далее выполняется обратная прогонка (справа налево) для получения коэффициентов

${\displaystyle \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_{N}}};}$

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

Далее вычисляют искомое значение вектора ${\displaystyle {\vec {y}}}$ по формулам

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

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

Ссылки

• P. Ahuja. // Introduction to Numerical Methods in Chemical Engineering. — PHI Learning Pvt. Ltd., 2010. — ISBN 9788120340183 . (англ.)
• А. А. Абрамов, В. Б. Андреев. // Ж. вычисл. матем. и матем. физ.. — 1963. — Т. 3:2 . — С. 377—381 .
• (англ.)
• Федоренко Р.П. Введение в вычислительную физику / Под ред. А.И.Лобанова. — Долгопрудный: Издательский дом «Интеллект», 2008. — 504 с. — ISBN 978-5-91559-011-2 .
• Березин И.С. , Жидков Н.П. Методы вычислений. — М. : Физматлит, 1960. — Т. 2. — 620 с.
• Самарский А.А. , Гулин А.В. Численные методы. — М. : Наука, 1989. — 432 с. — ISBN 5-02-013996-3 .
• Годунов С.К. , Рябенький В.С. Введение в теорию разностных схем. — М. : Физматгиз, 1962.

Примечания

Для улучшения этой статьи желательно : Найти и оформить в виде сносок ссылки на независимые авторитетные источники , подтверждающие написанное . Оформить список литературы. После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.