Метод деления отрезка пополам (дихотомии)

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

Рассмотрим функцию f(x). Возьмем отрезок на этой функции [а,в].

 

В этом методе точки Х1 и Х2 располагаются близко к середине отрезка [а,в], то есть

Х1 = (в+а- б)/2

Х2 = (в+а+ б)/2 где б (дельта)>0 – малое число

При этом отношение длин нового и исходного отрезков τ(тау)

τ = (в-Х1)/(в-а) = (Х2-а)/(в-а) близко к ½, этим и объясняется название метода.

Отметим, что для любых точек Х1 и Х2 величина τ>1/2, поэтому указанный выбор пробных точек объясняется стремлением обеспечить максимально возможное относительное уменьшение отрезка на каждой итерации поиска Х* (Х* - точка min).

В конце вычислений по методу дихотомии в качестве приближенного значения Х* берут середину последнего из найденных отрезков [а,в], убедившись предварительно, что достигнуто неравенство (в-а)/2<= Е, где Е (эпсилон).

Опишем алгоритм метода деления отрезка пополам.

ШАГ1:

Определить Х1 и Х2 по формуле (1). Вычислить f(X1) и f(X2).

ШАГ2:

Сравнить f(X1) и f(X2). Если f(X1)<=f(X2), то перейти к отрезку [а,Х2], положив в=Х2, иначе – к отрезку [Х1,в], положив а=Х1.

ШАГ3:

Найти достигнутую точность Е n=(в-а)/2. Если Е n> Е, то перейти к следующей итерации, вернувшись к шагу 1. Если Е n<= Е, то завершить поиск Х*, перейдя к шагу 4.

ШАГ4:

Положить Х*≈=(а+в)/2, f*≈f(), где – середина отрезка [а,в]

Замечания:

1. Число б из (1) выбирается на интервале (0;2 Е) с учетом следующих соображений:

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

б) при чрезмерно малом б сравнение значений f(x) в точках Х1 и Х2, отличающихся на величину б, становится затруднительным. Поэтому выбор б должен быть согласован с точностью определения f(х) и с количеством верхних десятичных знаков при задании аргумента Х.

2. Число итераций, необходимое для определения точки Х* с точностью Е, определяется неравенством:

n >= log2 (в-а- б)/(2 Е - б) [2]

3. Величина б может быть выбрана достаточно малой, поэтому, пренебрегая ею в [2], получим Е n ≈ (в-а)/2.

На каждой итерации метода дихотомии вычисляются два значения f(x). Поэтому после N-вычислений f(x) производится n=N/2 итераций и достигается точность определения Х*:

Е(N) = Е ≈(в-а)/ 2 [3]

Дата добавления: 2014-01-07