Алгоритм деления пополам

Алгоритм деления пополам

Рассмотрим следующую задачу условной оптимизации: найти минимум одномерной унимодальной функции (), определенной в замкнутой области допустимых значений =[ , ],

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

Более строго описанную схему алгоритма можно записать в нижеследующем виде.

1. Выполняем присваивания , , , .

2. Вычисляем величины (см. рис. 1)

3. Вычисляем значения функции ().

4. Если , то выполняем присваивания , , . Иначе - выполняем присваивания , ,

5. Если , то заканчиваем вычисления. Иначе - выполняем присваивание = +1 и переходим на п.2.

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

Приведенную схему алгоритма равномерного дихотомического поиска иллюстрирует рис. 2.

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