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

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

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

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

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

Введение

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

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

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

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

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

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

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

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

Коэффициенты a₁₁,₁₂,..., a_1n, ... , a_n1 , b₂ , ... , b_n считаются заданными. Вектор- строка íx₁ , x₂ , ... , x_n ý - называется решением системы (1), если при подстановке этих чисел вместо переменных все уравнения системы (1) обращаются в верное равенство.

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

определитель n-го порядка D_i ( i=1,2,...,n) получается из определителя системы петём замены i-го столбца свободными членами b₁ , b₂ ,..., b_n.

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

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

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

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

₁x₁ + e₁x₂ = b₁

c₂x₁ + d₂x₂ + e₂x₃ = b₂₃x₂ + d₃x₃ + e₃x₄ = b₃

... ... ..._n-1x_n-2 + d_n-1x_n-1 + e_n-1x_n = b_n-1

c_nx_n-1 + d_nx_n = b_n

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

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

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

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

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

| d_i | ≥ | c _i | + | e_i |

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

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ур

α= -  β=

α₁= - =-0.07087295

α₂= - =0.11764706

α₃= - =0

β₂==0.94117647

β₃==0.81111111

Xn=

X₁= = =0,856526

X₂= = =1,2617

X₃ =  =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/Метод_прогонки>