WikiSort.ru - Не сортированное

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

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

Система уравнений ${\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.

Пример использования

В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 14 апреля 2016 года.

Пусть дано уравнение :

${\displaystyle C_{xx}(x)-e^{C(x)}+r(x)=0}$

Обозначим этот оператор за L.

Можно добавить новую переменную t и добавить на неё уравнение.

${\displaystyle (LC)_{t}=-LC}$

Тогда

${\displaystyle -C_{xxt}+e^{C}C_{t}=C_{xx}-e^{C}+r}$

И разностная схема будет

${\displaystyle C_{m+1}^{n}+C_{m-1}^{n}-C_{m}^{n}(2+h^{2}e^{C_{m}^{n-1}})=e^{C_{m}^{n-1}}(1-h^{2}C_{m}^{n-1})+C_{m+1}^{n-1}+C_{m-1}^{n-1}-C_{m}^{n-1}+dt*((C_{m+1}^{n-1}+C_{m-1}^{n-1}-C_{m}^{n-1})/h^{2}-r_{m}),}$

где h, dt - шаги по сетке. решая её при больших конечных t мы получим решение начального уравнения. Этот метод называется методом инвариантного погружения.

Ссылки

Имеется викиучебник по теме
«Программные реализации метода прогонки»

• Пример решения
• 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.

Примечания

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