Математика / Начала анализа

Метод прогонки для трёхдиагональной системы

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

Опубликовано: 22 октября 2026 г.Обновлено: 22 октября 2026 г.

Формула

c_i x_{i-1}+a_i x_i+b_i x_{i+1}=d_i;\quad \alpha_i=-\frac{b_i}{a_i+c_i\alpha_{i-1}},\;\beta_i=\frac{d_i-c_i\beta_{i-1}}{a_i+c_i\alpha_{i-1}}

Схема Прогонка: прямой ход и обратная подстановка

Прогонка завершает решение прямым и обратным проходами, без повторных итераций.

Обозначения

$c_i$: поддиагональный коэффициент при x_(i−1), как у строки
$a_i$: главный диагональный коэффициент, как у строки
$b_i$: наддиагональный коэффициент при x_(i+1), как у строки
$α_i, β_i$: коэффициенты связи на прямом ходе, α безразмерен, β как x

Условия применения

Матрица должна быть трёхдиагональной, а все знаменатели прямого хода a_i+c_iα_(i−1) — ненулевыми. На границах отсутствующие c_1 и b_n обычно принимают равными нулю после правильной записи граничных условий. Строгая диагональная доминантность — удобное достаточное условие отсутствия нулевых ведущих знаменателей, но проверка конкретных знаменателей всё равно полезна.

Ограничения

Алгоритм не применим к общей плотной системе без изменения задачи: появление дальнего ненулевого коэффициента нарушает вывод. Малый знаменатель усиливает округление и требует устойчивой реализации с проверкой. При изменении одной строки нельзя без анализа считать старые α и β пригодными. Метод решает одну структуру быстро, но не даёт автоматически оценку физической корректности сеточной модели или её граничных условий.

Подробное объяснение

Трёхдиагональная система устроена как цепочка: i-е уравнение связывает только x_(i−1), x_i и x_(i+1). Прогонка использует это локальное устройство и на прямом ходе представляет каждую текущую неизвестную как x_i=α_i x_(i+1)+β_i. Подстановка такой связи в следующую строку не создаёт дальних коэффициентов, поэтому вычисления остаются линейными по числу строк.

Для первой строки при c_1=0 получается α_1=−b_1/a_1 и β_1=d_1/a_1. Далее в i-й строке заменяют x_(i−1) выражением из предыдущего шага, собирают коэффициент при x_i и делят на a_i+c_iα_(i−1). После прямого хода последняя строка сразу даёт x_n, а обратный ход использует x_i=α_i x_(i+1)+β_i.

Это специализированное исключение Гаусса без заполнения матрицы вне ленты. Для плотной матрицы общее исключение Гаусса требует порядка n³ арифметических операций, тогда как трёхдиагональная структура даёт прогонке порядок n. В FNC Book трёхдиагональная матрица определяется как матрица с ненулевыми элементами на главной и двух соседних диагоналях, что ровно соответствует предпосылке прогонки.

В расчёте важно вести индексы: коэффициент c относится к левому соседу, b — к правому. Полезная проверка после обратного хода — подставить найденный вектор во все исходные строки, а не только убедиться, что последняя формула выполнена. Это также сразу выявляет ошибку знака в α.

Как пользоваться формулой

Запишите систему в едином порядке c_i x_(i−1)+a_i x_i+b_i x_(i+1)=d_i и задайте отсутствующие граничные коэффициенты нулём.
Вычислите α_1 и β_1, затем последовательно формируйте знаменатель a_i+c_iα_(i−1), проверяя его на нуль.
На последней строке найдите x_n из сформированной связи, не подставляя несуществующий x_(n+1).
Пройдите назад по формуле x_i=α_i x_(i+1)+β_i и проверьте невязку каждой исходной строки.

Историческая справка

В численных расчётах XX–XXI веков трёхдиагональные системы стали типовой вычислительной формой в разностном решении одномерных краевых задач: каждая внутренняя точка взаимодействует с двумя соседями. Современная литература называет специализированный прямой алгоритм Thomas algorithm; русское название «прогонка» передаёт прямой и обратный проходы по цепочке. FNC Book определяет трёхдиагональную матрицу через главную и две соседние диагонали, что объясняет предпосылку алгоритма.

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

Историческая линия формулы

Английское имя Thomas algorithm и русское «метод прогонки» обозначают специализированное исключение для трёхдиагональной системы. В лекциях Беньямина Неты алгоритм разобран в контексте численного решения дифференциальных уравнений. Соглашения о знаках коэффициентов могут различаться при сохранении той же последовательности исключения.

Пример

Решим −x_1+2x_2−x_3=0, −x_2+2x_3=4 с первой строкой 2x_1−x_2=0. Здесь a=(2,2,2), b=(−1,−1,0), c=(0,−1,−1), d=(0,0,4). α_1=1/2, β_1=0. Для второй строки знаменатель 2−1·1/2=3/2, поэтому α_2=−(−1)/(3/2)=2/3 и β_2=0. В третьей: знаменатель 2−1·2/3=4/3, β_3=(4−(−1)·0)/(4/3)=3, значит x_3=3. Обратный ход: x_2=(2/3)·3=2, x_1=(1/2)·2=1. Подстановка даёт 2−2=0, −1+4−3=0, −2+6=4. Все три исходные строки проверены отдельно, а не выведены из преобразованной системы; это сохраняет контроль знаков и правой части.

Частая ошибка

Не меняйте местами b_i и c_i: они стоят справа и слева от главной диагонали и входят в разные места формулы. Не используйте α_n, если в последней строке нет x_(n+1); финальное значение получают отдельно. Ошибка знака в α_i особенно коварна: при записи x_i=α_i x_(i+1)+β_i перед b_i стоит минус. Не прячьте нулевой знаменатель заменой на маленькое число: это сигнал изменить постановку или применить устойчивый вариант.

Практика

Задачи с решением

Первая связь

Условие. Для 3x_1−x_2=6 найдите α_1 и β_1 в записи x_1=α_1x_2+β_1.

Решение. 3x_1=6+x_2, поэтому x_1=(1/3)x_2+2.

Ответ. α_1=1/3, β_1=2.

Обратный ход

Условие. Если α_2=0,4, β_2=1,2 и x_3=5, найдите x_2.

Решение. x_2=0,4·5+1,2=2+1,2.

Ответ. 3,2.

Дополнительные источники

https://faculty.nps.edu/bneta/npde.pdf
https://fncbook.com/structure/
https://fncbook.com/linear-systems/

Связанные формулы

Математика

Прямой ход метода Гаусса

$R_i\leftarrow R_i-\frac{a_{ik}}{a_{kk}}R_k$

Прямой ход метода Гаусса зануляет коэффициенты под ведущими элементами. В результате система приводится к ступенчатому виду, из которого решение находят обратной подстановкой.

Математика

Обратная подстановка в методе Гаусса

$x_i=\frac{b'_i-\sum_{j=i+1}^{n}u_{ij}x_j}{u_{ii}}$

Обратная подстановка находит неизвестные после прямого хода метода Гаусса. Она идет снизу вверх по ступенчатой системе: сначала последняя ведущая переменная, затем предыдущие.

Математика

Метод Гаусса-Жордана

$\left[A\mid b\right]\sim\left[I\mid x\right]$

Метод Гаусса-Жордана продолжает метод Гаусса до приведенного ступенчатого вида. Если система имеет единственное решение, расширенная матрица превращается в [I|x], и ответ читается сразу.

Математика

Число обусловленности для задачи МНК

$\kappa_2(A^\top A)=\frac{\sigma_{\max}^2}{\sigma_{\min}^2}=\kappa_2(A)^2.$

При переходе к нормальным уравнениям число обусловленности фактически возводится в квадрат, поэтому ошибки округления и шум в данных могут заметно усилиться.