Метод прогонки
Метод прогонки состоит из двух этапов - прямой прогонки (аналога прямого хода метода Гаусса) и обратной прогонки (аналога обратного хода метода Гаусса). Прямая прогонка состоит в том, что каждое неизвестное xi выражается через xi+1 с помощью прогоночных коэффициентов Ai, Bi:
Из первого уравнения системы (1) выразим x1 через x2:
С другой стороны, по формуле (2) x1=A1x2+B1. Сравнивая эти соотношения, получаем выражения для прогоночных коэффициентов:
Используя формулу (2) для x1, получим выражение для x2
или
Аналогично можно вычислить прогоночные коэффициенты для любого индекса i=2, 3, …, n-1:
Обратная прогонка состоит в последовательном вычислении неизвестных xi. Сначала нужно найти xn. Для этого воспользуемся выражением (2) при i=n-1 и последним уравнением системы (1):
Исключая xn-1 из этих выражений, находим:
Далее, используя формулы (2) и выражения для прогоночных коэффициентов (3), (4), последовательно вычисляем все неизвестные xn-1 , xn-2, …, x1.
(хотя бы для одного значения должно иметь место строгое неравенство), деление на нуль не возникает, и система (1) имеет единственное решение. Приведенное условие преобладания диагональных элементов (6) обеспечивает также устойчивость метода прогонки относительно погрешностей округления. Последнее обстоятельство позволяет использовать метод прогонки для решения больших систем уравнений. Заметим, что данное условие устойчивости прогонки (6) является достаточным, но не необходимым. В ряде случаев для хорошо обусловленных систем вида (1) метод прогонки оказывается устойчивым даже при нарушении условия преобладания диагональных элементов.
|
,
,
; 
; 
.
; 
; 
.
, 
.
.
При анализе алгоритма метода прогонки надо учитывать возможность деления на ноль в формулах (4). Можно показать, что при выполнении условия преобладания диагональных элементов, т.е. если
,
