Нахождение корня уравнения методом дихотомии и методом касательных
Описание методов дихотомии (половинного деления) и касательных. Их применение для решения нелинейных уравнений. Графическое отделение корней. Блок-схемы алгоритмов. Тексты (листинги) программ на языке Delphi. Тестовый пример решения задачи с помощью ЭВМ.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 15.06.2013 |
| Размер файла | 944,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Федеральное агентство по образованию
ФГОУ СПО «Уфимский авиационный техникум»
Курсовая работа
Нахождение корня уравнения методом дихотомии и методом касательных
По дисциплине «Численные методы»
Студент Д.Ш. Галямов
Введение
Внедрение ЭВМ во все сферы человеческой деятельности требует от специалистов разного профиля овладения навыками использования вычислительной техники. Повышается уровень подготовки студентов, которые уже с первых курсов приобщаются к использованию ЭВМ и простейших численных методов, не говоря уже о том, при что выполнении курсовых и дипломных проектов применение вычислительной техники становится нормой в подавляющем большинстве вузов.
Вычислительная техника используется сейчас не только в инженерных расчетах и экономических науках, но и таких традиционно нематематических специальностях, как медицина, лингвистика, психология. В связи с этим можно констатировать, что применение ЭВМ приобрело массовый характер. Возникла многочисленная категория специалистов - пользователей ЭВМ, которым необходимы знания по применению ЭВМ в своей отрасли - навыки работы с уже имеющимся программным обеспечением, а так же создания своего собственного ПО, приспособленного для решения конкретной задачи. И здесь на помощь пользователю приходят описания языков программирования высокого уровня и численные методы.
Численные методы разрабатывают и исследуют, как правило, высококвалифицированные специалисты-математики. Для большинства пользователей главной задачей является понимание основных идей и методов, особенностей и областей применения.
Цель курсовой работы: освоить два метода решения нелинейных уравнений, а именно - метод дихотомии и метод касательных (Ньютона) и применить их на практике.
Состав курсовой работы:
Первая часть - Теоретическая:
в ней содержатся описания методов;
Вторая часть - Практическая:
в ней содержатся постановка задачи, и ее решение требуемыми методами;
Третья часть - Программная, включающая в себя: блок-схемы алгоритмов, тексты (листинги) программ на языке Delphi, тестовый пример и результат его решения, а также результат решения поставленной задачи;
дихотомия касательный уравнение delphi
1. Теоретическая часть
1.1 Описание метода дихотомии
Метод дихотомии также называют методом половинного деления. Этот метод решения уравнений отличается тем, что для него не требуется выполнения условия, что первая и вторая производная сохраняют знак на интервале [a, b]. Метод половинного деления сходится для любых непрерывных функций f(x) в том числе недифференцируемых.
Разделим отрезок [a, b] пополам точкой . Если (что практически наиболее вероятно), то возможны два случая: либо f(x) меняет знак на отрезке [a, x1] (Рисунок. 1), либо на отрезке [x1, b] (Рисунок. 2).
Рисунок 1 На отрезке [a, x1}
Рисунок 2 На отрезке [x1, b]
Выбирая в каждом случае тот отрезок, на котором функция меняет знак, и продолжая процесс половинного деления дальше, можно дойти до сколь угодно малого отрезка, содержащего корень уравнения.
1.2 Описание метода касательных
Пусть корень уравнения f(x) = 0 отделен на отрезке . Необходимым условием сходимости метода является то, что производные и непрерывны и сохраняют постоянные знаки.
Алгоритм приближенного вычисления корня методом касательных.
Исходные данные:
f(x) - функция;
f`(x) - производная заданной функции f(x);
? - требуемая точность;
x0 - начальное приближение.
Результат: xпр. - приближенный корень уравнения f(x) = 0.
Метод решения:
Рассмотрим случай, когда , т.е. и имеют одинаковые знаки. Тогда возможны два случая построения кривой на отрезке (рис 3).
Проведем касательную к кривой y =f(x) в точке В0(b; f(b)). В курсе алгебры выводится уравнение касательной.
Уравнение касательной в точке В0 имеет вид . В качестве очередного приближения к корню уравнения берем точку пересечения касательной с осью Оx. Полагая y = 0, найдем . Теперь . Применяя метод еще раз для отрезка , получим
.
Получаем рекуррентную формулу вычисления приближений к корню:
Рисунок 3. Геометрическая интерпретация метода касательных для случая .
Обратим внимание, что в этом случае в качестве начального приближения к корню выбираем точку x0 = b. Приближение к коню происходит с правой стороны, поэтому получаем приближенное значение корня с избытком.
Пусть теперь , т.е. и имеют разные знаки. Тогда также возможны два случая построения кривой на отрезке (рис 4).
Рисунок 4. Геометрическая интерпретация метода касательных для случая.
Если снова провести касательную к кривой в точке В0, то она пересечет ось Ох в точке не принадлежащей отрезку . Поэтому проведем касательную в точке . Ее уравнение . Находим x1, полагая y = 0: . Корень . Применяя метод еще раз для отрезка , получим .
Получаем рекуррентную формулу вычисления приближений к корню, аналогичную первому случаю:
В данном случае в качестве начального приближения к корню выбираем точку x0 = a. Приближение к коню происходит с левой стороны, поэтому находим приближенное значение корня с недостатком.
Заметим, что вычислительные формулы метода отличаются друг от друга только выбором начального приближения: в первом случае за x0 принимаем конец b отрезка, во втором - конец a.
Убедитесь сами, что при выборе начального приближения корня можно руководствоваться правилом: за исходную точку следует выбрать тот конец отрезка , в котором знак функции совпадает со знаком второй производной (см. рисунки 8,9).
Условие окончания вычислительного процесса: , где ? - заданная точность. Тогда xпр. = xn+1 с точностью ?.
2. Постановка и решение задачи
2.1 Формулировка задачи
Применение метода дихотомии и метода касательных для решения нелинейных уравнений (на примере уравнения (x-sin(x)-0,25=0)
Графическое отделение корней
Уравнению x-sin(x)-0,25=0 соответствует эквивалентное уравнение x-0,25=sin(x) Если построить графики функций y1= x-0,25 и y2= 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
f(b)=2-sin(2)-0,25=0,252505>0
2. Вычисление значения с.
С=(a+b)/2=(1+2)/2=1,5
3. Проверка условия 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
0,25>0,001 верно
6. Выполнение пунктов 2-5, пока не будет опровергнуто условие под пунктом 5
6.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
Условие не опровергнуто
6.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
Условие не опровергнуто
6.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
Условие не опровергнуто
6.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
Условие не опровергнуто
6.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.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
Условие не опровергнуто
6.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
Условие не опровергнуто
6.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
Условие опровергнуто
7. Вычисление корня уравнение:
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
f(b)=2-sin(2)-0,25=0,252505>0
2. Проверим выполнение условия: f(a)*f(b)= -0,0914709*0,252505<0 - условие выполняется.
3. Найдем производные:
f'(x)=(x-sin(x)-0,25)'=1-cos(x)
f''(x)=(1-cos(x))'=sin(x)
4. На отрезке [1;2] производные f'(x)>0 и f''(x)>0, т.е. сохраняют знак, следовательно, условие выполняется.
5. Выберем значение x0 для метода касательных. Т.к. f''(x)>0 и f(1)>0, то x0=1.
6. Итерационная формула метода Ньютона будет такой:
7. Применяя эту формулу, последовательно находим:
Таким образом, корень уравнения x=1,118 с точностью ? = 0,001. Как мы видим, значение корня с нужной нам точностью было получено на втором шаге. (Третий шаг понадобился для того, чтобы можно было убедиться, что с нужной нам точностью значение перестало изменяться).
3. Программная реализация
3.1 Блок-схемы алгоритмов
Блок-схема алгоритма к методу дихотомии
Блок-схема алгоритма к методу касательных
3.2 Тексты программ
Текст программы метода дихотомии на языке Delphi
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;
type
TForm1 = class(TForm)
Label1: TLabel;
Label2: TLabel;
Label3: TLabel;
Label4: TLabel;
Label5: TLabel;
Edit1: TEdit;
Edit2: TEdit;
Button1: TButton;
Edit3: TEdit;
Edit4: TEdit;
procedure Button1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
implementation
{$R *.dfm}
procedure TForm1.Button1Click(Sender: TObject);
function f(x:real):real; {Уравнение}
begin
f:=x-sin(x)-0.25;
end;
Var b,a,c,d,e,x:real;
begin
a:=strtofloat(edit1.text);
b:=strtofloat(edit2.text) ;
e:=strtofloat(edit3.text) ;
c:=(a+b)/2 ;
d:=(b-a)/2 ;
while d>e do
begin
c:=(a+b)/2;
if f(c)>0 then b:=c{выбор точки сближения}
else a:=c;
d:=(b-a)/2;
end;
x:=(b+a)/2;
edit4.text:='x = '+floattostrf(x,fffixed, 10,8);
end;
end.
Текст программы метода касательных на языке Delphi
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;
type
TForm1 = class(TForm)
Button1: TButton;
Label1: TLabel;
Label2: TLabel;
Label3: TLabel;
Edit1: TEdit;
Label4: TLabel;
Label5: TLabel;
Edit2: TEdit;
Label6: TLabel;
Edit3: TEdit;
Edit4: TEdit;
Label7: TLabel;
procedure Button1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
var
Form1: TForm1;
implementation
{$R *.dfm}
procedure TForm1.Button1Click(Sender: TObject);
function f(x:real):real;{Enoiaiay ooieoey}
begin
f:=x-sin(x)-0.25;
end;
function f1(x:real):real;{Ia?aay i?iecaiaiay ooieoee}
begin
f1:=1-cos(x);
end;
function f2(x:real):real;{Aoi?ay i?iecaiaiay ooieoee}
begin
f2:=Sin(x);
end;
var a,b,x,y,e:real;
begin
a:=strtofloat(edit1.Text);
b:= strtofloat(edit2.Text);
eps:=strtofloat(edit3.Text);
if f(a)*f2(a)>=0 then x:=a else x:=b; {Выбор начальной точки приближения}
repeat
y:=f(x)/f1(x);
x:=x-y;
until abs(y)<=e;
edit4.text:='x = '+floattostrf(x,fffixed, 10,8);
end;
end.
end.
3.3 Тестовый пример
В качестве тестового примера рассмотрим линейное уравнение x3+ 1=0, корень которого равен -1.
На рисунке 6 представлено решение примера методом дихотомии.
Рисунок 6. Решение уравнения методом дихотомии
На рисунке 7 - решение тестового примера касательным методом
Рисунок 7. Решение уравнения методом касательных.
3.4 Решение задачи с помощью ЭВМ
На рисунке 8 представлен результат работы программы для метода дихотомии
Рисунок 8. Результат работы программы для метода дихотомии на языке Delphi
На рисунке 9 - результат работы программы для комбинированного метода
Рисунок 9. Результат работы программы для метода касательных на языке Delphi
Заключение
Ситуация, когда одну и ту же задачу можно решить многими способами, является довольно типичной. В таких случаях естественно возникает необходимость сравнения их между собой.
При оценке эффективности численных методов существенное значение имеют различные свойства:
1) универсальность;
2) простота организации вычислительного процесса и контроля над точностью;
3) скорость сходимости.
Метод дихотомии наиболее универсален, сходится для любых непрерывных функций f(x) в том числе недифференцируемых. Зачастую, когда функция недифферецируема, используют именно этот метод. Но его сходимость по отношению к другим численным методам обладает достаточно низкой сходимостью.
В данной курсовой наглядно представлена сходимость метода дихотомии, которая обладает низкой сходимостью по сравнению с методом касательных. Количество шагов приближения метода дихотомии в данном примере девять против метода касательных, количество которых равно двум на одинаковом отрезке приближения. А это метод касательных сходим более чем в 4 раза.
Метод касательных обладает наибольшей скоростью сходимости. В случае, когда подсчёт значений функции f(x) сложен и требует больших затрат машинного времени, это преимущество становится определяющим.
Метод касательных также отличается от других тем, что для определения интервала, в котором заключен корень, не требуется находить значения функции с противоположными знаками. Вместо интерполяции (приближения) по двум значениям функции в методе Ньютона осуществляется экстраполяция (предсказание) с помощью касательной к кривой в данной точке.
Итак, в данной курсовой работе были изучены два метода решения нелинейных уравнений: метод дихотомии и метод касательных, рассмотрено решение уравнения этими методами, также был разработан алгоритм решения поставленной задачи. По этому алгоритму на языке Delphi составлена и отлажена программа.
Список литературы
1. Ананий В. Левитин Глава 11. Преодоление ограничений: Метод деления пополам // [= 0-201-74395-7 Алгоритмы: введение в разработку и анализ] = Introduction to The Design and Analysis of Aigorithms. -- М.: «Вильямс», 2006. -- С. 476-480.
2. Бахвалов Н.С., Жидков Н.П., Кобельков Г.Г. Численные методы. -- 8-е изд.. -- М.: Лаборатория Базовых Знаний, 2000.
3. Кацман Ю.Я. Прикладная математика. Численные методы. Учебное пособие. - Томск: Изд. ТПУ, 2000. - 68 с.
Размещено на Allbest.ru
Подобные документы
Применение методов касательных (Ньютона) и комбинированного (хорд и касательных) для определения корня уравнения. Разработка алгоритма решения и его описание его в виде блок-схем. Тексты программ на языке Delphi. тестовый пример и результат его решения.
курсовая работа [923,7 K], добавлен 15.06.2013Особенности точных и итерационных методов решения нелинейных уравнений. Последовательность процесса нахождения корня уравнения. Разработка программы для проверки решения нелинейных функций с помощью метода дихотомии (половинного деления) и метода хорд.
курсовая работа [539,2 K], добавлен 15.06.2013Изучение численных методов решения нелинейных уравнений, используемых в прикладных задачах. Нахождение корня уравнения методом простой итерации и методом касательных (на примере уравнения). Отделение корней графически. Программная реализация, алгоритм.
курсовая работа [1,7 M], добавлен 15.06.2013Исследование количества, характера и расположения корней. Определение их приближенных значений итерационными методами: половинного деления (дихотомии) и хорд. Тексты программ. Решение уравнений на языках программирования Borland Delfi и Turbo Pascal.
курсовая работа [500,3 K], добавлен 15.06.2013Этапы численного решения нелинейных уравнений заданного вида: отделение (изоляция, локализация) корней уравнения аналитическим или графическим способами, уточнение конкретного выделенного корня методом касательных (Ньютона). Решение в системе MathCad.
курсовая работа [271,6 K], добавлен 22.08.2012Разработка программы для нахождения корней нелинейных уравнений несколькими методами: методом хорд, касательных, половинного деления, итераций. Реализации программы с помощью системы программирования Delphi 7. Методика работы пользователя с программой.
курсовая работа [1,3 M], добавлен 11.02.2013Математический алгоритм вычисления корней нелинейного уравнения и его решение методом касательных. Особенности программной реализации решения таких уравнений. Процедура подготовки и решения задачи на ЭВМ, характеристика алгоритма и структуры программы.
курсовая работа [96,6 K], добавлен 02.06.2012Обзор существующих методов по решению нелинейных уравнений. Решение нелинейных уравнений комбинированным методом и методом хорд на конкретных примерах. Разработка программы для решения нелинейных уравнений, блок-схемы алгоритма и листинг программы.
курсовая работа [435,8 K], добавлен 15.06.2013Численные методы решения нелинейных уравнений, используемых в прикладных задачах. Составление логической схемы алгоритма, таблицы индентификаторов и программы нахождения корня уравнения методом дихотомии и методом Ньютона. Ввод программы в компьютер.
курсовая работа [220,0 K], добавлен 19.12.2009Математическое описание, алгоритм и программа вычисления нелинейного уравнения методом дихотомии. Метод половинного деления. Метод поиска корней функции. Написание текста программы с комментариями. Проведение тестовых расчетов. Вывод ответа на экран.
курсовая работа [67,2 K], добавлен 15.02.2016
