Метод золотого сечения.
Пусть — унимодальная функция одного аргумента на
. К функции
не предъявляются требования дифференцируемости или непрерывности. Предполагается, что для любого
значение
может быть вычислено.
Для реализации метода золотого сечения строится следующий итерационный процесс.
Обозначим — левую границу интервала неопределённости, а через
— правую границу интервала неопределённости на
-ом шаге итерационного процесса.
Интервалом неопределённости будем называть отрезок числовой оси, на котором находится экстремум целевой функции . Первоначально предполагается, что интервал неопределённости совпадает с
, т.е.
,
.
Идея метода золотого сечения заключается в организации процедуры последовательного деления интервала неопределённости с использованием решающего правила, позволяющего выделить новый, уменьшённый интервал неопределённости.
Теперь рассмотрим способ размещения внутренних точек на каждом отрезке . Пусть длина интервала неопределенности равна
, а точка деления разбивает его на части
:
,
. Золотое сечение интервала неопределенности выбирается так, чтобы отношение длины большего отрезка к длине всего интервала равнялось отношению длины меньшего отрезка к длине большего отрезка:
Из этого соотношения можно найти точку деления, вычислив отношения
Так как нас интересуют только положительные значения, то
Тогда ,
.
Пусть к настоящему моменту уже сделано шагов метода золотого сечения.
Интервал неопределённости ограничен отрезком . На этом отрезке в точках:
(1)
вычислены значения целевой функции и
.
На рис.1. показаны три возможных варианта соотношений и
.
1. Если , то искомое значение минимума функции
очевидно находится на отрезке
и, следовательно, интервал неопределённости
уменьшается до
. Очевидно, что тогда:
,
.
В методе золотого сечения пропорции выбраны таким образом, что точка (отстоящая от
на
относительные единицы длины отрезка
) на отрезке
будет отстоять на те же
относительные единицы влево от точки
. Тогда
и для выполнения
-го шага метода золотого сечения нам потребуется вычислить
2. Если , то искомое значение минимума функции
лежит на отрезке
, в этом случае необходимо выполнить следующие действия:
3. Равенство означает, что точка минимума функции
расположена между
и
, тогда
Метод золотого сечения хорош тем, что для выполнения каждого шага итерации необходимо выполнить лишь одно дополнительное вычисление функции . При этом интервал неопределённости уменьшается на
%, а в случае равенства
и
на
%. Величина оставшегося интервала неопределённости может служить критерием останова алгоритма оптимизации, то есть если выполняется условие
, то можно считать, что искомый оптимум функции найден с точностью
.