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

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

Запишем систему уравнений в виде

a₁=c_n=0

b₁X₁+c₁X₂ = d₁

a₂X₁+b₂X₂+c₂X₃ = d₂

a₃X₂+b₃X₃+c₃X₄ = d₃

----------------------------------------

a_n-1X_n-2+b_n-1X_n-1+c_n-1X_n = d_n-1

a_nX_n-1+b_nX_n = d_n

На главной диагонали матрицы этой системы стоят элементы b₁, b₂,…, b_n, над ней – элементы с₁, с₂,…, с_n-1, под ней – элементы a₁, a₂,…, a_n. При этом обычно все b_i не равны нулю.

Метод прогонки состоит из двух этапов – прямой прогонки (аналог прямого хода метода Гаусса) и обратной прогонки (аналог обратного хода метода Гаусса).

Прямая прогонка состоит в том, что каждое неизвестное x_i выражается через Х_i+1 с помощью прогоночных коэффициентов A_i и B_i

X_i=A_iX_i+1+B_i , i=1, 2,…, n-1.

Из первого уравнения находим

X₁= –(c₁/b₁)X₂+d₁/b₁.

Отсюда можно определить (Х₁=А₁Х₂+В₁)

А₁= –с₁/b₁ , В₁=d₁/b₁.

Из второго уравнения системы выразим Х₂ через Х₃ с учетом выражения для Х₁ через А₁ и В₁

А₂(А₁Х₂+В₁)+b₂X₂+c₂X₃=d₂.

Теперь

X₂=(–c₂X₃+d₂–a₂B₁)/(a₂A₁+B₂)

или

X₂=A₂X₃+B₂ ,

где A₂= –c₂/L₂, B₂=(d₂–a₂B₁)/L₂, L₂=a₂A₁+b₂.

Аналогично, для любого номера i:

A_i= –c_i/L_i, B_i=(d_i–a_iB_i-1)/L_i, L_i=a_iA_i-1+b_i, i=2, 3,…, n-1.

Обратная прогонка состоит в последовательном вычислении неизвестных Х_i. Сначала нужно найти Х_n. Для этого воспользуемся выражением X_i=A_iX_i+1+B_i при i=n-1 и последним уравнением исходной системы:

X_n-1=A_n-1X_n+B_n-1,

A_nX_n-1+b_nX_n=d_n .

Отсюда, исключая X_n-1, находим

X_n=(d_n–a_nB_n-1)/(b_n+a_nA_n-1).

Далее, используя X_n-1=A_n-1X_n+B_n-1 и выражения для прогоночных коэффициентов А₁, В₁ и A_i, B_i (i=2, 3,…, n-1) последовательно вычисляем все неизвестные X_n-1, X_n-2,…, X₁.

М огут возникнуть сомнения по поводу деления на нуль в выражениях для A_i, B_i. Можно показать, что при преобладании диагональных элементов, т.е. если b_i > a_i + c_i , причем хотя бы для одного i имеет место строгое неравенство, деления на нуль не возникает и система имеет единственное решение.

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