Сравнение эффективности различных методов решения систем линейных алгебраических уравнений. Метод Крамера и метод простой итерации

Для использования этого метода систему, имеющую вид:

нужно привести к следующему виду (называемому нормальным):

(*)

Затем в полученную систему подставляют начальное приближение решения, т.е. некоторый набор значений и вычисляют следующее приближение решения - набор значений . Полученный набор значений снова подставляют в систему (*) для вычисления следующего приближения и т.д. Процесс повторяется до тех пор, пока не будет достигнута необходимая точность решения. Данный метод сходится при выполнении одного из следующих условий:

(**)

Т.е. метод простой итерации решения СЛАУ сходится, если максимальная из сумм модулей коэффициентов при неизвестных системы (*) взятых по строкам меньше единицы либо если максимальная из сумм модулей коэффициентов при неизвестных системы (*) взятых по столбцам меньше единицы, либо если сумма квадратов всех коэффициентов при неизвестных в правой части системы (*) меньше единицы. Каждое из этих условий является достаточным для сходимости метода, но не необходимым. Это означает, что метод сходится при выполнении хотя бы одного из этих условий, но он так же может сходиться и тогда, когда ни одно из них не выполняется. В данном случае руководствуются эмпирическим правилом: если в ходе итераций некоторая десятичная цифра повторилась 3 и более раз - её можно считать верной.

Во всех остальных случаях (когда выполняется одно из условий (**)) степень приближения к точному решению оценивается по формуле:

,(***)

При выполнении одного из условий (**) в качестве начального значения решения можно взять любой набор значений.

Где б - величина, вычисляемая по одной и формул (**) по которой обнаружена сходимость метода.

Метод простой итерации

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

AX=f (1)

где матрица A - вещественная, неособенная, с диагональным преобладанием; X - искомый вектор решения; f - вектор правой части системы.

Система (1) приводится к каноническому виду:

X=BX+g (2)

(3)

К каноническому виду систему (1) можно привести следующим образом:

(4)

Выбирается вектор начальных приближений

(5)

Итерационная последовательность строится по рекурентной форме:

X(k+1)=BX(k)+g , k=0,1,... (6)

(7)

Итерационный процесс продолжается до тех пор, пока все значения xi(k) не станут близкими к xi(k-1).

Тогда при заданной погрешности e>0 критерий окончания итерационного процесса можно записать в виде:

(8)

По относительным разностям условие окончания итерационного процесса:

(9)

Пример1:

Методом итераций решить систему линейных уравнений с точностью до 0.01, приведя ее к виду, удобному для итераций.

Решение:

Для приведения системы к каноническому виду, мы разделим уравнения первое - на 4, второе - на 3, третье - на 4 (то есть элементы aii):

и далее оставляем в правой части уравнений соответственно x1, x2 и x3: (в принципе, мы воспользовались формулами (4))

Теперь можно применять формулу (6), выбрав начальное приближение:

Найдем 1-ое приближение:

Очевидно, что условие (8) не выполняется, поэтому вычисляем 2-ое приближение:

Проверяем условие (6):

линейный уравнение программирование итерация

Таким образом, для первой координаты вектора решения не выполняется условие (6) - вычисляем 3-е приближение:

Условие (6) выполняется - завершаем итерационный процесс.

Получили вектор решения:

.

1.3 Метод Крамера

Метод Крамера (правило Крамера) -- способ решения квадратных систем линейных алгебраических уравнений с ненулевым определителем основной матрицы (причём для таких уравнений решение существует и единственно). Создан Габриэлем Крамером в 1751 году.[источник не указан 481 день]

Описание метода

Для системы n линейных уравнений с n неизвестными (над произвольным полем)

\begin{cases}

a_{11}x_1 + a_{12}x_2 + \ldots + a_{1n}x_n = b_1\\ a_{21}x_1 + a_{22}x_2 + \ldots + a_{2n}x_n = b_2\\ \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots\cdots\\ a_{n1}x_1 + a_{n2}x_2 + \ldots + a_{nn}x_n = b_n\\ \end{cases}

x_i=\frac{1}{\Delta}\begin{vmatrix}

a_{11} & \ldots & a_{1,i-1} & b_1 & a_{1,i+1} & \ldots & a_{1n} \\ a_{21} & \ldots & a_{2,i-1} & b_2 & a_{2,i+1} & \ldots & a_{2n} \\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\ a_{n-1,1} & \ldots & a_{n-1,i-1} & b_{n-1} & a_{n-1,i+1} & \ldots & a_{n-1,n} \\ a_{n1} & \ldots & a_{n,i-1} & b_n & a_{n,i+1} & \ldots & a_{nn} \\ \end{vmatrix}

(i-ый столбец матрицы системы заменяется столбцом свободных членов). В другой форме правило Крамера формулируется так: для любых коэффициентов c1, c2, …, cn справедливо равенство:

(c_1x_1+c_2x_2+\dots+c_nx_n)\cdot\Delta = -\begin{vmatrix}

a_{11} & a_{12} & \ldots & a_{1n} & b_1\\ a_{21} & a_{22} & \ldots & a_{2n} & b_2\\ \ldots & \ldots & \ldots & \ldots & \ldots\\ a_{n1} & a_{n2} & \ldots & a_{nn} & b_n\\ c_{1} & c_{2} & \ldots & c_{n} & 0\\ \end{vmatrix}

В этой форме формула Крамера справедлива без предположения, что \Delta отлично от нуля, не нужно даже, чтобы коэффициенты системы были бы элементами целостного кольца (определитель системы может быть даже делителем нуля в кольце коэффициентов). Можно также считать, что либо наборы b_1,b_2,...,b_n и x_1,x_2,...,x_n, либо набор c_1,c_2,...,c_n состоят не из элементов кольца коэффициентов системы, а какого-нибудь модуля над этим кольцом. В этом виде формула Крамера используется, например, при доказательстве формулы для определителя Грама и Леммы Накаямы.

Система линейных уравнений:

\begin{cases}

a_{11}x_1 + a_{12}x_2 + a_{13}x_3 = b_1\\ a_{21}x_1 + a_{22}x_2 + a_{23}x_3 = b_2\\ a_{31}x_1 + a_{32}x_2 + a_{33}x_3 = b_3\\ \end{cases}

Определители:

\Delta=\begin{vmatrix}

a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ \end{vmatrix},\ \ \Delta_1=\begin{vmatrix} b_1 & a_{12} & a_{13} \\ b_2 & a_{22} & a_{23} \\ b_3 & a_{32} & a_{33} \\ \end{vmatrix},\ \ \Delta_2=\begin{vmatrix} a_{11} & b_1 & a_{13} \\ a_{21} & b_2 & a_{23} \\ a_{31} & b_3 & a_{33} \\ \end{vmatrix},\ \ \Delta_3=\begin{vmatrix} a_{11} & a_{12} & b_1 \\ a_{21} & a_{22} & b_2 \\ a_{31} & a_{32} & b_3 \\ \end{vmatrix}

Решение:

x_1=\frac{\Delta_1}{\Delta},\ \ x_2=\frac{\Delta_2}{\Delta},\ \ x_3=\frac{\Delta_3}{\Delta}

Пример:

\begin{cases}

2x_1 + 5x_2 + 4x_3 = 30\\ x_1 + 3x_2 + 2x_3 = 150\\ 2x_1 + 10x_2 + 9x_3 = 110\\ \end{cases}

Определители:

\Delta_1=\begin{vmatrix}30&5&4\\150&3&2\\

110 & 10 & 9 \\ \end{vmatrix}=-760,\ \ \Delta_2=\begin{vmatrix} 2 & 30 & 4 \\ 1 & 150 & 2 \\ 2 & 110 & 9 \\ \end{vmatrix}=1350,\ \ \Delta_3=\begin{vmatrix} 2 & 5 & 30 \\ 1 & 3 & 150 \\ 2 & 10 & 110 \\ \end{vmatrix}=-1270. x_1=-\frac{760}{5}=-152,\ \ x_2=\frac{1350}{5}=270,\ \ x_3=-\frac{1270}{5}=-254

Из-за высокой вычислительной сложности метода -- требуется вычисление n+1 определителя размерности n\times n, он не применяется для машинного решения больших СЛАУ. Время, необходимое на вычисление одного определителя примерно такое же, как и время на решение одной системы уравнений при использовании метода Гаусса. Однако он иногда используется при ручном счёте и в теоретических выкладках.

1.4 Алгоритм решения

1.1. Вводим параметр (А) и точность(Е), с которой хотим найти корень, а также начальное и конечное значение X.

1.2. Строим график, чтобы узнать на каком отрезке находятся наши корни.

1.3. Находим корни двумя способами.

1.4. Сравниваем время, затраченное на решения первым и вторым способом.

1.5 Алгоритм решения (блок-схема)

Метод последовательных приближений:

Рисунок 1.1 - Блок-схема (метод последовательных приближений)

Метод касательных:

Рисунок 1.2 - Блок-схема (метод касательных)

2. ПРАКТИЧЕСКАЯ ЧАСТЬ

2.1 Реализация алгоритма решения

Программа состоит из двух форм (Form). frmMain - является главной формой программы, на которой расположены четыре компонента Label, четыре компонента Edit, один компонент Chart, два компонента Memo и четыре компонента Button. Компоненты Edit служат для ввода параметра, точности, начального и конечного значения отрезка, компонент Chart для построения графика, компоненты Memo для вывода результатов вычисления, компоненты Button для построения графика, нахождения корней, вывода справки и выхода, соответственно их надписям. Основное окно программы представлено на рисунке 2.1.

Рисунок 2.1 - Основное окно программы

При нажатии на кнопку "Справка" откроется окно справка - это третья форма программы. На этой форме расположен один компонент Memo и один компонент Button. Эта форма содержит сведения о программе и об авторе программы, кнопка расположена для закрытия справки. Окно справка представлено на рисунке 2.2.

Рисунок 2.2 - Окно справка

2.2 Результат выполнения программы

При любом параметре a данное уравнение имеет бесконечное множество решений. Поэтому для выполнения условий, когда уравнение имеет один корень, много корней или не имеет корней, будем рассматривать функцию с определённым параметром a=1, выбирая различные отрезки.

Возьмём отрезок [0;6].

При параметре a=1 на этом отрезке будет находиться три корня. Следуя вышеуказанному алгоритму, мы вводим исходные данные, строим график и находим корни. Результат показан на рисунке 2.3. В результате выполнения мы получаем три различных корня.

Возьмём отрезок [1;4].

При параметре a=1 на этом отрезке будет находиться один корень. Следуя вышеуказанному алгоритму, мы вводим исходные данные, строим график и находим корни. Результат показан на рисунке 2.4. В результате выполнения мы получаем один корень.

Возьмём отрезок [7;9].

При параметре a=1 на этом отрезке корни отсутствуют. Следуя вышеуказанному алгоритму, мы вводим исходные данные, строим график и находим корни. Результат показан на рисунке 2.5. В результате выполнения мы видим, что на отрезке корней нет.

Рисунок 2.3 - Результат выполнения алгоритма

Рисунок 2.4 - Результат выполнения алгоритма

Рисунок 2.5 - Результат выполнения алгоритма

Если взять отрезок [-5;0], то, выполняя алгоритм, программа не сможет уточнить один из корней методом последовательных приближений (рисунок 2.6). Это объясняется тем, что корень находится вблизи точки бесконечного разрыва, в котором функция имеет большую по модулю производную. Это оказывает влияние на условие |S (x)| < 1.

Рисунок 2.6 - Результат выполнения алгоритма

ЗАКЛЮЧЕНИЕ

Цель данной курсовой работы разработка проекта по вычислению корней нелинейных уравнений методом касательных и методом отделения корней, в среде программирования Delphi. Сравним полученные результаты при вычислении.

В задании требуется: коэффициент a подобрать самостоятельно так, чтобы уравнение не имело корней, имело один корень, имело более одного корня.

В первом двух случаях уравнение имеет три корня и один корень на отрезках [0;6] и [1;4] соответственно(при параметре a=1), и как мы видим на рисунках 2.3 и 2.4 количество итераций методом последовательных приближений значительно больше чем количество итераций методом касательных(119>41;50>15). Время выполнения методом последовательных приближений также больше чем методом касательных (0,0468>0,0297; 0,0188>0,0140). Следовательно, можно сказать, что скорость выполнения алгоритма метода касательных выше чем метода последовательных приближений. Найденные корни x₁=0,1210135632, x₂=3,6600989630, x₃=5,3408862820. В третьем случаи на отрезке [7;9](при параметре a=1) уравнение не имеет корней, т.к. на графике(при увеличении) видно что функция не пересекает ось Ох(имея точку бесконечного разрыва).

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Бобровский, С. И. Delphi 7. Учебный курс - СПб.: Питер, 2004. - 238 c.: ил.

2. Фленов, М. Е. Библия Delphi. - 2-е изд., перераб. И доп. - СПб.: БХВ-Петербург, 2008. - 800 с.: ил.

3. Кудряшов, Н. А. Аналитическая теория нелинейных дифференциальных уравнений. Москва-Ижевск: Институт компьютерных исследований, 2004. - 429 с.: ил.

4. Полянин, А. Д., Зайцев, В. Ф. Справочник по нелинейным уравнениям математической физики. М.: Физматлит, 2002. - 315 с.: ил.

ПРИЛОЖЕНИЕ

Листинг программы

unit kurs;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, TeEngine, Series, ExtCtrls, TeeProcs, Chart, StdCtrls,math,

Menus, XPMan;

type

TfrmMain = class(TForm)

chrtMy: TChart;

Edit1: TEdit;

lbl1: TLabel;

edXmax: TEdit;

Label2: TLabel;

Label1: TLabel;

edXmin: TEdit;

Series1: TFastLineSeries;

Button1: TButton;

btn4: TButton;

mmo1: TMemo;

Mmo2: TMemo;

Button2: TButton;

Edit2: TEdit;

Label3: TLabel;

Button3: TButton;

procedure FormCreate(Sender: TObject);

procedure btn4Click(Sender: TObject);

procedure Button1Click(Sender: TObject);

procedure Button2Click(Sender: TObject);

procedure Button3Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Xmin,Xmax,h,a,timer,timer1,timer2,time1,time2: real;sit1,sit2,kor,it1,it2,p:Integer;

frmMain: TfrmMain;

implementation

uses Unit1;

{$R *.dfm}

Function f(x,a:real):real;

begin

if (x<>0) then

f:=a*(tan(x))+a*ln(abs(sin(x)))+a*a*a*cos(x)+a

else f:=f(0.001,a);

end;

Function f1(x,a:real):real;

begin

f1:=a/(cos(x)*cos(x))+a*(cos(x)/sin(x))+a*a*a*(-sin(x))+a;

end;

procedure PoslPribl(z:real);

var x,xn,xk,x0,t,a,eps,u:real;s,i:Integer;

begin

timer:=0;it1:=0;

a:=StrToFloat(frmMain.Edit1.Text);

xn:=StrToFloat(frmMain.edXmin.text);

xk:=StrToFloat(frmMain.edxmax.text);

eps:=StrToFloat(frmMain.edit2.text)/10;

s:=Abs(Trunc(Log10(StrToFloat(frmMain.edit2.text))));

timer:=GetTickCount;

for i:=1 to 10000 do

begin

x:=z;

repeat

begin

x0:=x;

t:=f(x0,a)/10;

x:=x0-t;

inc(it1);

end;

until abs(t)<eps;

end;

timer:=(GetTickCount-timer)/10000;

it1:=Trunc(it1/10000);

if (x<=z) or (x>(z+0.1)) then frmMain.mmo1.lines.add(Корень уточнить не удалось x'+inttostr(kor)+'='+floattostr(z)) else

frmMain.mmo1.lines.add('x'+inttostr(kor)+'='+floattostrf(x,ffFixed,s,s));

end;

procedure Kasat(z:real);

var x,xn,xk,x0,t,eps,a:real;s,i:Integer;

begin

timer:=0;it2:=0;

a:=StrToFloat(frmMain.Edit1.Text);

xn:=StrToFloat(frmMain.edXmin.text);

xk:=StrToFloat(frmMain.edxmax.text);

eps:=StrToFloat(frmMain.edit2.text);

s:=Abs(Trunc(Log10(StrToFloat(frmMain.edit2.text))));

timer:=GetTickCount;

for i:=1 to 10000 do

begin

x:=z;

repeat

begin

x0:=x;

t:=f(x0,a)/f1(x0,a);

x:=x0-t;

inc(it2);

end;

until abs(t)<eps;

end;

timer:=(GetTickCount-timer)/10000;

it2:=Trunc(it2/10000);

if (x<=z) or (x>(z+0.1)) then frmMain.mmo1.lines.add(Корень уточнить не удалось x'+inttostr(kor)+'='+floattostr(z)) else

frmMain.mmo2.lines.add('x'+inttostr(kor)+'='+floattostrf(x,ffFixed,s,s));

end;

procedure TfrmMain.FormCreate(Sender: TObject);

begin

h:=0.001;

mmo1.Clear;mmo2.Clear;

end;

procedure TfrmMain.Button1Click(Sender: TObject);

var x,y1:real;

begin

a:=strtofloat(frmMain.Edit1.Text);

Series1.Clear;

Xmin :=strtofloat(edXmin.Text);

Xmax :=strtofloat(edXmax.Text);

x:=Xmin;

repeat

{if (x<>0) then}

y1:=f(x,a);

Series1.AddXY(x,y1,'',clTeeColor);

x:=x+h;

until x>Xmax;

end;

procedure TfrmMain.btn4Click(Sender: TObject);

var x,eps:real;

begin

sit1:=0;sit2:=0;

kor:=0;

mmo1.Clear;Mmo2.Clear;

mmo1.Lines.Add('Метод последовательных приближений:');

mmo2.Lines.Add('Метод касательных:');

time1:=0;

time2:=0;

a:=StrToFloat(Edit1.Text);

x:=Xmin;

eps:=0.1;

repeat

{if (x<>0) and (x<>eps) and (x<>-eps) and (x<>2*eps) then }

if (f(x,a)*f(x+eps,a)<0) and ((f(x,a)-f(x+eps,a))<10) then

if ((f(x,a)<f(x-eps,a)) and (f(x+eps,a)>f(x+2*eps,a))) or ((f(x,a)>f(x-eps,a)) and (f(x+eps,a)<f(x+2*eps,a))) then

begin

inc(kor);

PoslPribl(x);

sit1:=sit1+it1;

time1:=time1+timer;

Kasat(x);

time2:=time2+timer;

sit2:=sit2+it2;

end;

x:=x+eps;

until x>=Xmax;

if kor=0 then begin frmMain.mmo1.lines.add(''Корней нет'');frmMain.mmo2.lines.add('Корней нет') end;

frmMain.mmo1.lines.add('------------------');frmMain.mmo2.lines.add('------------------');

frmMain.Mmo1.Lines.Add('Время :'+FloatToStrf(time1,fffixed,8,4)+'in');frmMain.Mmo2.Lines.Add('Время :'+FloatToStrf(time2,fffixed,8,4)+'in');

frmMain.mmo1.lines.add('Количество итераций:'+floattostr(sit1));frmMain.mmo2.lines.add('Количество итераций:'+floattostr(sit2));

end;

procedure TfrmMain.Button2Click(Sender: TObject);

begin

Application.Terminate;

end;

procedure TfrmMain.Button3Click(Sender: TObject);

begin

form1.Show;

end;end.

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls;

type

TForm1 = class(TForm)

btn1: TButton;

mmo1: TMemo;

procedure btn1Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.btn1Click(Sender: TObject);

begin

Form1.Close;

end;end.

Размещено на Allbest.ru