Нужно составить алгоритм и написать программу. Через два дня надо сдать, а у меня ни того, ни второго. Теория:
Метод прогонки.
Он является модификацией метода Гаусса для частного случая разреженных систем — системы уравнений с трехдиагональной матрицей. Такие системы получаются при моделировании некоторых инженерных задач, а также при численном решении краевых задач для дифференциальных уравнений.
Запишем систему уравнений в виде:
b1x1+c1x2 =d1,
a2x¬1+b2x2+c2x3 =d2,
a3x2+b3x3+c3x4 =d3,
…………………………………………………………… (1),
an-1xn-2+bn-1xn-1+cn-1xn=dn-1,
anxn-1+bnxn=dn.
На главной диагонали матрицы этой системы стоят элементы b1,b2…,bn, над ней – элементы c1,c2,...,cn-1, под ней – элементы a2,a3,…,an. При этом обычно все коэффициенты bi не равны нулю.
Метод прогонки состоит из двух этапов — прямой прогонки (аналога прямого хода метода Гаусса) и обрат¬ной прогонки (аналога обратного хода метода Гаусса). Прямая прогонка состоит в том, что каждое неизвестное xi выражается через xi+1 c помощью прогоночных коэф¬фициентов Ai, Bi:
xi=Aixi+1+Bi, i=1,2,…,n-1. (2).
Из первого уравнения системы (1) найдем
x1= - c_1/b_1 x2 + d_1/b_1 .
С другой стороны, по формуле (2) x1=A1x2+B1 . При¬равнивая коэффициенты в обоих выражениях для x1, по¬лучаем
A1= - c_1/b_1 , B1= d_1/b_1 (3).
Из второго уравнения системы (1) выразим x2 через x3 заменяя x1 по формуле (2):
a2(A1x2+B1)+b2x¬2+c2x3=d2.
Отсюда найдем
x2= (-c_(2X_3 )+d_2-a_2 B_1)/(a_2 A_1+b_2 ),
или
x2=A2x3+B2,
A2= - c_2/e_2 , B2= (d_(2-) a_2 B_1)/e_2 , e2=a2A1+b2.
Аналогично можно вычислить прогоночные коэффициен¬ты для любого номера i:
Ai= - c_i/e_i , Bi= (d_i-a_i B_(i-1))/e_i , (4).
ei=aiAi-1+bi, i=2,3,…,n-1.
Обратная прогонка состоит в последовательном вы¬числении неизвестных хi. Сначала нужно найти хп. Для этого воспользуемся выражением (2) при i= n — 1 и последним уравнением системы (1). Запишем их:
xn-1=An-1xn+Bn-1,
anxn-1+bnxn=dn.
Отсюда, исключая xn-1 находим
xn= (d_n-a_n B_(n-1))/(b_n+a_n A_(n-1) ).
Далее, используя формулы (2) и выражения для прогоночных коэффициентов (3), (4), последова¬тельно вычисляем все неиз¬вестные xn-1, xn-2,…,x1.
При анализе алгоритма метода прогонки надо учи¬тывать возможность деления на нуль в формулах (4), Можно показать, что при выполнении условия преоб¬ладания диагональных эле¬ментов, т. е. если |bi|≥ |ai|+|ci|, причем хотя бы для одного значения i имеет место строгое неравенство, деления на нуль не возника¬ет, и система (1) имеет единственное решение.
Приведенное условие пре¬обладания диагональных эле¬ментов обеспечивает также устойчивость метода прогон¬ки относительно погрешно¬стей округлений. Последнее обстоятельство позволяет использовать метод прогон¬ки для решения больших систем уравнений. Заметим, что данное условие устойчи¬вости прогонки является достаточным, но не необходимым. В ряде случаев для хорошо обусловленных систем вида (1) метод прогонки оказывается устойчивым даже при нарушении условия преобладания диагональных элементов.
Пример.
2.05x1+1.07x2 =1.78
1.83x1+2.42x2-1.02x3 =2.45
-3.49x2+1.51x3=3.26
Решение:
Вычисляем прогоночные коэффициенты:
A1= - c_1/b_1 = - 1.07/2.05 = - 0.522
B1= d_1/b_1 = 1.78/2.05 = 0.868
ei=aiAi-1+bi, i=2,3,…,n-1
ei= - 0.522*1.83+2.42=1.465
A2= - c_2/e_2 = (-1.02)/1.465 = 0.696
B2= (d_(2-) a_2 B_1)/e_2 = (2.45-1.83*0.868)/1.465 = 0.588
Вычисляем неизвестные xi:
xn= (d_n-a_n B_(n-1))/(b_n+a_n A_(n-1) ) = (3.26-3.49*0.588)/(1.51-3.49*0.696) = -5.78
xi=Aixi+1+Bi, i=1,2,…,n-1.
x2= 0.696*(-5.78)+0.588 = - 3.435
x1= - 0.522*(-3.435)+0.686 = 2.611
Получили решение системы:
X=[(2.661
-3.435
-5.78)].
Метод прогонки.
Он является модификацией метода Гаусса для частного случая разреженных систем — системы уравнений с трехдиагональной матрицей. Такие системы получаются при моделировании некоторых инженерных задач, а также при численном решении краевых задач для дифференциальных уравнений.
Запишем систему уравнений в виде:
b1x1+c1x2 =d1,
a2x¬1+b2x2+c2x3 =d2,
a3x2+b3x3+c3x4 =d3,
…………………………………………………………… (1),
an-1xn-2+bn-1xn-1+cn-1xn=dn-1,
anxn-1+bnxn=dn.
На главной диагонали матрицы этой системы стоят элементы b1,b2…,bn, над ней – элементы c1,c2,...,cn-1, под ней – элементы a2,a3,…,an. При этом обычно все коэффициенты bi не равны нулю.
Метод прогонки состоит из двух этапов — прямой прогонки (аналога прямого хода метода Гаусса) и обрат¬ной прогонки (аналога обратного хода метода Гаусса). Прямая прогонка состоит в том, что каждое неизвестное xi выражается через xi+1 c помощью прогоночных коэф¬фициентов Ai, Bi:
xi=Aixi+1+Bi, i=1,2,…,n-1. (2).
Из первого уравнения системы (1) найдем
x1= - c_1/b_1 x2 + d_1/b_1 .
С другой стороны, по формуле (2) x1=A1x2+B1 . При¬равнивая коэффициенты в обоих выражениях для x1, по¬лучаем
A1= - c_1/b_1 , B1= d_1/b_1 (3).
Из второго уравнения системы (1) выразим x2 через x3 заменяя x1 по формуле (2):
a2(A1x2+B1)+b2x¬2+c2x3=d2.
Отсюда найдем
x2= (-c_(2X_3 )+d_2-a_2 B_1)/(a_2 A_1+b_2 ),
или
x2=A2x3+B2,
A2= - c_2/e_2 , B2= (d_(2-) a_2 B_1)/e_2 , e2=a2A1+b2.
Аналогично можно вычислить прогоночные коэффициен¬ты для любого номера i:
Ai= - c_i/e_i , Bi= (d_i-a_i B_(i-1))/e_i , (4).
ei=aiAi-1+bi, i=2,3,…,n-1.
Обратная прогонка состоит в последовательном вы¬числении неизвестных хi. Сначала нужно найти хп. Для этого воспользуемся выражением (2) при i= n — 1 и последним уравнением системы (1). Запишем их:
xn-1=An-1xn+Bn-1,
anxn-1+bnxn=dn.
Отсюда, исключая xn-1 находим
xn= (d_n-a_n B_(n-1))/(b_n+a_n A_(n-1) ).
Далее, используя формулы (2) и выражения для прогоночных коэффициентов (3), (4), последова¬тельно вычисляем все неиз¬вестные xn-1, xn-2,…,x1.
При анализе алгоритма метода прогонки надо учи¬тывать возможность деления на нуль в формулах (4), Можно показать, что при выполнении условия преоб¬ладания диагональных эле¬ментов, т. е. если |bi|≥ |ai|+|ci|, причем хотя бы для одного значения i имеет место строгое неравенство, деления на нуль не возника¬ет, и система (1) имеет единственное решение.
Приведенное условие пре¬обладания диагональных эле¬ментов обеспечивает также устойчивость метода прогон¬ки относительно погрешно¬стей округлений. Последнее обстоятельство позволяет использовать метод прогон¬ки для решения больших систем уравнений. Заметим, что данное условие устойчи¬вости прогонки является достаточным, но не необходимым. В ряде случаев для хорошо обусловленных систем вида (1) метод прогонки оказывается устойчивым даже при нарушении условия преобладания диагональных элементов.
Пример.
2.05x1+1.07x2 =1.78
1.83x1+2.42x2-1.02x3 =2.45
-3.49x2+1.51x3=3.26
Решение:
Вычисляем прогоночные коэффициенты:
A1= - c_1/b_1 = - 1.07/2.05 = - 0.522
B1= d_1/b_1 = 1.78/2.05 = 0.868
ei=aiAi-1+bi, i=2,3,…,n-1
ei= - 0.522*1.83+2.42=1.465
A2= - c_2/e_2 = (-1.02)/1.465 = 0.696
B2= (d_(2-) a_2 B_1)/e_2 = (2.45-1.83*0.868)/1.465 = 0.588
Вычисляем неизвестные xi:
xn= (d_n-a_n B_(n-1))/(b_n+a_n A_(n-1) ) = (3.26-3.49*0.588)/(1.51-3.49*0.696) = -5.78
xi=Aixi+1+Bi, i=1,2,…,n-1.
x2= 0.696*(-5.78)+0.588 = - 3.435
x1= - 0.522*(-3.435)+0.686 = 2.611
Получили решение системы:
X=[(2.661
-3.435
-5.78)].