Русская Википедия:Метод прогонки
Метод прогонки (Шаблон:Lang-en) или алгоритм Томаса (Шаблон:Lang-en) используется для решения систем линейных уравнений вида <math>Ax=F</math>, где <math>A</math> — трёхдиагональная матрица. Представляет собой вариант метода последовательного исключения неизвестных[1]. Метод прогонки был предложен И. М. Гельфандом и О. В. Локуциевским (в 1952 году[2]; опубликовано в 1960[3] и 1962[4] годах), а также независимо другими авторами[5].
Описание метода
Система уравнений <math>Ax=F</math> равносильна соотношению
- <math>A_{i}x_{i-1}+B_{i}x_{i}+C_{i}x_{i+1} = F_{i}.\qquad\qquad(1)</math>
Метод прогонки основывается на предположении, что искомые неизвестные связаны рекуррентным соотношением:
- <math>x_i = \alpha_{i+1}x_{i+1} + \beta_{i+1},</math> где <math>i=n-1,n-2,\dots,1.\qquad\qquad(2)</math>
Используя это соотношение, выразим <math>x_{i-1}</math> и <math>x_i</math> через <math>x_{i+1}</math> и подставим в уравнение (1):
- <math>\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</math>,
где Fi — правая часть i-го уравнения. Это соотношение будет выполняться независимо от решения, если потребовать
- <math>\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}</math> Отсюда следует:
- <math> \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}</math> Из первого уравнения получим:
- <math>\begin{cases} \alpha_2 = -C_1 / B_1 \\
\beta_2 = F_1 / B_1 \end{cases}</math> После нахождения прогоночных коэффициентов <math>\alpha</math> и <math>\beta</math>, используя уравнение (2), получим решение системы. При этом,
- <math>x_i = {\alpha_{i+1}x_{i+1} + \beta_{i+1}},</math> <math>i=n-1 \ldots 1</math>
- <math> x_n = \frac{F_n-A_n\beta_n}{B_n+A_n\alpha_n} </math>
Другим способом объяснения существа метода прогонки, более близким к терминологии конечно-разностных методов и объясняющим происхождение его названия, является следующий: преобразуем уравнение (1) к эквивалентному ему уравнению
- <math>A' x=F'\qquad\qquad(1')</math>
c надиагональной (наддиагональной) матрицей
- <math>
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} </math>.
Вычисления проводятся в два этапа. На первом этапе вычисляются компоненты матрицы <math>B_i'</math> и вектора <math>F'</math>, начиная с <math>i=2</math> до <math>i=n:</math>
- <math>B'_1=B_1;</math>
- <math>B'_i=B_i-\frac{A_i}{B'_{i-1}} C_{i-1},</math>
и
- <math>F'_1=F_1;</math>
- <math>F'_i=F_i-\frac{A_i}{B'_{i-1}} F'_{i-1}.</math>
На втором этапе, для <math>i=n, n-1, \dots, 1</math> вычисляется решение:
- <math>x_n=\frac{F'_n}{B'_n};</math>
- <math>x_i=\frac{F'_i-C_i x_{i+1}}{B'_i}.</math>
Такая схема вычисления объясняет также английский термин этого методаШаблон:Прояснить «shuttle»Шаблон:Нет АИ.
Для применимости формул метода прогонки достаточно свойства диагонального преобладания у матрицы A.
Пример использования
Трёхдиагональные матрицы, для обращения которых применяется метод простой прогонки, нередко возникают при решении дифференциальных уравнений двух независимых переменных методом конечных разностей. Рассмотрим для примера решение линейного одномерного уравнения теплопроводности:
<math>\frac{\partial u}{\partial t} - a^2 \frac{\partial^2 u}{\partial x^2}=f(x,t), </math>
где <math>a</math> — положительная константа (число <math>a^2</math> является коэффициентом температуропроводности) и <math>f(x,t)</math> — функция тепловых источников[6]. Искомая функция <math>u = u(x,t)</math> задает температуру в точке с координатой <math>x</math> в момент времени <math>t</math>.
Проведём дискретизацию этого уравнения на равномерной сетке с пространственным шагом <math>h</math> и временным <math>\tau</math>. При этом непрерывные функции <math>u(x,t)</math> и <math>f(x,t)</math> заменяются на их дискретные аналоги <math>u_i^j = u(x_i,t_j)</math> и <math>f_i^j = f(x_i,t_j)</math>, а пространственная и временная производная — на конечные разности:
<math>\left.\frac{\partial u}{\partial t}\right|_{t=t_j} \to \frac{u(x,t_{j+1}) - u(x,t_j)}{\tau},</math>
<math>\left.\frac{\partial^2 u}{\partial x^2}\right|_{x=x_i} \to \frac{u(x_{i+1},t) - 2 u(x_i,t) + u(x_{i-1},t)}{h^2}. </math>
Значения величин на слое <math>t^j</math> будем считать известными (полученными в результате дискретизации начальных условий, либо решения уравнения на предыдущем временном шаге). Рассмотрим далее неявную по времени аппроксимацию, в которой значения источников тепла и тепловых потоков берутся со следующего временного слоя <math>t^{j+1}</math>. Соответствующая система линейных алгебраических уравнений для неизвестных значений <math>u_i^{j+1}</math> имеет вид
<math>\frac{u_i^{j+1} - u_i^j}{\tau} - a^2 \frac{u_{i+1}^{j+1} - 2 u_i^{j+1} + u_{i-1}^{j+1}}{h^2} = f_i^{j+1}. </math>
Перенеся известные величины в правую часть, домножив на <math>\tau</math> и сгруппировав коэффициенты, приведём СЛАУ к окончательному виду
<math>\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}. </math>
Вид матрицы коэффициентов для конечных точек разностной сетки определяется граничными условиями и выводится отдельно. Наличие диагонального преобладания у матрицы коэффициентов гарантирует устойчивость метода прогонки при решении им данной СЛАУ.
Обобщение метода прогонки
А. А. Абрамовым в 1963 году предложен так называемый метод периодической прогонки, который позволяет решать СЛАУ с матрицей, в которой ненулевыми являются все угловые элементы <math>A_{1 1}</math>, <math>A_{1 N}</math>, <math>A_{N 1}</math>, <math>A_{N N}</math>. Для решения СЛАУ на первом шаге рассчитываются коэффициенты прямой прогонки:
<math>\alpha _1 = c_0 / b_0, \; \beta _1 = -\varphi _0/b_0,\; \gamma _1 = a_0/b_0;</math>
<math>\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}.</math>
Далее выполняется обратная прогонка (справа налево) для получения коэффициентов
<math>\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};</math>
<math>\mu _{n-1} = \alpha _n \mu _n +\gamma _n \mu _N,\; \nu _{n-1} = \beta _{n} + \alpha _n \nu _n +\gamma _n \nu _N.</math>
Далее вычисляют искомое значение вектора <math>\vec{y}</math> по формулам
<math>y_0 = \dfrac{\nu _0}{1- \mu _0};</math>
<math>y_{n-1} = \alpha _n (\mu _n y_0 +\nu _n)+ \beta _n+\gamma _n (\mu_N y_0 + \nu _N).</math>
Ссылки
- Пример решения
- Шаблон:КнигаШаблон:Ref-en
- Шаблон:Статья
- The Thomas AlgorithmШаблон:Ref-en
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
- Шаблон:Книга
Примечания
Шаблон:Rq Шаблон:Методы решения СЛАУ
- ↑ «Метод прогонки … представляет собой вариант метода последовательного исключения неизвестных» (Самарский, Гулин, с. 45).
- ↑ «Прогонка, как устойчивый метод решения краевых задач с большим числом параметров, была введена и исследована И. М. Гельфандом и О. В. Локуциевским в 1952 г.» (Федоренко, с. 500).
- ↑ Березин, Жидков, с. 387, 506 (со ссылкой на неопубликованную рукопись Гельфанда и Локуциевского).
- ↑ В приложении к книге Годунова и Рябенького.
- ↑ «Прогонка была „открыта“ И. М. Гельфандом и О. В. Локуциевским в 1952 г. именно как применение алгоритма, изложенного в школьном учебнике алгебры. Их заслугой является установление устойчивости и использование алгоритма при решении сложных задач. Примерно в то же время в связи с аналогичными работами прогонка была предложена другими авторами» (Федоренко, с. 501).
- ↑ Тихонов А. Н., Самарский А. А. Уравнения математической физики. — гл. III, § 1. — Любое издание.
