Дихотомия решение уравнений. Метод половинного деления (дихотомия). Метод половинного деления

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

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

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

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

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

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

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

Введение

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

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

2 Метод хорд

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

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

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

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

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

1 Блок-схемы

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

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

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

Заключение

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

Методы аппроксимации, в которых функция 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) принимает значения разных знаков на концах отрезка , т.е. f(a)f(b)<0 , то внутри этого отрезка находится по крайней мере один корень уравнения f(x)=0. Необходимо тем или иным способом проверить, является ли этот корень единственным.

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

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

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

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

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

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

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

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

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

) 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

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

Надежность

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

или

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

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

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

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

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

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

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

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

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

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

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

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

с = 1/2*(a + b )

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

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

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

1-й Шаг.

Найдем F(a) =

F(b) =(a)*F(c) = -12*3.125 = -37.5(a)*F(c) <= 0

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

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

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

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

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

25 > 0.01 - да

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

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

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

F(a) = -12(c) = -3.734375

8125 <= 0 - нет= c = -1.75

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

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

125 > 0.01 - да

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

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

F(a) = -3.734375

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

5032654 <= 0 - нет= c = -1.625

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

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

0625 > 0.01 - да

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

c = (-1.625 + (-1.5))/2 = -1.5625(a) = -0.134766(c) = 1.5368652(a)*F(c) = -0.134766*1.5368652 = -0.207117

207117 <= 0 - да = c = -1.5625

[-1.625;-1.5625]

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

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

03125 > 0.01 - да

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

c = (-1.625 + (-1.5625))/2 = -1.59375(a) = -0.134766(c) = 0.7115784(a)*F(c) = -0.134766*0.7115784 = -0.095897

095897 <= 0 - да = c = -1.59375

[-1.625;-1.59375]

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

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

015625 > 0.01 - да

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

c = (-1.625 + (-1.59375))/2 = -1.609375(a) = -0.134766(c) = 0.29105(a)*F(c) = -0.134766*0.29105 = -0.039224

039224 <= 0 - да = c = -1.5625

[-1.625;-1.609375]

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

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

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), min = 15.

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

Если 288 >= 0, то

2-й Шаг.

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

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

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

d = ²13²/15 = 0.8666

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

Метод хорд

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

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

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

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

{ Private declarations }

{$R *.dfm}TForm1.Button1Click(Sender: TObject);,x1,y,e:real; k:integer;F(c:real):real;:=c*c*c-6*c*c+c+20;;:=strtofloat(edit1.Text);:=strtofloat(edit2.Text);:=strtofloat(edit3.Text);:=(x1+x0)/2;f(x0)*f(x1)<0 then x1:=y else begin x0:=y end(x1-x0)

Метод хорд

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

{ Private declarations }

{ Public declarations };: TForm1;

{$R *.dfm}TForm1.Button1Click(Sender: TObject);,x1,y,e,g:real; k:integer;F(c:real):real;:=c*c*c-6*c*c+c+20;;:=strtofloat(edit1.Text);:=strtofloat(edit2.Text);:=strtofloat(edit3.Text);:=y;:=(x0*f(x1)-x1*f(x0))/(f(x1)-f(x0));f(x0)*f(y)<0 then x1:=y else x0:=y(abs(g-y))

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

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

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

Метод хорд

В качестве тестового примера возьмем уравнение x² - 1 = 0 на промежутке с точностью =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

Пример

Объём понятия «человек » можно разделить на два взаимоисключающих класса: мужчины и не мужчины . Понятия «мужчины » и «не мужчины » являются противоречащими друг другу, поэтому их объёмы не пересекаются. От дихотомии следует отличать обычное деление, приводящее к тому же самому результату. Например, объём понятия «человек » можно разделить по признаку пола на мужчин и женщин . Но между понятиями мужчина и женщина нет логического противоречия, поэтому здесь нельзя говорить о дихотомическом делении.

Преимущества и недостатки

Дихотомическое деление привлекательно своей простотой. Действительно, при дихотомии мы всегда имеем дело лишь с двумя классами, которые исчерпывают объем делимого понятия. Таким образом, дихотомическое деление всегда соразмерно; члены деления исключают друг друга, так как каждый объект делимого множества попадает только в один из классов а или не а ; деление проводится по одному основанию - наличие или отсутствие некоторого признака. Обозначив делимое понятие буквой а и выделив в его объёме некоторый вид, скажем, b , можно разделить объем а на две части - b и не b .

Дихотомическое деление имеет недостаток: при делении объёма понятия на два противоречащих понятия каждый раз остаётся крайне неопределённой та его часть, к которой относится частица «не». Если разделить учёных на историков и не историков , то вторая группа оказывается весьма неясной. Кроме того, если в начале дихотомического деления обычно довольно легко установить наличие противоречащего понятия, то по мере удаления от первой пары понятий найти его становится все труднее.

Применение

Дихотомия обычно используется как вспомогательный приём при установлении классификации.

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

Метод дихотомии

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

Пускай задана функция .

Разобьём мысленно заданный отрезок пополам и возьмём две симметричные относительно центра точки и так, что:

где - некоторое число в интервале

Отбросим тот из концов изначального интервала, к которому ближе оказалась одна из двух вновь поставленных точек с максимальным значением (напомним, мы ищем минимум), то есть:

Src="/pictures/wiki/files/54/6dfd1fa5bf638302d7bbb4016d0ed760.png" border="0">

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

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

Литература

Ананий В. Левитин Глава 11. Преодоление ограничений: Метод деления пополам // [= 0-201-74395-7 Алгоритмы: введение в разработку и анализ] = Introduction to The Design and Analysis of Aigorithms. - М.: «Вильямс» , 2006. - С. 476-480.
Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. пец. вузов. - М.: Высш. шк., 1986.
Амосов А.А., Дубинский Ю. А., Копченова Н.П. Вычислительные методы для инженеров. - М.: Мир, 1998.
Бахвалов Н.С., Жидков Н.П., Кобельков Г.Г. Численные методы. - 8-е изд.. - М.: Лаборатория Базовых Знаний, 2000.
Волков Е.А. Численные методы. - М.: Физматлит, 2003.
Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. - М.: Мир, 1985.
Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. - М.: Наука, 1970. - С. 575-576.
Коршунов Ю.М., Коршунов Ю.М. Математические основы кибернетики. - Энергоатомиздат, 1972.
Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. - М.: МИФИ, 1982.
Максимов Ю.А. Алгоритмы линейного и дискретного программирования. - М.: МИФИ, 1980.

Wikimedia Foundation . 2010 .

Смотреть что такое "Метод дихотомии" в других словарях:

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

Последовательные симплексы в методе Нелдера Мида для функции Розенброка (англ.) (вв … Википедия

Итерационный численный метод для вычисления корня заданной функции f(x) = 0. Был представлен Давидом Мюллером в 1956 году. Метод Мюллера основан на методе секущих, который строит на каждом шаге итерации прямые, проходящие через две точки на… … Википедия

Может означать: Двоичный поиск метод поиска в структурах данных. Метод бисекции метод поиска корней непрерывной функции на отрезке. Метод дихотомии Разделяй и властвуй парадигма разработки алгоритмов … Википедия

Последовательные симплексы в методе Нелдера Мида для функции Розенброка (англ.) (вверху) и функции Химмельблау (англ.) (внизу) Не путать с «симплекс методом» из линейного программирования методом оптимизации линейной системы с ограничениями.… … Википедия

Эта статья или раздел нуждается в переработке. Пожалуйста, улучшите статью в соответствии с правилами написания статей. Не следует путать с … Википедия

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

Метод дихотомии, 1) Один из методов численного решения уравнений с одним неизвестным. Пусть имеется уравнение f(x) = 0 с непрерывной на отрезке [а, b]функцией f(х), принимающей на концах отрезка значения разных знаков и имеющей внутри [а,… … Математическая энциклопедия

Стилостатистический метод анализа текста - – это применение инструментария математической статистики в области стилистики для определения типов функционирования языка в речи, закономерностей функционирования языка в разных сферах общения, типах текстов, специфики функц. стилей и… … Стилистический энциклопедический словарь русского языка

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

Пока не будет достигнута нужная точность.

Варианты метода дихотомии различаются выбором точки деления. Рассмотрим варианты дихотомии: метод половинного деления и метод хорд .

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

Метод половинного деления известен также как метод бисекции . В данном методе интервал делится ровно пополам.

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

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

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

Метод половинного деления как метод поиска корней функции

Изложение метода

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

Будем считать, что корень функции отделён на отрезке . Задача заключается в том, чтобы найти и уточнить этот корень методом половинного деления. Другими словами, требуется найти приближённое значение корня с заданной точностью .

Пусть функция непрерывна на отрезке ,

и - единственный корень уравнения .

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

Поделим отрезок пополам. Получим точку и два отрезка .

Новый отрезок делим пополам. Получаем середину этого отрезка и так далее.

Для того, чтобы найти приближённое значение корня с точностью до 0" alt=" \eps >0">, необходимо остановить процесс половинного деления на таком шаге , на котором и вычислить . Тогда можно взять .

Реализация метода на С++ и числовой пример

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

Ниже приведен пример программы на Си++ , которая решает поставленную задачу.

Программа 1. Корень уравнения

#include #include using namespace std; const double epsilon = 1e-2 ; double f(double x) { return 4 - exp (x) - 2 * x^ 2 ; } int main() { double a, b, c; a = 0 ; b = 2 ; while (b - a > epsilon) { c = (a + b) / 2 ; if (f(b) * f(c) < 0 ) a = c; else b = c; } cout << (a + b) / 2 << endl; return 0 ; }

Искомый корень . Вычисления проводились с точностью .

Промежуточные вычисления представлены в таблице ниже.

n	a n	b n	c n	b n -c n
1	0	1	0.5	0.5
2	0.5	1	0.75	0.25
3	0.75	1	0.875	0.125
4	0.875	1	0.9375	0.0625
5	0.875	0.9375	0.90625	0.03125
6	0.875	0.90625	0.890625	0.015625
7	0.875	0.890625	0.8828125	0.0078125

Метод половинного деления как метод оптимизации

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

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

Дана функция . Необходимо найти , доставляющий минимум (или максимум) функции на интервале с заданной точностью , т.е. найти

Запишем словесный алгоритм метода.

Схема алгоритма метода представлена на рис 2.

- константа,

При выводе – координата точки, в которой функция имеет минимум (или максимум), – значение функции в этой точке.

Метод хорд

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

Изложение метода

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

При этом в процессе поиска семейство хорд может строиться:

В результате итерационный процесс схождения к корню реализуется рекуррентной формулой:

для случая а):

для случая б):

Процесс поиска продолжается до тех пор, пока не выполнится условие или .

Метод обеспечивает быструю сходимость, если %200" alt="f(z)\cdot f""(z) > 0">, т.е. хорды фиксируются в том конце интервала , где знаки функции и ее кривизны совпадают.

Схема алгоритма уточнения корня методом хорд представлена на рис. 4.

Комбинация метода хорд и метода половинного деления

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

Метод половинного деления (дихотомия)

Дихотомия применяется, когда требуется надежность счета, а скорость сходимости не имеет значения.

х n х cр2 х * х cр1 х n+1 Х

Рисунок 5.2 – Геометрическая интерпретация метода дихотомии

Пусть дано уравнение f(x)=0 и отделен простой корень х * , то есть найден такой отрезок [х n , х n +1 ], х * принадлежит [х n , х n +1 ] и на концах интервала функция имеет значения, противоположные по знаку. Отрезок

[х n , х n +1 ] называется начальным интервалом неопределенности,потому что известно, что корень ему принадлежит, но его местоположение с требуемой точностью не определено.

Алгоритм метода дихотомии.

1. Вычисляют значения функции через равные интервалы значений х до смены знака, при переходе от f(x n) к f(x n +1)

2. Вычисляют среднее значение аргумента x ср и находят f(x ср).

3. Если знак f(x ср) совпадает со знаком f(x n), то в дальнейших расчетах вместо x n используют x cp . Если f(x cp) совпадает с f(x n+1), то вместо x n+1 берут x cp .

4. Интервал, в котором заключено значение корня, сужается. Если f(x cp k) ≤ 0 + ε, где ε положительное наперед заданное достаточное малое число – точность расчета, то процесс заканчивается за k итераций, при этом ширина интервала уменьшается в 2 k раз. Если f(x cp k) >

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

Метод не применим к корням четной кратности, т.е. тогда когда, f(x)=g(x)(x-x 1) m , где x 1 корень кратности m.

Метод хорд

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

x 1 * x 2 * x 3 * x 4 * x *

Рисунок 5.3 – Геометрическая интерпретация метода хорд

Алгоритм метода хорд.

1. Вычисляют значения функции через равные интервалы значений х до смены знака при переходе от f (x n) к f (x n +1).

х * = x n – f (x n)(x n +1 - x n)/ (f (x n +1) – f (x n)) (5.1)

3. Находят значение f (x k *), которое сравнивают с известными f (x n),

f (x n +1). Если знак f(x к *) совпадает со знаком f(x n), то в дальнейших расчетах вместо x n используют x k * . Если f(x k *) совпадает с f(x n+1), то вместо x n+1 берут x k * .

4. Проверяют близость f(x k *) к нулю c заданной точностью ε. Если f(x k *) ≤ 0 + ε, то процесс заканчивается за k итераций. Если f(x k *) > 0 + ε, повторяют пп.2-3 алгоритма.

В знаменателе формулы (5.1) стоит разность значений функций. Вдали от корня она несущественна, но вблизи корня эти значения близки и малы. Возникает потеря значащих цифр, приводящая к «разболтке» счета. Это ограничивает точность, с которой можно найти корень. Для простых корней это ограничение невелико, а для кратных – существенно. Можно использовать метод Гарвика. Выбирают не очень малое ε, ведут итерации до выполнения условия |x n +1 - x n | < ε и затем продолжают расчет до тех пор, пока |x n +1 - x n | убавает.

Метод Ньютона

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

Функция f(x), дважды дифференцируемая на отрезке , который содержит корень х * . При этом f(x *)=0. Для определения интервала, в котором заключен корень, в методе Ньютона не требуется находить значения функции с противоположными знаками. Вместо интерполяции по двум значениям функции будем проводить экстраполяцию с помощью касательной в данной точке.

М 0

Рисунок 5.4 – Геометрическая интерпретация метода Ньютона

Алгоритм метода:

1. Находят значение x n+1 , которое соответствует точке, в которой касательная к кривой в точке x n пересекает ось х

x n+1 = x n - f(x n)/f ′(x n) (5.2)

2. Процедуру повторяют до выполнения условия близости функции к нулю с заданной точностью f(x n) ≈ ε

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

Метод секущих

Одним из недостатков метода Ньютона является необходимость дифференцирования заданной функции f(x). Если нахождение производной затруднено, можно воспользоваться некоторым приближением, которое положено в основу метода секущих. Заменим производную f ′(x n) для расчета

x n+1 = x n - f(x n)/f ′(x n) разностью последовательных значений функции, отнесенных к разности последовательных значений аргумента, т.е. разделенной разностью первого порядка

F*(x n)= (f(x n)- f(x n-1))/(x n - x n-1),

x n+1 = x n - f(x n)/ F*(x n). (5.3)

Схема алгоритма остается, как и в методе Ньютона, изменяется только вид итерационной формулы (5.3).

5.6 Метод простой итерации (последовательных приближений)

Для применения этого метода уравнение f(x)=0 приводится к виду

х = g(х). Задаются начальным значением х 0 , а последующие приближения вычисляются с помощью итерационной процедуры

x n+1 = g(х n). (5.4)

Для сходимости метода необходимо выполнение условия

0< g′ (х n)<1

Метод дихотомии имеет свое название от древнегреческого слова, что в переводе означает деление надвое. Именно поэтому данные метод имеет еще второе название: метод половинного деления. Его мы используем довольно часто. Допустим, играя в игру "Угадай число", где один игрок загадывает число от 1 до 100, а другой пытается его отгадать, руководствуясь подсказками "больше" или "меньше". Логично предположить, что первым числом будет названо 50, а вторым в случае если оно меньше - 25, если больше - 75. Таким образом, на каждом этапе (иттерации) неопределенность неизвестного уменьшается в 2 раза. Т.е. даже самый невезучий в мире человек отгадает загаданное число в данном диапазоне за 7 предположений вместо 100 случайных утверждений.

Метод половинного деления в решении уравнения

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

Алгоритм метода дихотомии

Алгоритм метода дихотомии очень прост. Рассмотрим отрезок |a,b| в пределах которого имеется один корень x 1

На первой этапе вычисляется x 0 =(a+b)/2

Далее определеяется значение функции в этой точке: если f(x 0)< 0, то , если наоборот, то ,т.е происходит сужение интервала. Таким образом в результате формируется последовательность x i , где i - номер иттерации.

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

В качестве примера использования метода половинного деления найдем корень на интервале уравнения x 3 -3*x+1=0 с точностью в 10 -3

Как видно из таблицы корнем является 0,347. Колличество иттераций равно 10. Условие завершения: a-b=0,0009< 10 -3

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

Скачать:

Решение уравнения методом дихотомии - Решение уравнения методом половинного деления в Паскале.