- некоторую начальную точку,
- величину шага. Положить
.1.2. Алгоритм Свенна
Для эвристического выбора начального интервала неопределенности можно применить алгоритм Свенна [8]:
1. Задать произвольно следующие параметры:
- некоторую начальную точку,
- величину шага. Положить
.
2. Вычислить значение функции
в трех точках:
.
3. Проверить условие окончания:
а) Если
, то начальный интервал неопределенности найден:
.
б) Если
, то функция не является унимодальной, а требуемый интервал неопределенности не может быть найден. Вычисления при этом прекращаются (рекомендуется задать другую начальную точку
).
в) Если условие окончания не выполняется, то перейти к шагу 4.
4. Определить величину
:
а) Если
, то
.
б) Если
, то
.
5. Найти следующую точку
.
6. Проверить условие убывания функции:
а) Если
и
, то
.
Если
и
, то
.
В обоих случаях положить
и перейти к шагу 5.
б) Если
, процедура завершается.
При
положить
, а при
положить
. В результате имеем
- искомый интервал неопределенности.
Далее, уменьшение интервала неопределенности осуществляется с использованием последовательной стратегии, т.е. производится на основании вычисления функции в двух точках текущего интервала. Свойство унимодальности позволяет определить, в каком из возможных подынтервалов точка минимума отсутствует. В качестве нового интервала берется интервал, наверняка содержащий точку минимума (метод деления отрезка пополам, метод «золотого» сечения, метод Фибоначчи).
Для оценки эффективности алгоритмов уменьшения интервала неопределенности при заданном числе
вычислений функции введем критерий.
Определение 8. Характеристикой
относительного уменьшения начального интервала неопределенности называется отношение
,
где
- длина интервала, полученного в результате
вычислений функции,
- длина начального интервала неопределенности.
Пример 3. Найти начальный интервал неопределенности для поиска минимума функции
.
Решение. Воспользуемся алгоритмом Свенна.
1. Зададим
и
. Положим
.
20. Вычислим значения функции в точках:
.
Тогда получим
.
30. Условия окончания не выполняются.
40. Так как
, то полагаем
.
50. Найдем следующую точку:
.
60. Так как
и
, то
. Положим
и перейдем к шагу 5.
51. Найдем следующую точку
.
61. Так как
и
, то поиск завершен, полагаем
.
Поэтому начальный интервал неопределенности
.