Методы последовательного поиска

Большая группа этих методов основана на следующей схеме. Строится последовательность вложенных друг в друга отрезков локализации , , где . Если , то . На практике знание такой последовательности отрезков локализации позволяет локализовать минимум с необходимой точностью. Например, если задано некоторое , то при таком, что , любую точку отрезка можно считать приближенным решением задачи. При этом .

Методы последовательного поиска различаются способами построения последовательности отрезков , В частности, одним из вариантов последовательного поиска является многократное повторение пассивного поиска на получаемых отрезках локализации. Например, ес-

ли на каждом этапе полагать , то есть , , , , и , то точки будут делить отрезок локализации на четыре равные части. Следовательно, длина нового отрезка локализации будет в 2 (а иногда, возможно, и в 4) раза меньше длины отрезка .

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

Далее мы обсудим возможность построения таких схем построения отрезков локализации, ко-торые позволят на каждой итерации добавлять к

уже известным узлам только лишь один новый. Но прежде мы приведем еще одно свойство унимодальной на отрезке функции .

Теорема 1. Пусть числа таковы, что . Если , то отрезок является отрезком локализации, если же , то тогда отрезок является отрезком локализации.

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

Пусть построен отрезок локализации , где Опишем способ нахождения отрезка . Тем или иным способом находятся числа такие, что . Если , то полагаем . Иначе полагаем .

Основное различие методов в рамках этой схемы состоит в разных правилах вычисления точек . Во многих из этих методов точки расположены симметрично относительно середины

текущего отрезка локализации. К таким методам

относятся, например, метод дихотомии, метод золотого сечения, метод Фибоначчи и другие.

Остановимся коротко на двух из них.

Date: 2015-06-12; view: 995; Нарушение авторских прав