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

 

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ

"БАРАНОВИЧСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ"

КУРСОВАЯ РАБОТА

по дисциплине Основы алгоритмизации и программирования

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

Исполнитель:

студент 1 курса группы ИСТ-11

Сенько Дарья Ивановна

Руководитель:

Климко Елена Викторовна

Барановичи 2010

РЕФЕРАТ

Курсовая работа: 17 с., 7 иллюстр., 4 источника.

Решение нелинейных уравнений.

Объектом и предметом исследования является методы решения нелинейных уравнений.

Цель работы - разработка программы, которая будет решать СЛАУ двумя способами: методом Крамера и методом простой итерации.

При выполнении работы использованы методы: изучение литературы, разработка и отладка программы на компьютере.

Областью возможного практического применения являются научно-исследовательская работа.

Автор подтверждает, что приведенный в работе расчетно-аналитический материал правильно и объективно отражает состояние исследуемого процесса, а все заимствованные из литературных и других источников теоретические, методологические и методические положения и концепции сопровождаются ссылками на их авторов.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

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

.2 Метод простой итерации решения СЛАУ

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

ПРИЛОЖЕНИЕ

ВВЕДЕНИЕ

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

Система линейных алгебраических уравнений имеет вид:

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

Используемые в наше время методы решения СЛАУ разбивают на 2 группы:

. Точные методы - это методы, в которых вычисления ведутся без округлений и приводят к точным значениям неизвестных. Но так как на практике используемые данные имеют некоторую ограниченную точность, то используемые точные методы решения неизбежно будут содержать погрешности. К точным методам относится метод Гаусса решения СЛАУ.

. Приближённые методы - это методы, которые даже при вычислении без округлений позволяют получить решение системы лишь с какой-то заданной точностью. Точное решение системы в этом случае может быть получено теоретически, как результат бесконечного процесса. К приближённым методам решения СЛАУ относят методы простой итерации, метод Зейделя и другие.

Наиболее эффективно программируемым на ЭВМ являются метод Гаусса с выбором главного элемента в матрице и метод Зейделя. Если при экспериментальных исследованиях получаются приближенные значения коэффициентов СЛАУ, то сначала решают методом Гаусса с выбором главного элемента, а затем уточняют решение методом Зейделя.

1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

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

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

Программа должна соответствовать следующим требованиям:

-быть доступной для любого уровня подготовки пользователя, использующего данную программу;

-соответствовать современному уровню программирования;

1.2 Метод простой итерации решения СЛАУ

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

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

(*)

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

(**)

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

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

,(***)

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

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

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

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

=f (1)

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

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

=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}_{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}_{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}_{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}_{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}

Решение:

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

Пример:

\begin{cases}

x_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\\

& 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.Вводим параметр (А) и точность(Е), с которой хотим найти корень, а также начальное и конечное значение X.

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

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

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

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

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

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

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

Рисунок 1.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 Результат выполнения программы

При любом параметре 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). Следовательно, можно сказать, что скорость выполнения алгоритма метода касательных выше чем метода последовательных приближений. Найденные корни x1=0,1210135632, x2=3,6600989630, x3=5,3408862820. В третьем случаи на отрезке [7;9](при параметре a=1) уравнение не имеет корней, т.к. на графике(при увеличении) видно что функция не пересекает ось Ох(имея точку бесконечного разрыва).

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

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

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

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

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

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

ПРИЛОЖЕНИЕ

Листинг программыkurs;, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, TeEngine, Series, ExtCtrls, TeeProcs, Chart, StdCtrls,math,, XPMan;= class(TForm): TChart;: TEdit;: TLabel;: TEdit;: TLabel;: TLabel;: TEdit;: TFastLineSeries;: TButton;: TButton;: TMemo;: TMemo;: TButton;: TEdit;: TLabel;: TButton;FormCreate(Sender: TObject);btn4Click(Sender: TObject);Button1Click(Sender: TObject);Button2Click(Sender: TObject);Button3Click(Sender: TObject);

{ Private declarations }

{ Public declarations };,Xmax,h,a,timer,timer1,timer2,time1,time2: real;sit1,sit2,kor,it1,it2,p:Integer;: TfrmMain;

implementationUnit1;

{$R *.dfm}f(x,a:real):real;(x<>0) then:=a*(tan(x))+a*ln(abs(sin(x)))+a*a*a*cos(x)+af:=f(0.001,a);;f1(x,a:real):real;:=a/(cos(x)*cos(x))+a*(cos(x)/sin(x))+a*a*a*(-sin(x))+a;;PoslPribl(z:real);x,xn,xk,x0,t,a,eps,u:real;s,i:Integer;:=0;it1:=0;:=StrToFloat(frmMain.Edit1.Text);:=StrToFloat(frmMain.edXmin.text);:=StrToFloat(frmMain.edxmax.text);:=StrToFloat(frmMain.edit2.text)/10;:=Abs(Trunc(Log10(StrToFloat(frmMain.edit2.text))));:=GetTickCount;i:=1 to 10000 do:=z;:=x;:=f(x0,a)/10;:=x0-t;(it1);;abs(t)<eps;;:=(GetTickCount-timer)/10000;:=Trunc(it1/10000);(x<=z) or (x>(z+0.1)) then frmMain.mmo1.lines.add(Корень уточнить не удалось x'+inttostr(kor)+'='+floattostr(z)) else.mmo1.lines.add('x'+inttostr(kor)+'='+floattostrf(x,ffFixed,s,s));;Kasat(z:real);x,xn,xk,x0,t,eps,a:real;s,i:Integer;:=0;it2:=0;:=StrToFloat(frmMain.Edit1.Text);:=StrToFloat(frmMain.edXmin.text);:=StrToFloat(frmMain.edxmax.text);:=StrToFloat(frmMain.edit2.text);:=Abs(Trunc(Log10(StrToFloat(frmMain.edit2.text))));:=GetTickCount;i:=1 to 10000 do:=z;:=x;:=f(x0,a)/f1(x0,a);:=x0-t;(it2);;abs(t)<eps;;:=(GetTickCount-timer)/10000;:=Trunc(it2/10000);(x<=z) or (x>(z+0.1)) then frmMain.mmo1.lines.add(Корень уточнить не удалось x'+inttostr(kor)+'='+floattostr(z)) else.mmo2.lines.add('x'+inttostr(kor)+'='+floattostrf(x,ffFixed,s,s));;TfrmMain.FormCreate(Sender: TObject);:=0.001;.Clear;mmo2.Clear;;TfrmMain.Button1Click(Sender: TObject);x,y1:real;:=strtofloat(frmMain.Edit1.Text);.Clear;:=strtofloat(edXmin.Text);:=strtofloat(edXmax.Text);:=Xmin;

{if (x<>0) then}:=f(x,a);.AddXY(x,y1,'',clTeeColor);:=x+h;x>Xmax;;TfrmMain.btn4Click(Sender: TObject);x,eps:real;:=0;sit2:=0;:=0;.Clear;Mmo2.Clear;1.Lines.Add('Метод последовательных приближений:');

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

time1:=0;:=0;:=StrToFloat(Edit1.Text);:=Xmin;:=0.1;

{if (x<>0) and (x<>eps) and (x<>-eps) and (x<>2*eps) then }(f(x,a)*f(x+eps,a)<0) and ((f(x,a)-f(x+eps,a))<10) then((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(kor);(x);:=sit1+it1;:=time1+timer;(x);:=time2+timer;:=sit2+it2;;:=x+eps;x>=Xmax;kor=0 then begin frmMain.mmo1.lines.add(''Корней нет'');frmMain.mmo2.lines.add('Корней нет') end;.mmo1.lines.add('------------------');frmMain.mmo2.lines.add('------------------');.Mmo1.Lines.Add('Время :'+FloatToStrf(time1,fffixed,8,4)+'ìñ');frmMain.Mmo2.Lines.Add('Время :'+FloatToStrf(time2,fffixed,8,4)+'ìñ');.mmo1.lines.add('Количество итераций:'+floattostr(sit1));frmMain.mmo2.lines.add('Количество итераций:'+floattostr(sit2));;TfrmMain.Button2Click(Sender: TObject);.Terminate;;TfrmMain.Button3Click(Sender: TObject);.Show;;end.Unit1;, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, StdCtrls;= class(TForm): TButton;: TMemo;btn1Click(Sender: TObject);

{ Private declarations }

{ Public declarations };: TForm1;

{$R *.dfm}TForm1.btn1Click(Sender: TObject);.Close;;end.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ "БАРАНОВИЧСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ"

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