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

Метод половинного деления (метод дихотомии), использующийся для решения задачи (1.1.1), относится к методам нулевого порядка и применяется для унимодальных на некотором начальном интервале (a, b) функций. Он предполагает выполнение двух этапов:

– отделение (локализация) положения локального минимума с целью построения начального интервала неопределенности D₀ = (a, b) (в данной работе не рассматривается);

– последовательное уменьшение длины интервала неопределенности (этот этап отражает суть метода).

Уменьшение длины интервала неопределенности методом половинного деления осуществляется следующим образом. Пусть функция f(x) является унимодальной на интервале D₀ = (a, b), содержащем х^* Î (a, b) – точку искомого минимума функции f(x). Зададим достаточно малое число
e > 0, затем выберем симметрично относительно центра интервала D₀ две пробные точки: x₁ = (b – a)/2 – e/2 и x₂ = (b – a)/2 + e/2. Число e определяет степень различимости этих точек. Построим очередной интервал неопределенности, который содержит точку минимума, используя свойства унимодальной на интервале D₀ функции f(x). Очевидно, этот интервал неопределенности D₁ будет совпадать с одним из интервалов: (а, x₂), (x₁, b) или (x₁, x₂). Следовательно, его возможная наибольшая длина êD₁ê = (b – a)/2 + e/2.

Теперь приведем более формальное описание метода половинного деления. Пусть функция f(x) является унимодальной на интервале (a, b), заданы достаточно малые числа e > 0 и d > 0 – требуемая точность определения точки искомого минимума данной функции х^* Î (a, b). Тогда метод половинного деления можно записать в виде следующего алгоритма.

1. Задать функцию f(x) и числа а, b, d > 0, e > 0.

2. Если b – a £ 2d Þ перейти к выполнению п. 8.

3. Вычислить с = (a + b)/2.

4. Задать х₁ = с – e/2 и х₂ = х₁ + e.

5. Вычислить f(x₁); f(x₂).

6. Если f(x₁) > f(x₂) положить a: = х₁.

Если f(x₁) < f(x₂) положить b := х₂.

Если f(x₁) = f(x₂) положить a: = х₁; b : = х₂;

7. Перейти к выполнению п. 2.

8. Положить х^* = (a + b)/2. Процесс завершен.

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

Таблица 1.2.1

Дадим общую характеристику метода половинного деления:

– всегда сходится к решению задачи (1.1.1);

– скорость сходимости метода практически линейная. На каждом шаге длина интервала неопределенности уменьшается, после k-го шага процесса она составляет не более (b – a)/2^k + (1 - 2^-k)e. Нетрудно подсчитать количество итераций, необходимых для уменьшения исходного интервала неопределенности в заданное количество раз. Например, чтобы уменьшить ее не менее чем в 100 раз, потребуется семь итераций;

– на каждом шаге требуется вычисление значений функции f(x)
в точках х₁ и х₂, которые расположены симметрично относительно центра текущего интервала неопределенности на расстоянии e друг от друга. Число e > 0 рекомендуется выбирать достаточно малым; практически оно ограничено снизу точностью производимых вычислений.

Таким образом, чтобы уменьшить длину исходного интервала неопределенности не менее чем в 100 раз, потребуется вычисление значения функции f(x) в 14 пробных точках. Для сравнения отметим, что можно
последовательно разместить внутри интервала неопределенности 99 точек с интервалом h = 0,01(b – a) и проанализировать значения функции в этих точках (так называемый пассивный поиск). В результате этих действий интервал неопределенности также будет уменьшен в 100 раз, но уже за счет 99 вычислений значений функции f(x). Следовательно, метод половинного деления является более эффективным, чем метод одновременного размещения большого количества пробных точек внутри исходного интервала неопределенности.