Численные методы линейной алгебры

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

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

Ax=b, (2.34)
когда матрица А – трехдиагональная и ненулевые элементы определяются следующим образом: a_ij0, если j=i-1, j=i, j=i+1.
Введем обозначения
a_ii-1=-a_i , a_ii=c_i , a_ii+1=-d_i .
Тогда система уравнений (2.34) запишется в виде
(2.35)
Решение (2.35) будем искать в виде
x_i=_ix_i+1+_i , (2.36)
где _i , _i – неизвестные прогоночные коэффициенты. Подставив, найденные из (2.36) x_i-1 в среднее уравнение из системы (2.35), получим для 2in-1 :
(2.37)
Из сравнения (2.36) и (2.37) следует, что
(2.38)
Зная ₁ , ₁ по формулам (2.38) можно найти все _i , _i для i=2, 3,…, n, то есть провести прямой ход прогонки.
Если удастся найти x_n , то по формуле (2.36) при известных _i , _i можно вычислить неизвестные x_i для i=n-1, n-2,…, 1, то есть провести обратный ход прогонки. Поэтому дальше определяем ₁ , ₁ и x_n .
Из первого уравнения системы (2.35) найдем

что вместе с уравнение
х₁=₁х₂+₁
из (2.36) при i=1 дает
(2.39)
Далее, из последнего уравнения системы (2.35) и из (2.36) при i=n-1 имеем систему уравнений

откуда находим
(2.40)
Таким образом, алгоритм метода прогонки при решении СЛАУ (2.35) заключается в следующем:

1. 
   по формулам (2.39) и (2.38) вычисляются коэффициенты _i , _i для i=1, 2,…,n (прямой ход);
   

2) по формулам (2.40) и (2.36) вычисляются неизвестные x_i для i=n-1, n-2,…, 1 (обратный ход).
Метод прогонки реализуется, если нет деления на нуль в формулах (2.38)-(2.40). Для выполнения этого условия достаточно, чтобы detA0.
Так как при использовании метода прогонки заранее неизвестен detA , то необходим простой способ оценки устойчивости метода.


Достаточные условия устойчивости метода прогонки. Для устойчивости метода прогонки достаточно выполнение неравенств:

Рассмотренный здесь вариант метода прогонки называется правой прогонкой. Название метода следует из того, что при обратном ходе неизвестные x_i вычисляются справа налево, т.е. сначала x_n , x_n-1 и т.д.

Существует метод левой прогонки, в котором неизвестные x_i вычисляются слева направо, т.е. сначала х₁ , х₂ и так далее.
Комбинация левой и правой прогонок дает метод встречных прогонок.