Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Методы последовательного поиска
Большая группа этих методов основана на следующей схеме. Строится последовательность вложенных друг в друга отрезков локализации , , где . Если , то . На практике знание такой последовательности отрезков локализации позволяет локализовать минимум с необходимой точностью. Например, если задано некоторое , то при таком, что , любую точку отрезка можно считать приближенным решением задачи. При этом . Методы последовательного поиска различаются способами построения последовательности отрезков , В частности, одним из вариантов последовательного поиска является многократное повторение пассивного поиска на получаемых отрезках локализации. Например, ес-
ли на каждом этапе полагать , то есть , , , , и , то точки будут делить отрезок локализации на четыре равные части. Следовательно, длина нового отрезка локализации будет в 2 (а иногда, возможно, и в 4) раза меньше длины отрезка . Положительным моментом этого метода является высокая скорость уменьшения длины отрезка локализации (на каждой итерации гарантируется ее уменьшение в два раза). Легко вычислить количество итераций , необходимое для достижения заданной точности. Действительно, так как для любого выполняется , то – это наименьшее значение , для которого . Таким образом, . В то же время, отрицательным моментом этого метода является, то, что на каждой итерации необходимо к оставшимся с предыдущей итерации трем точкам , которые теперь обозначим как , добавить новые и вычислить значения функции . Далее мы обсудим возможность построения таких схем построения отрезков локализации, ко-торые позволят на каждой итерации добавлять к
уже известным узлам только лишь один новый. Но прежде мы приведем еще одно свойство унимодальной на отрезке функции . Теорема 1. Пусть числа таковы, что . Если , то отрезок является отрезком локализации, если же , то тогда отрезок является отрезком локализации. Это свойство унимодальных функций используется в различных методах одномерного поиска для построения последовательности отрезков локализации. Приведем основанную на теореме 2 принципиальную схему методов минимизации унимодальной функции , для которой известен отрезок локализации . Пусть построен отрезок локализации , где Опишем способ нахождения отрезка . Тем или иным способом находятся числа такие, что . Если , то полагаем . Иначе полагаем . Основное различие методов в рамках этой схемы состоит в разных правилах вычисления точек . Во многих из этих методов точки расположены симметрично относительно середины текущего отрезка локализации. К таким методам
относятся, например, метод дихотомии, метод золотого сечения, метод Фибоначчи и другие. Остановимся коротко на двух из них.
|