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

Заняття 12

МЕТОДЫ ОДНОМЕРНОЙ ОПТИМИЗАЦИИ

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

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

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

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

1. Выполняем присваивания , , , .
2. Вычисляем величины (см. рис. 1)
   
3. Вычисляем значения функции ( ).
4. Если , то выполняем присваивания , , . Иначе - выполняем присваивания , ,
5. Если , то заканчиваем вычисления. Иначе - выполняем присваивание = +1 и переходим на п.2.

Рис. 1. К определению величин x₀^r,x₁^r,x₂^r.

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

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

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

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