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

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

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

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

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

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

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

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

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

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

Рис. 1. К определению величинx0r,x1r,x2r.

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

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

Рис. 2. Первые две итерации поиска минимума одномерной унимодальной функции с помощью алгоритма равномерного дихотомического поиска.

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