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

Является частным случаем метода Гаусса и применяется для решения систем уравнений с трех диагональной (ленточной) матрицей. Такая система уравнений записывается в виде:

a_ix_i-1+b_ix_i+c_ix_i+1 = d_i i = 1, 2, 3, ..., n (2.6)

a₁= 0; c_n = 0.

Формула обратного хода записываем в следующем виде:

x_i = U_i x_i+1 + V_i ; i = n, n-1,..,1 (2.7)

Уменьшаем в формуле (2.7) индекс на единицу и подставляем в (2.6):

x_i-1 = U _{i -1}x_i + V_i-1,

a_i (U_i-1x_i + V_i-1) + b_ix_i + c_ix_i+1 = d_i

Приведем подобные и запишем:

(a_iU_i-1 +b_i)x_i =-c_ix_i+1 + d_i -a_iV_i-1,

x_i =-c_i /(a_iU_i-1+ b_i)x_i+1+ (d_i - a_iV_i-1)/(a_iU_i-1 + b_i) (2.8)

сравнивая (2.7) и (2.8), получим:

U_i = -c_i / (b_i + a_iU_i-1);

V_i = (d_i - a_iV_i-1) / (b_i + a_iU_i-1); i = 2, 3, ..., n (2.9)

Поскольку a₁ = 0, то

U₁ = -c₁ / b₁; V₁ = d₁ / b₁. (2.10)

Теперь по формулам (2.9) и (2.10) можно вычислить прогоночные коэффициенты U_i и V_i (i=1,2,3,...,n). Это прямой ход прогонки. Зная прогоночные коэффициенты по формулам (2.7), можно вычислить все x_i; i=n,...,3,2,1 (обратный ход прогонки). Поскольку c_n = 0, то U_n = 0 и x_n = V_n. Далее вычисляем x_n-1, x_n-2, ..., x₂, x₁.

Пример: Решить систему уравнений методом прогонки:

10x₁ + x₂ = m+5

-2x₁ + 9x₂ + x₃ = n+9 m -1

0,1x₂ +4x₃ -x₄ = 4 n+0,1 m -5

-x₃ +8x₄ – x₅ = 40 -n – L

x₅ = L,

где значения m - номер варианта, n - номер группы, L – номер факультета.

Решение: Даны значения a_i; b_i; c_i; d_i; m=0, n=0, L=0; i=1, 2, 3, 4, 5. Их записываем в виде таблицы 2.1.

Таблица 2.1

i	ai	bi	ci	di
1	0	10	1	5
2	-2	9	1	-1
3	0,1	4	-1	-5
4	-1	8	-1	40
5	0	1	0	0

Прямой ход прогонки. По формулам (2.9) и (2.10) определяем прогоночные коэффициенты U_i и V_i (i=1,2,3,4).

U₁=-c₁/b₁=-1/10=-0,1

V₁=d₁/b₁=5/10=0,5

U₂= -c₂ /(b₂ + a₂U₁)=-1/(9+2·0,1)= -0,1087

V₂ = (d₂ - a₂V₁)/(b₂ + a₂U₁)=(-1+2·0,5)/(9+2·0,1)=0

U₃= -c₃ /(b₃ + a₃U₂)=1/(4-0,1·0,1087)= 0,25068

V₃ = (d₃ - a₃V₂)/(b₃ + a₃U₂)=(-5-0,1·0)/( 4-0,1·0,1087)= -1,25341

U₄= -c₄ /(b₄ + a₄U₃)= 1/(8-1·0,25068)= 0,1290436

V₄ = (d₄ - a₄V₃)/(b₄ + a₄U₃)=(40-1·1,25341)/(8-1·0,25068)= 5

U₅= -c₅ /(b₅ + a₅U₄)=0

V₅ = (d₅ – a₅V₄)/(b₅ + a₅U₄)=(0-0·5)/(1+0·0,1290436)= 0

Обратный ход прогонки. По формулам (2.7) вычисляем все x_i; i=4,3,2,1). Поскольку c_n = 0, то x₅ = V₅ = 0.

Далее вычисляем x₄, x₃, x₂, x₁.

x ₄ = U₄ x₅ + V₄ =0,1290436 · 0+5=5

x ₃ = U₃ x₄ + V₃ =0,25068·5-1,25341=0

x₂ = U₂ x₃ + V₂ =-0,1087·0+0=0

x₁ = U₁ x₂ + V₁ =-0,1·0+0,5=0,5

Вычисляем невязки r_i = d_i - a_ix_i-1 - b_ix_i - c_ix_i+1; i=1, 2, 3, 4, 5.

r₁ = d₁ - b₁x₁ - c₁x₂ = 5 -10·0,5 – 1 · 0=0

r₂ = d₂ - a₂x₁ - b₂x₂ - c₂x₃ = -1+2·0,5 - 9·0 - 0=0

r₃ = d₃ - a₃x₂ - b₃x₃ - c₃x₄ = -5-0,1 · 0 -4 · 0 +1 · 5=0

r₄ = d₄ - a₄x₃ – b₄x₄ – c₄x₅ = 40 +1 · 0 -8 · 5 +1 · 0 =0

r₅ = d₅ – a₅x₄ – b₅x₅ = 0 -0 · 5 -1 · 0 = 0

Алгоритм метода прогонки заключается в следующем:

1. Ввести a_i; b_i; c_i; d_i; i=1, 2, 3, ..., n.

2. Выполнить прямой ход, т.е. вычислить U_i и V_i; i=1, 2, 3, ..., n.

3. Выполнить обратный ход прогонки, т.е. вычислить x_i=U_i · x_i+1+V_i;

i=n, n-1,...,1.

4. Напечатать x_i; i=1, 2, 3, ..., n.

5. Вычислить невязки r_i = d_i - a_ix_i-1 - b_ix_i - c_ix_i+1; i=1, 2, 3, ..., n.

6. Напечатать r_i ; i=1, 2, 3, ..., n.

На рис. 2.1 приведена программа решения методом прогонки.

REM LR-2-2, m=13, n=5

DIM A(5), B(5), C(5), D(5), U(5), V(5), X(6), R(5)

DATA 0, 10, 1, 5

DATA -2, 9, 1, -1

DATA 0.1, 4, -1, -5

DATA -1, 8, -1, 40

DATA 0, 1, 0, 0

FOR I =1 TO 5

READ A(I), B(I), C(I), D(I)

U(I) = -C(I) / (A(I)*U(I-1) + B(I))

V(I) =(D(I)-A(I)*V(I-1)) / (A(I)*U(I-1) + B(I))

NEXT I

X(5) = V(5)

FOR I =4 TO 1 STEP -1

X(I) = U(I)*X(I+1) + V(I)

NEXT I

FOR I =1 TO 5

R(I) = D(I)-A(I)*X(I-1)-B(I) *X(I)-C(I)*X(I+1)

PRINT X ; I;  = ; X(I); R; I; R(I)

NEXT I

Рис.2.1. Программа решения методом прогонки.