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

23.06.2015

Поиск минимума функции M(X) на отрезке [а, b] (рис. 5.4) начинается с выбора двух точек: x1 = (a + b - δ) / 2 и x2 = (a + b + δ) / 2, где δ — постоянный параметр метода; 0 < δ < (b-а).
Величина δ выбирается исследователем и может определяться целесообразным количеством верных десятичных знаков при задании аргумента X. В этом случае x1 и x2 расположены на отрезке [а, b] симметрично относительно его середины и при малых значениях 8 делят его почти пополам — отсюда название метода. После выбора точек x1 и x2 вычисляются значения функций M(x1), M(x2), а затем сравниваются между собой. Если M(x1) < M(x2), то полагают, что a1 = а, b1 = х2, если же M(x1) ≥ M(x2), то a1 = x1, b1 = b. Для любого из рассматриваемых случаев длина получившегося отрезка, включающего точку минимума, равна b1 — a1 = (b — а + 8) / 2 = [(b — а — 8) / 2] + δ. Примечание: условие M(x1) = M(x2) означает конец поиска.
Продолжая далее аналогичные вычисления (путем деления полученных отрезков пополам), получим отрезок [аk, bk] длины (bk — аk) < ε; где ε — заданная точность, ε ≥ δ. Так как каждое деление пополам требует двух вычислений значений функции, то для достижения точности (bk — аk) < ε требуется n = 2k таких вычислений.

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