Метод дихотомии деления отрезка пополам

Разделим полученный в результате нормирования отрезок на оси абсцисс на четыре равные части и вычислим значение целевой функции в пяти точках: 0, 1/4, 1/2, 3/4, 1. Затем выберем минимальное из пяти найденных значений. Очевидно, что экстремум функции лежит в границах нормированного участка [1/4, 3/4], (соответственно участка [a‘, b] изменения переменной p), прилегающего с двух сторон к точке найденного минимума. Следовательно, интервал поиска сужается в два раза. Если минимум находится в точке 0 (а) или 1 (b), то интервал сужается в четыре раза.

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

Рис. 2. Иллюстрация метода дихотомии

2. Метод Фибоначчи

В основу метода положен ряд чисел, называемых числами Фибоначчи. Это ряд F0 = F1 = 1, F2 = 2, F3 = 3, F4 = 5, F5 = 8,…, Fk = Fk-1+Fk-2. Предлагаемая стратегия последовательного поиска экстремума назы­вается поиском Фибоначчи, поскольку она тесно связана с этими числами. При оптимальной стратегии поиска выбираем два значения переменной pk-1 = Fk-2/Fk и pk = Fk-1/Fk и проводим вычисление целевой функции в четырех точках. Какой бы из интервалов [0, pk] или [pk-1,1] не стал суженным интервалом неопределенности, в нем находится «унаследованная» точка, т.е. точка, значение целевой функции в которой уже вычислено и будет использовано на последующем шаге. Она будет иметь по отношению к новому интервалу одну из двух следующих координат: Fk-3/Fk-1 или Fk-2/Fk-1. На втором шаге, вычисление целевой функции проводим только для одной новой переменной pk-2. Используя Ф(pk-2) и зна­чение функции, унаследованное от прежнего интервала, сокращаем интервал неопределенности и передаем в наслед­ство следующему шагу одно значение функции. На последнем шаге мы придем к некоторому интервалу

You can leave a response, or trackback from your own site.

Leave a Reply