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