Додаток 7.1

Дата добавления: 2015-10-15; просмотров: 622

Замечательный Рэй метис немецкой овчарки I поколения, 7 лет. Ветпаспорт, здоровье превосходное. У Рэя умер хозяин и ему грозит приют!!Пес знает команды, отлично ходит на поводке, любит поездки в машине, диван, умный и добрый к людям. Всю жизнь прожил в квартире. Собака-компаньон. тел:8(926)2105538; 8(925)0907290

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

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

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

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

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

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

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

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

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

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

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

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

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

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