Анализ и сравнение численных методов решения нелинейных уравнений

Министерство образования и науки Российской федерации

Стерлитамакский филиал

федерального государственного бюджетного образовательного учреждения

высшего профессионального образования

«Башкирский государственный университет»

 

 

Экономический факультет

Кафедра математического моделирования

 

 

 

 

 

 

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

на тему: ««Анализ и сравнение численных методов решения нелинейных

 уравнений»

 

 

 

 

 

Выполнили студенты 3 курса                 

                     группы БИ-31 

                     Серебряков Е.А.________

      Федоров С.О.__________

                   «___»__________2014г.

 

 

Научный руководитель                                       к.ф.-м.н., доцент

                                                                               Карасев Е.М. __________

                      «___»____________2014г.

 

 

 

 

 

СТЕРЛИТАМАК – 2014

Содержание

 

1. Введение            3
2. Численные методы решения нелинейных

уравнений           5

3. Постановка задачи               6
4. Основные методы решения нелинейных 

уравнений                                7

5.1.  Метод половинного деления       8

5.2. Метод  касательных        11

5.3.  Метод хорд          14

5. Практическая часть         19
6. Заключение          26
7. Список используемой литературы       27

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

Решение систем нелинейных алгебраических уравнений – одна из сложных и до конца не решенных задач. Даже о расположении и существовании корней систем нелинейных уравнений почти ничего нельзя сказать. Большинство методов решения систем нелинейных уравнений сходятся к решению, если начальное приближение достаточно близко к нему, и могут вообще не давать решения при произвольном выборе начального приближения. Условия и скорость сходимости каждого итерационного процесса существенно зависят от свойств уравнений, то есть от свойств матрицы системы, и от выбора начальных приближений.

В своей курсовой работе я поставила три основные цели и задачи:

1. Изучение разновидности комбинаторных задач.
2. Изучение основных комбинаторных операций.
3. Изучение комбинаторики как раздел элементарной алгебры.

Для достижения поставленных целей и решения задач в курсовой работе я использовала различные источники информации. В основном это были книги Бахвалов Н. С. Численные методы и Вержбицкий В. М. Численные методы. Линейная алгебра и нелинейные уравнения. В них четко и точно изложен нужный для моей курсовой работы материал.

Курсовая работа построена таким образом, что сначала идут сведения о численных методах в целом, а уже после более подробно  рассмотрены решения нелинейных уравнений.

 

Численные методы.

Проблема численного решения линейных уравнений интересует математиков уже несколько столетий. Первые математические результаты появились в XVIII веке. В 1750 году Г. Крамер (1704-1752) опубликовал свои труды по детерминантам квадратных матриц и предложил алгоритм нахождения обратной матрицы, известный как правило Крамера. Гаусс в 1809 году опубликовал работу, посвященную движению небесных тел, в которой был изложен метод для решения линейных систем, известный как метод исключения.

В 40-х годах XX века с появлением компьютеров сильно возрос интерес к численным методам. Тогда же началось активное исследование существующих методов для их реализации на ЭВМ и предпринимались активные попытки увеличить их точность.

Вплоть до 80-х годов решение вычислительных задач было ограничено ресурсами ЭВМ, поэтому особое значение придавалось экономичности алгоритмов.

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

 

 

 

 

 

 

 

 

 

 

 

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

Пусть имеется уравнение вида

                                   f (x) = 0.                                                 

где f (x)  - заданная алгебраическая или трансцендентная функция. (Функция называется алгебраической, если для получения её значения нужно выполнить арифметические операции и возведение в степень с рациональным показателем. Примеры трансцендентных функций - показательная, логарифмическая, тригонометрические, обратные тригонометрические.)

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

Поставим задачу найти такое приближенное значение корня xпр, которое мало отличается от точного значения корня x*, так что выполняется неравенство │x* – xпр │< e , где e (эпсилон) – малая положительная величина – допустимая ошибка, которую мы можем заранее задать по своему усмотрению. Если корень найден с точностью e, то принято писать x*=xпр±e.

Будем предполагать, что уравнение (1) имеет лишь изолированные корни, т.е. для каждого корня существует окрестность, не содержащая других корней этого уравнения.

 

Основные методы решения нелинейных уравнений

Уравнение типа F(x)=0 или x=f(x) называется нелинейным. Решить уравнение это значит найти такое x, при котором уравнение превращается в тождество. В общем случае уравнение может иметь 0; 1; 2;...∞ корней. Рассмотренные ниже численные методы решения нелинейных уравнений позволяют находить один корень на заданном интервале [a,b]. При этом на интервале должен существовать только один корень. Рассмотрим несколько методов решения нелинейных уравнений.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Метод половинного деления.

Метод деления отрезка пополам имеет другие названия: метод половинного деления, метод дихотомии, метод проб, метод бисекций. 
Пусть корень уравнения f (x) = 0 отделен на отрезке[a;b] , т.е. f(a)∙f(b)<0. 
Алгоритм приближенного вычисления корня методом половинного деления. 
Исходные данные: f (x) – функция; ε – требуемая точность; a, b – границы заданного интервала (границы поиска корня). 
Результат: xпр – приближенный корень уравнения f (x) = 0.

Метод решения:

Шаг 1. Выбрать середину   отрезка[a;b]  в качестве приближенного корня.

Шаг 2. Если f(c)=0, то c – искомый корень уравнения, на этом прекращаем вычисления. В противном случае перейти к шагу 3.

Шаг 3. Точный корень уравнения x* отличается от c не более чем на половину длины отрезка, т.е. не более чем на (полученная точность). Проверяем условие . Если условие не выполняется, т.е. полученная точность нас не устраивает (она больше, чем требуемая), то перейти к шагу 4; в противном случае прекратить вычисления, поскольку мы достигли требуемой точности, и приближенным корнем уравнения f(x) = 0 считать середину c  отрезка [a;b] .

Шаг 4. Определить интервал дальнейшего поиска корня. Из двух образовавшихся при делении отрезков переходим к той из его половин [a;c]  и [c;b] , на концах которого функция принимает значения разных знаков. 
Случай 1 (рис. 1). Корень на отрезке [a;c]. f(a)∙f(c)≤0, граница b сдвигается влево – заменить b на с: b:= c.

 
Рис. 1. Графическая иллюстрация метода половинного деления.

Случай 2 (рис. 1). Корень на отрезке [c;b] . f(a)∙f(c)>0, граница a сдвигается вправо – заменить a на с: a:= c.

Перейти к шагу 1.

Алгоритм деления отрезка пополам довольно медленный, но зато абсолютно застрахован от неудач. Основное достоинство метода состоит в том, что его скорость сходимости не зависит от вида функции f (x). Данный метод не имеет дополнительных условий сходимости, кроме f(a)∙f(b)<0.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                              Блок-схема программы 

 

 

 

 

 

 

 

 НЕТ ДА

 

 

 

 

 ДА НЕТ

 

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

Пусть на отрезке [a; b] отделен корень с уравнения f (x) = 0 и f -функция непрерывна на отрезке [a; b], а на интервале  (a; b) существуют отличные от нуля производные f ’ и f ”.

Так как f ’(x) ¹ 0 , то запишем уравнение f (x) = 0 в виде:

x = x – ( f (x) / f ’(x))     (1)

Решая его методом итераций можем записать:

xn+1 = x n– ( f (x n) / f ’(x n))    (2)

Если на отрезке [a;b]   f ’(x) * f “(x) > 0, то нулевое приближение выбираем x0=a. Рассмотрим геометрический смысл метода. Рассмотрим график функции y=f(x). Пусть для определенности f ‘(x) > 0 и f “(x) > 0 (рис. 1). Проведем касательную к графику функции в точке B (b, f (b)). Ее уравнение будет иметь вид:

y = f (b) + f ’(b) * (x – b)

Полагая в уравнении y = 0 и учитывая, что f ’(x) ¹ 0, решаем его относительно x. Получим :

x = b – (f (b) /f ‘(b))

Нашли абсциссу x1 точки c1 пересечения касательной с осью Оx:

x1 = b – (f (b) – f ’ (b))

Проведем  касательную к графику функции в точке b1 (x1; f (x1)).Найдем абсциссу x2 точки с2 пересечения касательной с осью Ox:

x2 = x1 – (f (x1) / ( f ’(x1))

Вообще :

xk+1 = x k – ( f (x k) / f ’(x k))     (3)

Таким образом, формула (3) дает последовательные приближения (xk) корня, получаемые из уравнения касательной , проведенной к графику функции в точке         b k (x k; f (x k0) метод уточнения корня  c  [a;b] уравнения f (x) = 0 с помощью формулы (3) называется методом касательной или методом Ньютона.

Геометрический смысл метода касательных состоит в замене дуги y = f (x) касательной, одной к одной  из крайних точек . Начальное приближение x 0=a или    x0 = b брать таким, чтобы вся последовательность приближения х k принадлежала интервалу  (a;b). В случае существования производных f ’, f ”, сохраняющих свои знаки в интервале, за х0 берется тот конец отрезка [a;b], для которого выполняется условие  f ’(х0) * f (х0) > 0. Для оценки приближения используется общая формула :

|c-x k-1 | £ | f (x k+1)/m| , где m = min f ’(x) на отрезке [a;b] .

На практике проще пользоваться другим правилом :

Если на отрезке [a;b] выполняется условие  0 < m <  | f (x)|  и e - заданная точность решения, то неравенство | x k+1-x k| £ e влечет выполнение неравенства       |c-x k-1| £ e .

В этом случае процесс последовательного приближения продолжают до тех пор, пока не выполнится неравенство:

|c-x k-1| £ e .

 

 

 

 

 

 

 

 

 

                              Блок-схема программы

 

 

 

 

 

 

 

                                                               НЕТ

 

 

 ДА

 
Метод хорд.

Пусть на отрезке [a;b] функция непрерывна, принимает на концах отрезка значение разных знаков, а производная f '(x) сохраняет знак. В зависимости от знака второй производной возможны следующие случаи расположения кривых (рис. 1).

 
 

Рис. 1. Возможные случаи расположения кривых.

Алгоритм приближенного вычисления корня методом хорд. 
Исходные данные: f (x) – функция; ε – требуемая точность; x0 – начальное приближение. 
Результат: xпр – приближенный корень уравнения f (x) = 0.

Метод решения: 

Рис. 2. Геометрическая интерпретация метода хорд для случая f '(x) f ''(x)>0.

Рассмотрим случай, когда f '(x)  и f ''(x)  имеют одинаковые знаки (рис. 2).

График функции проходит через точки A0(a,f(a)) и B0(b,f(b)). Искомый корень уравнения (точка x*) нам неизвестен, вместо него возьмет точку х1 пересечения хорды А0В0 с осью абсцисс. Это и будет приближенное значение корня. 
В аналитической геометрии выводится формула, задающая уравнение прямой, проходящей через две точки с координатами (х1; у1) и (х2; у2): . 
Тогда уравнение хорды А0В0 запишется в виде: . 
Найдем значение х = х1, для которого у = 0:  . Теперь корень находится на отрезке [x1;b]. Применим метод хорд к этому отрезку. Проведем хорду, соединяющую точки A1(x1,f(x1)) и B0(b,f(b)), и найдем х2 - точку пересечения хорды А1В0 с осью Ох: x2=x1 . 
Продолжая этот процесс, находим: x3=x2. Получаем рекуррентную формулу вычисления приближений к корню xn+1=xn. 
В этом случае конец b отрезка [a;b]  остается неподвижным, а конец a перемещается. 
Таким образом, получаем расчетные формулы метода хорд:

xn+1=xn;         x0=a.                                     (4)

Вычисления очередных приближений к точному корню уравнения продолжается до тех пор, пока не достигнем заданной точности, т.е. должно выполняться условие: |xn+1-xn|<, где - заданная точность. 
Теперь рассмотрим случай, когда первая и вторая производные имеют разные знаки, т.е. f '(x) f ''(x)<0. (рис. 3).

 
Рис. 3. Геометрическая интерпретация метода хорд для случая f '(x) f ''(x)<0.

Соединим точки A0(a,f(a)) и B0(b,f(b))  хордой А0В0. Точку пересечения хорды с осью Ох будем считать первым приближение корня. В этом случае неподвижным концом отрезка будет являться конец а. 
Уравнение хорды А0В0:. Отсюда найдем x1, полагая y = 0: x1=b. Теперь корень уравнения x[a;x1]. Применяя метод хорд к этому отрезку, получим x2=x1. Продолжая и т.д., получим xn+1=xn. 
Расчетные формулы метода:

xn+1=xn, x0=0 .                                                           (5) 
Условие окончания вычислений: |xn+1-xn|<. Тогда хпр = xn+1 с точностью Итак, если f '(x) f ''(x)>0 приближенное значение корня находят по формуле (4), если f '(x) f ''(x)<0, то по формуле (5).

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

Пример. Проиллюстрировать действие этого правила на уравнении

(x-1)ln(x)-1=0, если отрезок изоляции корня [2;3].

Решение. Здесь f(x)=(x-1)ln(x)-1.

f '(x)=ln(x)+;

 f ''(x)=.

Вторая производная в этом примере положительна на отрезке изоляции корня [2;3]: f ''(x)>0, f(3)>0, т.е. f(b) f''(x)>0. Таким образом, при решении данного уравнения методом хорд для уточнения корня выбираем формулы (4).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Блок-схема программы

 

 

 

 

 

                                                   Нет

 

 ДА

 

 

 

 

 

 

 

 

 

Практическая часть

unit Unit1;

interface

uses

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

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

type

  TForm1 = class (TForm)

    Label3: TLabel;

    Button1: TButton;

    Edit3: TEdit;

    Edit4: TEdit;

    Chart1: TChart;

    Series1: TFastLineSeries;

    Edit2: TEdit;

    Edit5: TEdit;

    Button3: TButton;

    Label2: TLabel;

    Button2: TButton;

    Label4: TLabel;

    Button4: TButton;

    Button5: TButton;

    Panel1: TPanel;

    Panel2: TPanel;

    Edit6: TEdit;

    Label5: TLabel;

    Panel3: TPanel;

    Edit9: TEdit;

    Label8: TLabel;

    Button6: TButton;

    Button7: TButton;

    Button8: TButton;

    Button9: TButton;

    Label6: TLabel;

    Label7: TLabel;

    Label1: TLabel;

    procedure Button1Click(Sender: TObject);

    procedure Button3Click(Sender: TObject);

    procedure Button2Click(Sender: TObject);

    procedure Button4Click(Sender: TObject);

    procedure Button5Click(Sender: TObject);

    procedure Button6Click(Sender: TObject);

    procedure Button7Click(Sender: TObject);

    procedure Button8Click(Sender: TObject);

    procedure Button9Click(Sender: TObject);

  //  procedure Label3Click(Sender: TObject);

  

  private

    { Private declarations }

  public

    { Public declarations }

  end;

var

  Form1: TForm1;

implementation

uses Unit2;

{$R *.dfm}

function F(x:real): real;

begin

result:=2*cos((x+pi/6))+x*x-4*x+3;

end;

 

function F1(x:real): real;

begin

result:=2*(x-1/6*(6*x+pi)*sin(x)+cos(x)-2);

end;

procedure TForm1.Button1Click(Sender: TObject);

Var a,y,x0,y1,b,x1,xn,xn1: real;

    x,e, Fx, Fx1: real;

begin

e:=strtofloat(edit3.Text);

a:=StrToFloat(Edit2.Text);

b:=StrToFloat(Edit5.Text);

x0:=a;

x:=x0-f(x0)/f1(x0);

repeat

begin

  x1:=x;

  y:=f(x);

  y1:=f1(x);

  x:=x-y/y1;

end;

until   (x-x1)>e;

Repeat

x:=x-(F(x)/F1(x));

Until abs(f(x))<e;

edit4.Text:=FloatToStr(x);

end;

procedure TForm1.Button3Click(Sender: TObject);

var

a,b,h: real;

i,n: integer;

begin

a:=StrToFloat(Form1.Edit2.Text);

b:=StrToFloat(Form1.Edit5.Text);

n:=100;

h:=(b-a)/n;

Form1.Series1.AddXY(a,f(a));

for i:=1 to n do

Form1.Series1.AddXY(a+h*i,f(a+h*i));

end;

procedure TForm1.Button2Click(Sender: TObject);

begin

Form1.Series1.Clear;

end;

procedure TForm1.Button4Click(Sender: TObject);

var x,c,a,b,e:real;

begin

  e:=strtofloat(Edit6.Text);

  a:=strtofloat(edit2.Text);

  b:=strtofloat(edit5.Text);

repeat

c:=(a+b)/2;

if f(a)*f(c)<0 then b:=c else a:=c;

until b-a<e;

x:=(a+b)/2;

  begin

   edit4.Text:=FloatToStr(x);

  end;

end;

 

procedure TForm1.Button5Click(Sender: TObject);

Var a,b,c,g,e,x,x0,x1,y:real;

     Fx: real;

begin

e:=strtofloat(edit9.text);

a:=strtofloat(edit2.Text);

b:=strtofloat(edit5.Text);

c:=a;

repeat

g:=c;

c:=(a*f(b)-b*f(a))/(f(b)-f(a));

if f(a)*f(c)<0 then b:=c else a:=c;

until abs(c-g)<e;

Form1.Edit4.Text:=(floattostr(c));

end;

procedure TForm1.Button6Click(Sender: TObject);

begin

panel1.Visible:=true;

panel2.Visible:=false;

panel3.Visible:=false;

end;

procedure TForm1.Button7Click(Sender: TObject);

begin

panel2.Visible:=true;

panel1.Visible:=false;

panel3.Visible:=false;

end;

procedure TForm1.Button8Click(Sender: TObject);

begin

panel3.Visible:=true;

panel1.Visible:=false;

panel2.Visible:=false;

end;

procedure TForm1.Button9Click(Sender: TObject);

begin

form2.showmodal;

end;

end.

 

 

Метод касательных
Точность	0,001
Интервал	(-1,2)
Ответ	1,02390

 

 

 

 

 

 

 

 

 

Метод половинного деления
Точность	0,001
Интервал	(-1,2)
Ответ	1,02404

 

 

 

Метод хорд
Точность	0,001
Интервал	(-1,2)
Ответ	1,02383

 

 

 

 

 

 

 

Заключение.

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

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

Проведя исследования по теме курсовой работы "Численные методы. Решение нелинейных уравнений", мы добились поставленных  во введении целей. К каждому определению и теореме были приведены несколько примеров. Все теоремы доказаны.

Использование различных источников дало возможность полностью раскрыть тему.

 

 

 

 

 

 

 

 

 

 

 

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

1. Бахвалов Н. С. Численные методы  М.: БИНОМ. Лаб. знаний, 2007. 632с.

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

3. Вержбицкий В. М. Численные методы. Линейная алгебра и нелинейные уравнения. М.: Высш.шк., 2006. 268 с.

4. Вержбицкий В. М. Численные методы. Математический анализ и обыкновенные дифференциальные уравнения. М.: Высш.шк., 2008. 383с.

5. Волков Е. А. Численные методы. СПб.: Лань, 2010. 248 с.

6. Шуп Т. Е. Прикладные численные методы в физике и технике. М.: Высш. шк., 2007. 255 с.