Нахождение корня уравнения методом дихотомии и методом касательных

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

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

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

Нахождение корня уравнения методом дихотомии и методом касательных

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

Студент Д.Ш. Галямов

Введение

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

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

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

Цель курсовой работы: освоить два метода решения нелинейных уравнений, а именно - метод дихотомии и метод касательных (Ньютона) и применить их на практике.

Состав курсовой работы:

Первая часть - Теоретическая:

в ней содержатся описания методов;

Вторая часть - Практическая:

в ней содержатся постановка задачи, и ее решение требуемыми методами;

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

дихотомия касательный уравнение delphi

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

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

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

Разделим отрезок [a, b] пополам точкой . Если (что практически наиболее вероятно), то возможны два случая: либо f(x) меняет знак на отрезке [a, x₁] (Рисунок. 1), либо на отрезке [x₁, b] (Рисунок. 2).

Рисунок 1 На отрезке [a, x₁}

Рисунок 2 На отрезке [x₁, b]

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

.2      Описание метода касательных

Пусть корень уравнения f(x) = 0 отделен на отрезке . Необходимым условием сходимости метода является то, что производные  и  непрерывны и сохраняют постоянные знаки.

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

Исходные данные:(x) - функция;

f^‘(x) - производная заданной функции f(x);

ε - требуемая точность;

x₀ - начальное приближение.

Результат: x_пр. - приближенный корень уравнения f(x) = 0.

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

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

Проведем касательную к кривой y =f(x) в точке В₀(b; f(b)). В курсе алгебры выводится уравнение касательной.

Уравнение касательной в точке В₀ имеет вид . В качестве очередного приближения к корню уравнения берем точку пересечения касательной с осью Оx. Полагая y = 0, найдем . Теперь . Применяя метод еще раз для отрезка , получим

.

Получаем рекуррентную формулу вычисления приближений к корню:

Рисунок 3. Геометрическая интерпретация метода касательных для случая .

Обратим внимание, что в этом случае в качестве начального приближения к корню выбираем точку x₀ = b. Приближение к коню происходит с правой стороны, поэтому получаем приближенное значение корня с избытком.

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

Рисунок 4. Геометрическая интерпретация метода касательных для случая.

Если снова провести касательную к кривой в точке В₀, то она пересечет ось Ох в точке не принадлежащей отрезку . Поэтому проведем касательную в точке . Ее уравнение . Находим x₁, полагая y = 0: . Корень . Применяя метод еще раз для отрезка , получим .

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

В данном случае в качестве начального приближения к корню выбираем точку x₀ = a. Приближение к коню происходит с левой стороны, поэтому находим приближенное значение корня с недостатком.

Заметим, что вычислительные формулы метода отличаются друг от друга только выбором начального приближения: в первом случае за x₀ принимаем конец b отрезка, во втором - конец a.

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

Условие окончания вычислительного процесса: , где ε - заданная точность. Тогда x_пр. = x_n+1 с точностью ε.

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

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

Применение метода дихотомии и метода касательных для решения нелинейных уравнений (на примере уравнения (x-sin(x)-0,25=0)

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

Уравнению x-sin(x)-0,25=0 соответствует эквивалентное уравнение x-0,25=sin(x) Если построить графики функций y₁= x-0,25 и y₂= sin(x) то абсциссы точек пересечения графиков этих функций дадут искомые корни данного уравнения. Из рисунка 5 видно, что корень уравнения лежит на промежутке [1;2].

Рисунок 5. Графическое отделение корней

2.2    Решение задачи методом дихотомии

1.      Вычисление значения функции x-sin(x)-0,25=0 на концах отрезка:

f(a)=1-sin(1)-0,25= -0,0914709<0(b)=2-sin(2)-0,25=0,252505>0

2.      Вычисление значения с.

С=(a+b)/2=(1+2)/2=1,5

.        Проверка условия f(a)*f(c)<0

f(a)*f(c)=(1-sin(1)-0,25)*(1,5-sin(1,5)-0,25)= -0,0914709*0,252505<0

Условие выполняется, отсюда выполняется действие:

b:=c; b=1,5

4.      d=(b-a)\2

d=(1,5-1)/2=0,25

5.      Проверка условия d>e

,25>0,001 верно

.1.     с=(1+1,5)/2=1,25

f(a)*f(c)=(1-sin(1)-0,25)*(1,5-sin(1,5)-0,25)= -0,0914709*0,05101<0

b:=c; b=1,25

d=(b-a)\2; d=(1,5-1)/2=0,125>0,001

Условие не опровергнуто

.2.     с=(1+1,25)/2=1,125

f(a)*f(c)=(1-sin(1)-0,25)*(1,25-sin(1,125)-0,25)= -0,0914709*(-0,24967)>0

a:=c; a=1,125

d=(b-a)\2; d=(1,25-1,125)/2=0,0625>0,001

Условие не опровергнуто

.3.     с=(1,125+1,25)/2=1,1875

f(a)*f(c)= (1,125-sin(1,125)-0,25)*(1,25-sin(1,25)-0,25)=-0,027268*0,010063<0

b:=c; b=1,1875

d=(b-a)\2; d=(1,1875-1,125)/2=0,03125>0,001

Условие не опровергнуто

.4.     с=(1,125+1,1875)/2=1,15625

f(a)*f(c)=(1,125-sin(1,125)-0,25)*(1,1875-sin(1,1875)-0,25)=

=-0,027268*(-0,009049)<0

a:=c; a=1,1563

d=(b-a)\2; d=(1,1875-1,1563)/2=0,015625>0,001

Условие не опровергнуто

.5.     с=(1,1563+1,1875)/2=1,171875

f(a)*f(c)=(1,1563-sin(1,1563)-0,25)*(1,1875-sin(1,1875)-0,25)=

= -0,009049*0,000394<0

b:=c; b=1,171875

d=(b-a)\2; d=(1,171875-1,1563)/2=0,007813>0,001

Условие не опровергнуто

.6.     с=(1,1563+1,1719)/2=1,164063

f(a)*f(c)=( 1,1563-sin(1,1563)-0,25)*(1,1719-sin(1,1719)-0,25)=

=-0,009049*(-0,004355)>0

a:=c; a=1,1641

d=(b-a)\2; d=(1,1719-1,1641)/2=0,003906>0,001

Условие не опровергнуто

.7.     с=(1,1641+1,1719)/2=1,167969

f(a)*f(c)=( 1,1641-sin(1,1641)-0,25)*(1,1719-sin(1,1719)-0,25)=

=-0,004355*(-0,001987)>0

a:=c; a=1,168

d=(b-a)\2; d=(1,1719-1,168)/2=0,001953>0,001

Условие не опровергнуто

.8.     с=(1,1680+1,1719)/2=1,169922

f(a)*f(c)=(1,1680-sin(1,1680)-0,25)*( 1,1719-sin(1,1719)-0,25)=

=-0,001987*(-0,000798)>0

a:=c; a=1,1699

d=(b-a)\2; d=(1,1719-1,1699)/2=0,000977<0,001

Условие опровергнуто

.        Вычисление корня уравнение:

x:=(a+b)/2

x=(1,1699+1,1719)/2=1,170898

8.      Таким образом, корнем уравнения является x=1,170898 с точностью вычисления

ε = 0,001, и погрешностью d==0,000977

2.3    Решение задачи методом касательных

1.      Вычислим значения функции x-sin(x)-0,25=0 на концах отрезка:

f(a)=1-sin(1)-0,25= -0,0914709<0(b)=2-sin(2)-0,25=0,252505>0

2.     
Проверим выполнение условия: f(a)*f(b)= -0,0914709*0,252505<0 - условие выполняется.

.        Найдем производные:

f’(x)=(x-sin(x)-0,25)’=1-cos(x)’’(x)=(1-cos(x))’=sin(x)

4.      На отрезке [1;2] производные f’(x)>0 и f’’(x)>0, т.е. сохраняют знак, следовательно, условие выполняется.

.        Выберем значение x₀ для метода касательных. Т.к. f’’(x)>0 и f(1)>0, то x₀=1.

.        Итерационная формула метода Ньютона будет такой:

.        Применяя эту формулу, последовательно находим:

Таким образом, корень уравнения x=1,118 с точностью ε = 0,001. Как мы видим, значение корня с нужной нам точностью было получено на втором шаге. (Третий шаг понадобился для того, чтобы можно было убедиться, что с нужной нам точностью значение перестало изменяться).

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

3.1    Блок-схемы алгоритмов

Блок-схема алгоритма к методу дихотомии

Блок-схема алгоритма к методу касательных

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

Текст программы метода дихотомии на языке Delphi

{ Private declarations }

{ Public declarations };: TForm1;

{$R *.dfm}TForm1.Button1Click(Sender: TObject);f(x:real):real; {Уравнение}:=x-sin(x)-0.25;;b,a,c,d,e,x:real;:=strtofloat(edit1.text); :=strtofloat(edit2.text) ;:=strtofloat(edit3.text) ;:=(a+b)/2 ;:=(b-a)/2 ;d>e do:=(a+b)/2;f(c)>0 then b:=c{выбор точки сближения}a:=c;:=(b-a)/2;;:=(b+a)/2;.text:='x = '+floattostrf(x,fffixed, 10,8);

end;.

Текст программы метода касательных на языке Delphi

unit Unit1;, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, StdCtrls;= class(TForm): TButton;: TLabel;: TLabel;: TLabel;: TEdit;: TLabel;: TLabel;: TEdit;: TLabel;: TEdit;: TEdit;: TLabel;Button1Click(Sender: TObject);

{ Private declarations }

{ Public declarations };: TForm1;

{$R *.dfm}TForm1.Button1Click(Sender: TObject);f(x:real):real;{Èñõîäíàÿ ôóíêöèÿ}:=x-sin(x)-0.25;;f1(x:real):real;{Ïåðâàÿ ïðîèçâîäíàÿ ôóíêöèè}:=1-cos(x);;f2(x:real):real;{Âòîðàÿ ïðîèçâîäíàÿ ôóíêöèè}:=Sin(x);;a,b,x,y,e:real;:=strtofloat(edit1.Text);:= strtofloat(edit2.Text);:=strtofloat(edit3.Text); f(a)*f2(a)>=0 then x:=a else x:=b; {Выбор начальной точки приближения}

repeat:=f(x)/f1(x);:=x-y;abs(y)<=e;.text:='x = '+floattostrf(x,fffixed, 10,8);;..

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

В качестве тестового примера рассмотрим линейное уравнение x³+ 1=0, корень которого равен -1.

На рисунке 6 представлено решение примера методом дихотомии.

Рисунок 6. Решение уравнения методом дихотомии

На рисунке 7 - решение тестового примера касательным методом

Рисунок 7. Решение уравнения методом касательных.

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

На рисунке 8 представлен результат работы программы для метода дихотомии

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

На рисунке 9 - результат работы программы для комбинированного метода

Рисунок 9. Результат работы программы для метода касательных на языке Delphi

Заключение

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

При оценке эффективности численных методов существенное значение имеют различные свойства:

1)      универсальность;

2)      простота организации вычислительного процесса и контроля над точностью;

)        скорость сходимости.

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

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

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

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

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

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

1.      Ананий В. Левитин Глава 11. Преодоление ограничений: Метод деления пополам // [= 0-201-74395-7 Алгоритмы: введение в разработку и анализ] = Introduction to The Design and Analysis of Aigorithms. - М.: «Вильямс», 2006. - С. 476-480.

.        Бахвалов Н.С., Жидков Н.П., Кобельков Г.Г. Численные методы. - 8-е изд.. - М.: Лаборатория Базовых Знаний, 2000.

.        Кацман Ю.Я. Прикладная математика. Численные методы. Учебное пособие. - Томск: Изд. ТПУ, 2000. - 68 с.