Размещено на http://www.allbest.ru/

Федеральное агентство по образованию

ФГОУ СПО «Уфимский авиационный техникум»

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

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

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

Студент Г. Р. Хайбуллина

Руководитель работы

Э.Р. Ахматсафина

Содержание

Введение

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

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

1.2 Метод хорд

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

2.1 Формулировка задачи

2.2 Решение уравнения методом половинного деления

2.3 Решение уравнения методом хорд

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

3.1 Блок-схемы

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

3.3 Тестовый пример

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

Заключение

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

Введение

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

Нелинейные уравнения можно разделить на 2 класса - алгебраические и трансцендентные. Алгебраическими уравнениями называют уравнения, содержащие только алгебраические функции (целые, рациональные, иррациональные). В частности, многочлен является целой алгебраической функцией. Уравнения, содержащие другие функции (тригонометрические, показательные, логарифмические и другие) называются трансцендентными.

Целью данной курсовой работы является раскрытие содержания темы «Нахождение корня нелинейного уравнения методом половинного деления и методом хорд» и дальнейшее ее закрепление путем выполнения задания.

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

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

Методы решения нелинейных уравнений делятся на две группы:

1. точные методы;

2. итерационные методы.

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

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

Итерационный процесс состоит в последовательном уточнении начального приближения х₀. Каждый такой шаг называется итерацией. В результате итераций находится последовательность приближенных значений корня х₁, х₂,..., х_n. Если эти значения с увеличением числа итераций n приближаются к истинному значению корня, то говорят, что итерационный процесс сходится.

Можно выделить два типа итерационных методов:

1. Методы сужения интервала, содержащего корень (например, метод половинного деления). Здесь используется только знак функции y = f(x), а не ее значения. Они являются относительно простыми, но имеют низкую скорость сходимости.

2. Методы аппроксимации, в которых функция y = f(x) заменяется некоторой более простой функцией y = ц(x), для которой и отыскивается корень (например, метод хорд). Используют значения функции y = f(x). Скорость сходимости у них выше.

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

Задача нахождения корня уравнения f(x) = 0 итерационным методом состоит из двух этапов:

1. отделение корней - отыскание приближенного значения корня или содержащего его отрезка;

2. уточнение приближенных корней - доведение их до заданной степени точности.

Процесс отделения корней начинается с установления знаков функции f (x) в граничных x = a и x = b точках области ее существования. Для отделения корней используют следующую теорему. Теорема. Если непрерывная функция f(x) принимает значения разных знаков на концах отрезка [a,b], т.е. f(a)f(b)<0, то внутри этого отрезка находится по крайней мере один корень уравнения f(x)=0. Необходимо тем или иным способом проверить, является ли этот корень единственным.

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

Метод половинного деления или дихотомии (дихотомия - сопоставленность или противопоставленность двух частей целого) при нахождении корня уравнения f(x)=0 состоит в делении пополам отрезка [a; b], где находится корень. Затем анализируется изменение знака функции на половинных отрезках, и одна из границ отрезка [a; b] переносится в его середину. Переносится та граница, со стороны которой функция на половине отрезка знака не меняет. Далее процесс повторяется. Итерации прекращаются при выполнении одного из условий: либо длина интервала [a; b] становится меньше заданной погрешности нахождения корня е, либо значение функции сравнимо с погрешностью расчетов.

Пусть:

1. функция y=F(x) определена и непрерывна на отрезке [a; b]

2. F(a)*F(b)<0

Требуется найти корень на отрезке с точностью е

Разделим отрезок [a; b] пополам точкой c = (a + b)/2, как показано на рисунке 1.

Рисунок 1. Построение последовательного приближения по методу половинного деления

Если F(c) не равно 0, то возможны два случая:

1) F(x) меняет знак на отрезке [a; c];

2) F(x) меняет знак на отрезке [c; b].

Выбираем тот отрезок, на котором функция меняет знак. Если F(x) меняет знак на отрезке [a; c], то b:=c; если F(x) меняет знак на отрезке [c; b], то a:=c.

Условие окончания счета: b - a < е

Корень уравнения: x = (a + b)/2

Погрешность метода: dx = (b - a)/2

Рассмотрим положительные и отрицательные стороны метода половинного деления

«+»

1. надежность

2. не требует приведения к специальному виду

3. не требует дифференцируемости функции

4. устойчивость к ошибкам округления

«-»

1. медленная сходимость

2. метод не применим для корней четной кратности

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

1.2 Метод хорд

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

Значение функции f(x) сравнивается со значениями функций f(a) и f(b) и в дальнейшем используется вместо того из них, с которым оно совпадает по знаку. Если значение f(x) недостаточно близко к нулю, то вся процедура повторяется до тех пор, пока не будет достигнута необходимая степень сходимости е.

Пусть дано уравнение , где - непрерывная функция, имеющая в интервале (a,b) производные первого и второго порядков. Корень считается отделенным и находится на отрезке [a,b].

Идея метода хорд состоит в том, что на достаточно малом промежутке [a,b] дугу кривой можно заменить хордой и в качестве приближенного значения корня принять точку пересечения с осью абсцисс. Рассмотрим случай, показанный на рисунке 2, когда первая и вторая производные имеют одинаковые знаки, т.е. .

Размещено на http://www.allbest.ru/

Рисунок 2. График функции f(x), (первая и вторая производные имеют одинаковые знаки)

Уравнение хорды - это уравнение прямой, проходящей через две точки (a, f(a)) и (b, f(b)).

Общий вид уравнения прямой, проходящей через две точки:

Подставляя в эту формулу значения, получим уравнение хорды AB:

.

Пусть x₁ - точка пересечения хорды с осью x, так как y = 0, то

x₁ может считаться приближенным значением корня.

Аналогично для хорды, проходящей через точки и , вычисляется следующее приближение корня:

В общем случае формулу метода хорд имеет вид:

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

Размещено на http://www.allbest.ru/

Выбор формулы в каждом конкретном случае зависит от вида функции и осуществляется по правилу: неподвижной является такая граница отрезка изоляции корня, для которой знак функции совпадает со знаком второй производной. Формула (4) используется в том случае, когда . Если справедливо неравенство , то целесообразно применять формулу (5).

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

Если обозначить через m наименьшее значение |f'(x)| на промежутке [a, b], которое можно определить заранее, то получим формулу для оценки точности вычисления корня:

или

где - заданная погрешность вычислений.

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

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

2.1 Формулировка задачи

Нахождение корня уравнения методом дихотомии и методом хорд (на примере уравнения ).

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

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

Отделение корней графически

Дано уравнение , отделим корни уравнения графическим методом, для этого преобразуем его к равносильному ему уравнению .

Вычислим координаты точек графика функции F()

x	-2	-1	0	1	2	3	4
y	-8	-1	0	1	8	27	64

Вычислим координаты точек второй функции F()

x	-1	0	1	2	3	4
y	14	-20	-14	4	34	76

Рисунок 4. Отделение корней графически.

2.2 Решение уравнения методом половинного деления

Разделим отрезок [a, b] пополам точкой

с = 1/2*(a + b)

Получим с = 1/2(-2 - 1)=-3/2=-1.5

Если F(c)=0, то возможны два случая, либо F(x) меняет знак на отрезке [a, с], либо на отрезке [с, b]. Выбирая в каждом случае тот из отрезков на котором функция меняет знак и продолжая процесс половинного деления так же можно дойти до столь угодного малого отрезка, содержащего корень уравнения.

Определим, где фикция меняет знак, для этого начнем цикл и вычислим F(a)*F(c) <= 0

1-й Шаг.

Найдем F(a) =

F(b) =

F(a)*F(c) = -12*3.125 = -37.5

F(a)*F(c) <= 0

Если -37.5 <= 0, то b:=c, так как функция меняет знак

Промежуток сократиться до [-2;-1.5]

2-й Шаг. Вычисление погрешности

d = (b - a)/2 = (-1.5 + 2)/2=0.25

Сравним полученную погрешность с погрешностью заданной по условию d > е

0.25 > 0.01 - да

Полученная погрешность больше, следовательно, возвращаемся к началу цикла F(a)*F(c) <= 0. Затем выполняем цикл решения до тех пор, пока полученная погрешность не удовлетворит условию задачи.

3-й Шаг. Вычисление середины отрезка

с = (-2 + (-1.5))/2 = -1.75

F(a) = -12

F(c) = -3.734375

44.8125 <= 0 - нет

a = c = -1.75

[-1.75;-1.5]

4-й Шаг. Вычисление погрешности

d = (-1.5 + 1.75)/2 = 0.125

0.125 > 0.01 - да

5-й Шаг. Вычисление середины отрезка

c = (-1.75 + (-1.5))/2 = -1.625

F(a) = -3.734375

F(c) = -0.134766

F(a)*F(c) = -3.734375*(-0.134766) = 0.5032654

0.5032654 <= 0 - нет

a = c = -1.625

[-1.625;-1.5]

6-й Шаг. Вычисление погрешности

d = (-1.5 + 1.625)/2 = 0.0625

0.0625 > 0.01 - да

7-й Шаг. Вычисление середины отрезка

c = (-1.625 + (-1.5))/2 = -1.5625

F(a) = -0.134766

F(c) = 1.5368652

F(a)*F(c) = -0.134766*1.5368652 = -0.207117

-0.207117 <= 0 - да

b = c = -1.5625

[-1.625;-1.5625]

8-й Шаг. Вычисление погрешности

d = (-1.5625 + 1.625)/2 = 0.03125

0.03125 > 0.01 - да

9-й Шаг. Вычисление середины отрезка

c = (-1.625 + (-1.5625))/2 = -1.59375

F(a) = -0.134766

F(c) = 0.7115784

F(a)*F(c) = -0.134766*0.7115784 = -0.095897

-0.095897 <= 0 - да

b = c = -1.59375

[-1.625;-1.59375]

10-й Шаг. Вычисление погрешности

d = (-1.59375 + 1.625)/2 = 0.015625

0.015625 > 0.01 - да

11-й Шаг. Вычисление середины отрезка

c = (-1.625 + (-1.59375))/2 = -1.609375

F(a) = -0.134766

F(c) = 0.29105

F(a)*F(c) = -0.134766*0.29105 = -0.039224

-0.039224 <= 0 - да

b = c = -1.5625

[-1.625;-1.609375]

12-й Шаг. Вычисление погрешности

d = (-1.609375 + 1.625)/2 = 0.0078125

0.0078125 > 0.01 - нет

x = (b + a)/2 = (-1.625 + (-1.609375))/2 = -1.6271875

Ответ: Значение корня x = -1.6271875 с погрешностью d = 0.0078125

2.3 Решение уравнения методом хорд

Нахождение корня уравнения методом хорд на примере уравнения на промежутке [-2;-1], с погрешностью е =0.01.

1-й Шаг. Проверка условия

F(a)*F ? (a) >= 0

Для этого вычислим вторую производную

F ? (a) = 6*x - 12 = 6*(-2) - 12 = -12 - 12 = -24

F(a) = = -8 - 6*4 + 20 = -8 - 24 + 20 = -8 - 4 = -12

F(a)*F ? (a) = -12*(-24) = 288

Для нахождения минимума, вычислим первые производные промежутка [-2;-1], то есть найдем Fґ(a) и Fґ(b).

Fґ(a) = = = 12 + 24 = 36

Fґ(b) =

В данном случае минимум будет являться Fґ(b), min = 15.

Проверим ранее полученное условие F(a)*F ? (a) >= 0.

Если 288 >= 0, то

c:= a = -2

x = -1

2-й Шаг.

Вычисляем значение у по формуле итерационной последовательности

y = (c*F(x) - x*F(c))/(F(x) - F(c))

3-й Шаг. Вычисление погрешности

d = ІF(x)І/m

d = І13І/15 = 0.8666

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

d >= е

0.8666 >= 0.01 - да

x:= y = -1.52

4-й Шаг.

.625792

5-й Шаг. Вычисление погрешности

d = І2.625792І/15 = 0,1750528

0.1750528 >= 0.01 - да

x:= y = -1.606175

6-й Шаг.

y = (-2*0.377604 - (-1.606175)*(-12))/(0.377604 - (-12)) = (-0.755208 - (19.2741))/12.377604 =-1.628189

7-й Шаг. Вычисление погрешности

d = І0.377604І/15 = 0.0251736

0.0251736 >= 0.01 - да

x:= y = -1.628189

8-й Шаг.

y = (-2*0.0515006 - (-1.618189)*(-12))/(0.0505006 - (-12)) = (12.763357 - 19.418268)/12.0505006 = -0.552252

9-й Шаг. Вычисление погрешности

d = І0.0505006І/15 = 0.003667

0.0033667 >= 0.01 - нет

x = -1.628189

d = 0.0033667

Ответ: Значение корня x = -1.628189 с погрешностью d = 0.0033667

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

3.1 Блок-схемы

корень уравнение дихотомия хорда

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

Метод хорд

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

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

Программа реализована для нахождения корня уравнения , методом половинного деления, корни которого находятся на промежутке [-2;1], с погрешностью е=0.01.

unit Unit1;

interface

uses

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

Dialogs, StdCtrls;

type

TForm1 = class(TForm)

Edit1: TEdit;

Edit2: TEdit;

Label1: TLabel;

Label2: TLabel;

Label3: TLabel;

Edit3: TEdit;

Button1: TButton;

Edit4: TEdit;

procedure Button1Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);

var

x0,x1,y,e:real; k:integer;

function F(c:real):real;

begin

f:=c*c*c-6*c*c+c+20;

end;

begin

x0:=strtofloat(edit1.Text);

x1:=strtofloat(edit2.Text);

e:=strtofloat(edit3.Text);

repeat

y:=(x1+x0)/2;

if f(x0)*f(x1)<0 then x1:=y else begin x0:=y end

until (x1-x0)<e;

Edit4.text:='Ответ:'+floattostrf(y,ffFixed, 20,6);

end;

end.

Метод хорд

Программа реализована для нахождения корня уравнения , методом половинного деления, корни которого находятся на промежутке [-2;1], с погрешностью е=0.01.

unit Unit1;

interface

uses

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

Dialogs, StdCtrls;

type

TForm1 = class(TForm)

Edit1: TEdit;

Edit2: TEdit;

Label1: TLabel;

Label2: TLabel;

Label3: TLabel;

Edit3: TEdit;

Button1: TButton;

Edit4: TEdit;

procedure Button1Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);

var

x0,x1,y,e,g:real; k:integer;

function F(c:real):real;

begin

f:=c*c*c-6*c*c+c+20;

end;

begin

x0:=strtofloat(edit1.Text);

x1:=strtofloat(edit2.Text);

e:=strtofloat(edit3.Text);

repeat

g:=y;

y:=(x0*f(x1)-x1*f(x0))/(f(x1)-f(x0));

if f(x0)*f(y)<0 then x1:=y else x0:=y

until (abs(g-y))<e;

Edit4.text:='Ответ:'+floattostrf(y,ffFixed, 20,6);

end;

end.

3.3 Тестовый пример

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

В качестве тестового примера возьмем уравнение xІ - 1 = 0 на промежутке [0; 5] с точностью =0.0001

Рисунок 5. Результат работы программы (Метод половинного деления)

Метод хорд

В качестве тестового примера возьмем уравнение xІ - 1 = 0 на промежутке [0; 5] с точностью =0.0001

Рисунок 6. Результат работы программы (Метод хорд)

Значения, полученные в результате решения аналитически и программно - верны

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

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

При решении заданного уравнения на языке программирования Delphi 7 мы получаем следующие результаты, показанные на рисунке 6.

Рисунок 7. Результат работы программы (метод половинного деления)

Метод хорд

При решении заданного уравнения на языке программирования Delphi 7 мы получаем следующие результаты, показанные на рисунке 7.

Рисунок 8. Результат работы программы (Метод хорд)

Заключение

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

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

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

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

1. Каханер Д., Моулер К., Нэш С. Численные методы и программное обеспечение (пер. с англ.). М.: Мир, 2001, 575 c.

2. Самарский А. А., Гулин А. В. Численные методы: Учеб. пособие для вузов. - М.: Наука. Гл. ред. физмат. лит., 1989. - 432 с.

3. Турчак Л.И. Основы численных методов. -М.: Наука, 1987.

4. http://www.osnpas.com/file23.html

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