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

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

Постановка задачи

Метод прогонки предназначен для решения системы линейных уравнений вида:

\[ a_i x_{i-1} + b_i x_i + c_i x_{i+1} = d_i, \quad i = 1, 2, \dots, n \]

с граничными условиями, которые обычно задаются в виде \( x_0 = 0 \) и \( x_{n+1} = 0 \) или через модификацию коэффициентов. В матричной записи такая система имеет трёхдиагональную структуру:

\[ \begin{pmatrix} b_1 & c_1 & 0 & \dots & 0 \\ a_2 & b_2 & c_2 & \dots & 0 \\ 0 & a_3 & b_3 & \dots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & a_n & b_n \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ \vdots \\ x_n \end{pmatrix} = \begin{pmatrix} d_1 \\ d_2 \\ d_3 \\ \vdots \\ d_n \end{pmatrix} \]

Здесь \(a_i\), \(b_i\), \(c_i\) — известные коэффициенты, \(d_i\) — правая часть, \(x_i\) — искомые неизвестные. Для корректной работы метода требуется, чтобы \(b_i \neq 0\) и выполнялось условие диагонального преобладания: \(|b_i| \geq |a_i| + |c_i|\) хотя бы для одного \(i\) строго.

Алгоритм

Метод прогонки состоит из двух этапов: прямой прогонки (вычисление прогоночных коэффициентов) и обратной прогонки (нахождение неизвестных).

Прямая прогонка

На первом этапе для каждого \(i\) от 1 до \(n\) вычисляются прогоночные коэффициенты \(\alpha_i\) и \(\beta_i\) по рекуррентным формулам:

\[ \alpha_1 = \frac{c_1}{b_1}, \quad \beta_1 = \frac{d_1}{b_1} \]

\[ \alpha_i = \frac{c_i}{b_i - a_i \alpha_{i-1}}, \quad \beta_i = \frac{d_i - a_i \beta_{i-1}}{b_i - a_i \alpha_{i-1}}, \quad i = 2, 3, \dots, n \]

Эти коэффициенты представляют собой отношение соседних неизвестных: \(x_i = \alpha_i x_{i+1} + \beta_i\).

Обратная прогонка

На втором этапе, начиная с последнего уравнения, вычисляются значения неизвестных:

\[ x_n = \beta_n \]

\[ x_i = \alpha_i x_{i+1} + \beta_i, \quad i = n-1, n-2, \dots, 1 \]

В случае, если граничные условия заданы не как нулевые, а, например, \(x_0 = \gamma x_1 + \delta\) или \(x_{n+1} = \mu x_n + \nu\), формулы прямой прогонки модифицируются соответствующим образом.

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

Метод прогонки является устойчивым и даёт точное решение (с точностью до машинной арифметики) при выполнении следующих условий:

• Диагональное преобладание: \(|b_i| \geq |a_i| + |c_i|\) для всех \(i\), причём хотя бы для одного \(i\) неравенство строгое. Это гарантирует, что знаменатели в формулах не обращаются в ноль.
• Ненулевые диагональные элементы: \(b_i \neq 0\).
• Отсутствие вырожденности: матрица системы невырождена (определитель отличен от нуля).

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

Вычислительная сложность

Метод прогонки является одним из самых эффективных для трёхдиагональных систем. Его вычислительная сложность составляет \(O(n)\) — линейная по числу неизвестных, что значительно быстрее общих методов (например, метода Гаусса, имеющего сложность \(O(n^3)\)). Для решения системы из \(n\) уравнений требуется примерно \(8n\) арифметических операций.

История

Метод прогонки был впервые описан в 1949 году американским математиком Ллевеллином Томасом (Llewellyn Thomas) в контексте решения задач теплопроводности. В советской научной литературе метод получил название «прогонка» и был детально разработан в 1950-х годах в работах А. А. Самарского, И. М. Гельфанда и других математиков. Самарский внёс значительный вклад в теорию устойчивости и обобщение метода на многомерные задачи.

Модификации

Метод прогонки для периодических систем

Для систем с периодическими граничными условиями (когда \(x_0 = x_n\) и \(x_{n+1} = x_1\)) применяется циклическая прогонка (алгоритм Шермана — Моррисона). Она требует дополнительного решения двух вспомогательных систем.

Метод прогонки для блочно-трёхдиагональных матриц

В задачах, где неизвестные являются векторами (например, в методах конечных элементов), используется блочная прогонка. В этом случае коэффициенты \(a_i, b_i, c_i\) — матрицы, а \(x_i, d_i\) — векторы.

Метод встречных прогонок

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

Применение

Метод прогонки широко применяется в следующих областях:

• Численное решение дифференциальных уравнений: метод конечных разностей для уравнений теплопроводности, диффузии, волнового уравнения, уравнения Пуассона в одномерном случае.
• Интерполяция кубическими сплайнами: построение сплайнов сводится к решению трёхдиагональной системы.
• Обработка сигналов: фильтрация, сглаживание данных, решение задач свёртки.
• Экономика и финансы: модели ценообразования опционов (например, метод конечных разностей для уравнения Блэка — Шоулза).
• Механика: расчёт напряжений в балках, оболочек, конструкций.

Пример

Рассмотрим систему:

\[ \begin{cases} 2x_1 + 3x_2 = 8 \\ 4x_1 + 5x_2 + 6x_3 = 20 \\ 7x_2 + 8x_3 = 30 \end{cases} \]

Здесь \(a = [0, 4, 7]\), \(b = [2, 5, 8]\), \(c = [3, 6, 0]\), \(d = [8, 20, 30]\).

Прямая прогонка:

• \(\alpha_1 = c_1 / b_1 = 3 / 2 = 1.5\)
• \(\beta_1 = d_1 / b_1 = 8 / 2 = 4\)
• \(\alpha_2 = c_2 / (b_2 - a_2 \alpha_1) = 6 / (5 - 4 \cdot 1.5) = 6 / (5 - 6) = -6\)
• \(\beta_2 = (d_2 - a_2 \beta_1) / (b_2 - a_2 \alpha_1) = (20 - 4 \cdot 4) / (5 - 6) = (20 - 16) / (-1) = -4\)
• \(\alpha_3 = 0\) (так как \(c_3 = 0\))
• \(\beta_3 = (d_3 - a_3 \beta_2) / (b_3 - a_3 \alpha_2) = (30 - 7 \cdot (-4)) / (8 - 7 \cdot (-6)) = (30 + 28) / (8 + 42) = 58 / 50 = 1.16\)

Обратная прогонка:

• \(x_3 = \beta_3 = 1.16\)
• \(x_2 = \alpha_2 x_3 + \beta_2 = (-6) \cdot 1.16 + (-4) = -6.96 - 4 = -10.96\)
• \(x_1 = \alpha_1 x_2 + \beta_1 = 1.5 \cdot (-10.96) + 4 = -16.44 + 4 = -12.44\)

Решение: \(x_1 \approx -12.44\), \(x_2 \approx -10.96\), \(x_3 \approx 1.16\). Проверка подстановкой подтверждает корректность.

Критика и ограничения

Основные недостатки метода прогонки:

• Чувствительность к вырождению: при нарушении диагонального преобладания метод может стать неустойчивым.
• Ограниченность структуры: метод применим только к трёхдиагональным системам; для более общих разреженных матриц требуются другие алгоритмы.
• Накапливание ошибок округления: при большом числе уравнений (\(n > 10^5\)) ошибки округления могут существенно исказить результат, особенно если матрица плохо обусловлена.

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

Источники

• Самарский А. А., Гулин А. В. Численные методы. — М.: Наука, 1989.
• Тихонов А. Н., Самарский А. А. Уравнения математической физики. — М.: Наука, 1977.
• Thomas L. H. Elliptic Problems in Linear Differential Equations over a Network. — Watson Scientific Computing Laboratory, 1949.
• Press W. H., Teukolsky S. A., Vetterling W. T., Flannery B. P. Numerical Recipes: The Art of Scientific Computing. — 3rd ed. — Cambridge University Press, 2007.
• Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы. — М.: Бином, 2008.