Главная Случайная страница


Полезное:

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


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






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





 

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

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

 

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

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

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

 

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

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

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

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

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

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

 

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

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

Date: 2015-06-12; view: 883; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.007 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию