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

 

Курсовая работа

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

по дисциплине Численные методы

Введение

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

Системы линейных алгебраических уравнений возникают как промежуточный или окончательный этап при решении ряда прикладных задач, описываемых дифференциальными, интегральными или системами нелинейных (трансцендентных) уравнений. Они могут появляться как этап в задачах математического программирования, статистической обработки данных, аппроксимации функций, при дискретизации краевых дифференциальных задач методом конечных разностей, методом конечных элементов, проекционными методами, в методе граничных элементов, дискретных особенностей, панельном методе аэродинамической компоновки летательного аппарата и т.д.

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

Одним из самых распространенных методов решения систем линейных уравнений является метод прогонки. Он является модификацией метода Гаусса для частного случая разреженных систем - системы уравнений с трёхдиагональной матрицей.

Цель работы: научиться решать системы линейных уравнений методом прогонки.

1.Теоретическая часть

.1Метод Крамера

Пусть дана система линейных уравнений:

Коэффициенты a11,12,..., a1n, ... , an1 , b2 , ... , bn считаются заданными. Вектор- строка íx1 , x2 , ... , xn ý - называется решением системы (1), если при подстановке этих чисел вместо переменных все уравнения системы (1) обращаются в верное равенство.

Определитель т-го порядка D=çAê=ça ij ç, составленный из коэффициентов при неизвестных, называется определителем системы (1). В зависимости от определителя системы (1) различают следующие случаи: .). Если D¹0, то система (1) имеет единственное решение, которое может быть найдено по формулам Крамера: x1=, где

определитель n-го порядка Di ( i=1,2,...,n) получается из определителя системы петём замены i-го столбца свободными членами b1 , b2 ,..., bn.

б). Если D=0 , то система (1) либо имеет бесконечное множество решений, либо несовместна, т.е. решений нет.

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

Для решения систем A x = b с трехдиагональной матрицей наиболее часто применяется метод прогонки, являющийся адаптацией метода Гаусса к этому случаю.

Запишем систему уравнений

1x1 + e1x2 = b1

c2x1 + d2x2 + e2x3 = b23x2 + d3x3 + e3x4 = b3

... ... ...n-1xn-2 + dn-1xn-1 + en-1xn = bn-1

cnxn-1 + dnxn = bn

в матричном виде: A x = b где A=

Выпишем формулы метода прогонки в порядке их применения.

Прямой ход метода прогонки (вычисление вспомогательных величин):

Обратный ход метода прогонки (нахождение решения):

Метод прогонки можно применять, если нигде в формулах знаменатели не равны нулю. В доказано следующее утверждение: для применимости формул метода прогонки достаточно выполнения условий диагонального преобладания у матрицы A, то есть

| di | ? | c i | + | ei |

причем хотя бы одно неравенство должно быть строгим.

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

.1Решение систем линейных уравнений методом Крамера

Нам дано уравнение вида:

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

Затем подставим значения в формулы для нахождения ?

=0.71*0.34*0.56+0.1*(-0.1)*(-0.04)+0.1*0.64*(-0.12)-0.34*(-0.12)*(-0.1)-0.71*0.64*(-0.04)-0.1*(-0.56)*(-0.1)=0.135184+0.0004-0.00768-0.00408+0.018176-0.0056=0.1364

0.29*0.34*0.56+0.32*0.64*(-0.12)+0.1*(-0.04)*(-0.1)-(-0.1)*0.34*(-0.12)-0.64*0.29*(-0.04)-0.32*0.1*0.56=0.055216-0.024576+0.0004-0.00408+0.007424-0.01792=0.016464

0.71*0.32*0.56+0.1*(-0.1)*(-0.12)+0.29*(-0.04)*(-0.1)-(-0.1)*0.32*(-0.12)-0.1*0.29*0.56-(-0.1)*(-0.04)*0.71= =0.127232+0.0012+0.00116-0.00384-0.01624-0.00284=0.106672

0.71*0.34*(-0.1)+0.1*0.64*0.29+0.1*0.32*(-0.1)-(-0.1)*0.32*0.29-0.64*0.32*0.71-0.1*0.1*(-0.1)=

=-0.02414+0.01856-0.0032+0.00928-0.145408+0.001=-0.143908

Подсчитаем чему равны корни уравнения

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

0,71*0,12070381+0,1*0,78205279-0,12*(-1,055044) =0,0856997051+0,078205279+0,12660528=0,2905102641

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

линейный уравнение программный прогонка

ур*0.1 2ур*(-0.71)

ур+2ур

ур*(-0,56 3ур*0,0284)

ур+3ур

?= - ?=

?1= - =-0.07087295

?2= - =0.11764706

?3= - =0

?1==-0.8565255

?2==0.94117647

?3==0.81111111

Xn=

X1= = =0,856526

X2= = =1,2617

X3 = =0,615844

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

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

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;

lbx: TLabel;: TLabel;: TLabel;btn1Click(Sender: TObject);

{ Private declarations }

{ Public declarations };: TForm1;

{$R *.dfm}

// нажатие на "вычислить"TForm1.btn1Click(Sender: TObject);

const=3; // размерность массивов и матриц

var, D, E : array of Real; //матрица уравнений

B : 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);[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.2Тестовый пример

Рассмотрим работу программы на простейшем примере

Все корни данной системы равны 1. Результат показан на рисунке 1.

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

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

Рассмотрим работу программы на примере

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

X=0,856526 Y=1,2617 Z= - 0,6158

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

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

Заключение

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

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

Список литературы

1.Л.И.Турчак П.В.Плотников Основы численных методов

2.<http://www.gasu.ru/resour/eposobia/metody/R_1_3.html>

.<http://ru.wikipedia.org/wiki/Метод_прогонки>

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

Больше работ по теме: