Метод основан на делении текущего отрезка [ а, b ], где содержится искомый экстремум, на две неравные части, подчиняющиеся правилу золотого сечения, для определения следующего отрезка, содержащего максимум.
Золотое сечение определяется по правилу: отношение отрезка к большей его части равно отношению большей части отрезка к меньшей. Ему удовлетворяют две точки с и d, расположенные симметрично относительно середины отрезка.
Рис. 3.3. Иллюстрация метода золотого сечения:
1 — интервал, включающий в себя искомый максимум функции после
первого этапа (первого золотого сечения в точках c и d );
2 — то же, после второго этапа (новая точка е и старая точка d
Путем сравнения R(с) и R(e) определяют следующий отрезок, где содержится максимум. Если R(e) > R(с), то в качестве следующего отрезка выбирается отрезок [ с, b ], в противном случае — отрезок [ a, e ].
Поэтому на каждой следующей итерации (кроме "запуска" метода на исходном отрезке) нужно вычислять только одно значение критерия оптимальности.
|
|
Новый отрезок снова делится на неравные части по правилу золотого сечения. Следует отметить, что точка d является и точкой золотого сечения отрезка [ с, b ], т.е.
Обозначим коэффициент золотого сечения k=db/cd, тогда можно получить квадратное уравнение для его нахождения
k=0,618
Решение уравнения применительно к первой итерации имеет вид
Условие окончания поиска — величина отрезка, содержащего максимум, меньше заданной погрешности.
Метод обеспечивает более быструю сходимость к решению, чем многие другие методы, и применим, очевидно, только для одноэкстремальных функций.
Пример.
Дана функция
R(x)=sin(x+1),
Найти максимум на интервале: [-1,2]. Ошибка задается по х: e =0,05.
Результаты расчетов. Для "запуска" метода найдем две симметричные точки золотого сечения для отрезка [-1, 2]:
х 1 = 0,145898, х 2 = 0,85410197.
Значения критериев в этих точках соответственно R(x 1 ) = 0,911080, R(x 2 ) = 0,960136. Следовательно, новым отрезком является [0,145898,2], внутри которого находится максимальное из найденных значений R. Точка золотого сечения для нового отрезка будет х 3 = 0,58359214, a R(x 3 ) = 0,99991813.
Далее приведены только координаты лучших точек при очередном шаге, номер шага и значения критерия в этих точках.
x 3 = 0,584 R 3 = 0,9999 x 4 = 0,584 R 4 = 0,9999
С точностью до четырёх значащих цифр задача решена на третьей итерации
d )
Рис. 3.4