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

Наиболее важным частным случаем метода Гаусса решения систем линейных алгебраических уравнений является метод прогонки, применяемый к системам с трехдиагональной матрицей. Такие системы обычно записывают в каноническом виде:

(1)

Так как прогонка – частный случай метода Гаусса, различают прямую прогонку и обратную прогонку.

Прямой ход сводится к исключению элементов a_i. В результате получается система, содержащая в каждом уравнении только два неизвестных y_i и y_{i+1 .} Поэтому формулы обратного хода имеют вид:

(2)

Таким образом, в ходе прямой прогонки следует определить коэффициенты α _i+1 и β _i+1.

Уменьшим в формуле (2) индекс i на 1: (3)

и подставим выражение (3) в уравнение (1): .

Отсюда (4)

Для того, чтобы выражение (4) совпало с выражением (2), следует приравнять коэффициенты. Так получаем формулы прямого хода: (5)

Для начала вычислений прямой прогонки требуются значения α ₁ и β _1. Используя первое уравнение системы (1), получаем ,

следовательно, α ₁ =0 и β ₁=1, а для начала вычислений обратной прогонки требуется значение y_n, которое дает последнее уравнение системы (1). Таким образом, при решении краевой задачи граничные условия дополняют разностную схему.

Покажем, что если выполнено условие преобладания диагональных элементов (6)

(причем хотя бы при одном i имеет место строгое неравенство), то в формулах прямого хода (5) не возникает деления на 0, и, следовательно, система (1) имеет единственное решение. Для этого предположим, что | α _i |< 1 при некотором значении индекса. Тогда

Так как α ₁ =0, по индукции получаем, что | α _i |< 1 при любом значении i, а значит, для любого i – что и требовалось доказать.

При выполнении условия (6) формулы прогонки устойчивы относительно ошибок округления и позволяют успешно решать системы уравнений с несколькими сотнями и тысячами неизвестных.

Условие (6) является достаточным, но не необходимым условием устойчивости прогонки. В практических расчетах для хорошо обусловленных систем типа (1) прогонка часто оказывается устойчивой даже при нарушении условия диагонального преобладания.

Вычисления по формулам прогонки (5), (4) требуют всего 3 n ячеек памяти и 9 n арифметических операций (тогда как метод Гаусса с выбором главного элемента требует n² ячеек памяти и ~2/3 n³ арифметических операций). Таким образом, метод прогонки значительно экономнее общего метода исключения неизвестных.

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

То .