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

Постановка задачи. Пусть известен отрезок [ A, B ] – отрезок локализации. На отрезке [ A, B ] найти точку минимума функции f(x) и отвечающее ей значение функции.

Метод дихотомии заключается в последовательном сокращении отрезка локализации.

Введём обозначение: [ A, B ] ® [ A ⁽⁰⁾ ,B ⁽⁰⁾] – начальный отрезок.

1) На отрезке [ A, B ] выберем две симметрично расположенные точки α и β (рис.2.2):

где 0 < d < (B - A)/2

d - параметр метода – его конкретная величина будет определена далее.

2) Вычислим значения f (a ⁽⁰⁾), f (b ⁽⁰⁾)

3) Из утверждения 2 для унимодальных функций имеем:

если f (a ⁽⁰⁾) £ f (b ⁽⁰⁾), то Î [ A ⁽⁰⁾, b ⁽⁰⁾]; тогда A ^{(1 )} = A ⁽⁰⁾, B ⁽¹⁾ = b ⁽⁰⁾;

если f (a ⁽⁰⁾) > f (b ⁽⁰⁾), то Î [ a ⁽⁰⁾, B ⁽⁰⁾]; тогда A ^{(1 )} = a ⁽⁰⁾, B ⁽¹⁾ = B ⁽⁰⁾;

Получили [ A ^{(1 )} , B ⁽¹⁾ ] – новый отрезок локализации.

4) Далее, повторяя пункты 1) – 3), на k+1 -ом шаге на отрезке [ A ^{(k )} ,B ^(k)] снова выберем две симметрично расположенные точки α;^(k) и β;^(k):

5) За очередное приближение к точке минимума можно выбрать:

х^(k) = a ^(k) или х^(k) = b ^(k)

6) Обозначим D⁽ⁿ⁾ = B ⁽ⁿ⁾ – A ⁽ⁿ⁾ - длина отрезка [ A ^{(n )} ,B ⁽ⁿ⁾]

Тогда справедливо равенство:

откуда следует: , где D = B – A - длина отрезка [ A, B ].

D⁽ⁿ⁾ убывает и при n ® ¥ стремится к 2 d.

Чтобы D⁽ⁿ⁾ стало меньше некоторого заданного e > 0, надо выбрать параметр метода d < e/2.

Тогда из соотношения | x ⁽ⁿ⁾- | < D⁽ⁿ⁾ следует, что значение можно найти с точностью e, если выполнять вычисления, пока не выполнится условие: D⁽ⁿ⁾ £ e.

Тогда ^* = x ⁽ⁿ⁾ – приближение к с точностью e.

Метод дихотомии для поиска абсциссы точки, в которой целевая функция F(x) достигает своего минимума, оформим в виде процедуры DIHOTOM.

Блок-схема алгоритма процедуры DIHOTOM(A,B,Eps,X0) приведена на рис.2.3.

F(x) – заданная целевая функция – должна быть описана отдельно.

Входные параметры: А, B – значения концов отрезка локализации [A, B];

Eps – заданная точность вычислений;

Выходные параметры: X0 - приближение к искомому значению абсциссы точки минимума;

DIHOTOM (A, B, Eps, X0)

Здесь параметр метода выбрали δ = ε/3 < ε/2

Alfa = (A + B)/2 – Eps/3

Beta = (A + B)/2 + Eps/3

FA = F(Alfa)

FB = F(Beta)

-

+

FA £ FB

B = Beta A = Alfa

 

-

|B – A| < Eps

+

X0 = (A + B)/2

end

 

Рисунок 2.3 - Блок-схема алгоритма процедуры DIHOTOM