Решение систем линейных алгебраических уравнений методом прогонки

а, используя (7) , получаем

т.е. знаменатели выражений (4) не обращаются в нуль.

Более того

Следовательно,

Далее, учитывая второе из условий (8) и только что доказанное неравенство , имеем

т.е. не обращается в нуль и знаменатель в выражении для .

К аналогичному выводу можно прийти и в том случае, когда условия (7), (8) заменяются условиями

Таким образом при выполнении условий (7), (8) (так же как и условий (9), (10)) система (1), (2) эквивалентна системе (4)-(6). Поэтому эти условия гарантируют существование и единственность решения системы (1), (2) и возможность нахождения этого решения методом прогонки.

Кроме того, доказанные неравенства ,  обеспечивают устойчивость счета по рекуррентным формулам (6). Последнее означает, что погрешность,внесенная на каком-либо шаге вычислений, не будет возрастать при переходе к следующим шагам.

Действительно, пусть в формуле (6) при  вместо  вычислена величина  

Тогда на следующем шаге вычислений, т.е. при  

вместо

получим величину  и погрешность окажется равной

Отсюда получаем, что ,т.е. погрешность не возрастает.

Подсчитаем число арифметических действий, выполняемых при решении задачи (1), (2) методом прогонки.

По формулам (4), что реализуемые с помощью шести арифметических действий, вычисления производятся  раз, по формуле (6) выполняется 5 арифметических действий, наконец по формуле (3), требующей всего два действия, вычисления осуществляются раз. Итак в методе прогонки всего затрачивается

арифметических действий, т.е. число действий растет линейно относительно числа неизвестных

При решении же произвольной системы линейных алгебраических уравнений методом Гаусcа число действий пропорционально кубу числа неизвестных.

2. Постановка и решение задачи

.1 Формулировка задачи

Решение систем линейных алгебраических уравнений методом прогонки (на примере системы )

.2 Решение системы методом Гаусса

Дана система:

Преобразуем в матрицу:

Чтобы было легче работать, умножим каждый член матрицы на 100:

Преобразуем матрицу, умножив вторую строку на 3 и вычтем из третью строку:

Получим:

Далее, умножим первую строку на 5 и вычтем 21 умноженную на третью строку

.Найдем сумму третьей строки умноженной на 92 и второй строки умноженной на 185

В результате преобразований данная система приводится к треугольному виду:

из последнего уравнения находим z:

подставляя это значение во второе уравнение, получаем:

из первого уравнения, подставив полученные значения, получим:

Выполним проверку

подставим полученные значения x,y,z в первую строку данной матрицы:

,63*0,376+0,05*0,777+0,15*0,427=0,34

,05*0,376+0,34*0,777+0,1*0,427=0,32

,15*0,376+0,1*0,777+0,71*0,427=0,42

Проверка выполнена.

2.3 Решение системы методом прогонки

Приведем матрицу к виду:

 <#"656787.files/image082.gif">

- умножим вторую строку на 15 и вычтем из нее первую строку:

- третью строку умножим на 5 и вычтем из нее третью строку:

Мы преобразовали матрицу к виду:

Вычислим значения прогоночных коэффициентов  и :

=

=

=

=  т.к =0

=

Обратный ход

Вычислим значение :

Подставив в формулу значение , вычислим значение :

Подставив в формулу значение , вычислим значение  :

3/ Программная реализация

.1 Блок-схема

.2 Текст программы

Unit1;

interface, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, StdCtrls;= class(TForm): TEdit;: TLabel;: TEdit;: TLabel;: TEdit;: TEdit;: TLabel;: TEdit;: TLabel;: TEdit;: TEdit;: TLabel;: TLabel;: TEdit;: TLabel;: TEdit;: TLabel;: TEdit;: TButton;: TLabel;: TLabel;: TLabel;: TLabel;btn1Click(Sender: TObject);

{ Private declarations }

{ Public declarations };: TForm1;

{$R *.dfm}

// нажатие на "вычислить"TForm1.Click(Sender: TObject);=3; // размерность массивов и матриц

C, D, E : array of Real; //матрица уравнений: array of Real; // чему равны уравнения (первая часть): array of Real; // результат,k : Integer; // для циклов, перебора, BET : array of Real; // Alpha и Beta для предв. вычислений: Real;

{установим длины массивов}

SetLength(C,n);(D,n);(E,n);(B,n);(Y,n);

(ALF,n);(BET,n);

{заполним массивы}

//главная диагональ (d):[0]:=strtofloat(edtD1.text);[1]:=strtofloat(edtD2.text);[2]:=strtofloat(edtD3.text);

//диагональ c (та что пониже d)

c[0]:=0;[1]:=strtofloat(edtC2.text);

c[2]:=strtofloat(edtC3.text);

//диагональ e (та что повыше d)

e[0]:=strtofloat(edtE1.text);[1]:=strtofloat(edtE2.text);

e[2]:=0;

//заполняем чему равны наши выражения

b[0]:=strtofloat(edtB1.text);[1]:=strtofloat(edtB2.text);

b[2]:=strtofloat(edtB3.text);

//проверим, можно ли считать этим способом:

k:=0;i:=0 to n-1 doAbs(d[i])>Abs(c[i])+abs(e[i]) then k:=k+1;

if k=0 then begin('Данный способ не применим, т.к. условие диагонального преобладания матрицы не выполняется :( ');;;

{вычисление вспомогательных величин}

ALF[0]:= -(E[0]/D[0]);[0]:= B[0]/D[0];

{прямой ход}I:= 1 to n - 1 do:= d[i] + c[i]*ALF[i-1];[i]:= -(e[i]/znam);[i]:= (-c[i]*BET[i-1]+b[i])/znam;

end;

{обратный ход, нахождение корней}

Y[n-1]:=(b[n-1]-c[n-1]*BET[n-2])/(d[n-1]+c[n-1]*ALF[n-2]);I:= n - 2 downto 0 do[i]:=Y[i+1]*ALF[i]+BET[i];

//вывод результата.Caption:='X = ' + floattostr(Y[0]);.Caption:='Y = ' + floattostr(Y[1]);.Caption:='Z = ' + floattostr(Y[2]);

end;.

.3 Тестовый пример

В качестве тестового примера возьмем :

При ручном подсчете корни равны: x=-3 y=-7 z= -15

Рисунок 1. Результат работы программы.

3.4 Решение задачи с помощью ЭВМ

При решении системы линейных алгебраических уравнений методом прогонки с помощью Delphi получаем:

Рисунок 2. Результат работы программы (метод прогонки)

Заключение

Решение систем линейных алгебраических уравнений - одна из основных задач вычислительной линейной алгебры. Хотя задача решения системы линейных уравнений сравнительно редко представляет самостоятельный интерес для приложений, от умения эффективно решать такие системы часто зависит сама возможность математического моделирования самых разнообразных процессов с применением ЭВМ. Значительная часть численных методов решения различных (в особенности - нелинейных) задач включает в себя решение систем линейных уравнений как элементарный шаг соответствующего алгоритма.

Численные методы являются одним из мощных математических средств решения задачи. Простейшие численные методы мы используем всюду, например, извлекая квадратный корень на листке бумаги. Есть задачи, где без достаточно сложных численных методов не удалось бы получить ответа; классический пример - открытие Нептуна по аномалиям движения Урана.

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

В ходе выполнения курсовой работы мы проделали ручной расчет заданного уравнения, выполнили расчет на языке программирования Delphi. Также мы выполнили тестовый пример для проверки метода прогонки.

Список использованной литературы

Карманов В.Г. Математическое программирование. - М.: Наука 1986

Пирумов У.Г. Численные методы. - М.: Изд-во МАИ, 1998

Бахвалов Н.С., Лапин А.В., Чижонков Е.В. Численные методы в задачах и упражнениях. - М.: Высшая школа, 2001.

Самарский А.А., Гулин А.В. Численные методы. -М.:Наука,1989.-432с.