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

Данный метод также является модификацией метода Гаусса для частного случая разреженных систем – систем с матрицей трехдиагонального типа (краевая задача ДУ).

Каноническая форма их записи

a_ix_{i –1} + b_ix_i + c_ix_{i +1} = d_i; i =; a ₁ = c_n = 0, (9)

или в развернутом виде

b ₁ x ₁ + c ₁ x ₂ = d ₁;

a ₂ x ₁ + b ₂ x ₂ + c ₂ x ₃ = d ₂;

a ₃ x ₂ + b ₃ x ₃ + c ₃ x ₄ = d ₃;

... (10)

a_{n –1} x_{n –2} + b_{n –1} x_{n –1} + c_{n –1} x_n = d_{n –1};

a_nx_{n –1} + b_nx_n = d_n.

При этом, как правило, все коэффициенты b_i ¹ 0.

Метод реализуется в два этапа – прямой и обратный ходы.

Прямой ход. Каждое неизвестное x_i выражается через x_{i +1}

x_i = A_i × x_{i +1} + B_i для i = 1,2,..., n –1, (11)

посредством прогоночных коэффициентов A_i и B_i. Определим алгоритм их вычисления.

Из первого уравнения системы (10) находим x ₁

.

Из уравнения (11) при i =1: x ₁ = A ₁ × x ₂ + B ₁. Следовательно

. (12)

Из второго уравнения системы (10) определяем x ₂ через x ₃, подставляя найденное значение x ₁

а ₂ (A ₁ x ₂ + B ₁) + b ₂ x ₂ + c ₂ x ₃ = d ₂ ,

откуда

; (12*)

и согласно (11) при i = 2: x ₂ = A ₂ × x ₃ + B ₂, следовательно

, где е ₂ = а ₂ × А ₁ + b ₂.

Ориентируясь на соотношения индексов при коэффициентах (12) и (12*) можно получить эти соотношения для общего случая

, где е_i = а_i × А_{i –1} + b_i (i =2,3,..., n –1). (13)

Обратный ход. Из последнего уравнения системы (10) с использованием (11) при i = n –1

. (14)

Далее посредством (11) и прогоночных коэффициентов (12), (13) последовательно вычисляем x_{n –1}, x_{n –2},..., x ₁.

При реализации метода прогонки нужно учитывать, что при условии

| b_i | ³ | a_i | + | c_i |, (15)

или хотя бы для одного b_i имеет место строгое неравенство (15), деление на «0» исключается и система имеет единственное решение.

Заметим, что условие (15) является достаточным, но не необходимым. В ряде случаев для хорошо обусловленных систем (10) метод прогонки может быть устойчивым и при несоблюдении условия (15).

Схема алгоритма метода прогонки может иметь вид, представленный на рис. 2.2.

Рис. 2.2. Блок-схема метода прогонки

Дата добавления: 2014-01-04