Метод золотого сечения
Метод "золотого" сечения требует только унимодальности функции .
"Золотое" сечение, открытое Евклидом, состоит в разбиении интервала [а,b] точкой x1 на две части таким образом, чтобы отношение большей части к длине всего интервала было равно отношению меньшей части к большей.
. (33.1)
Представим интервал [а,b] как совокупность двух отрезков:
. (7.2)
Разделив уравнение (33.2) на (b-а), получим:
.
Так как и , имеем , корни которого определяются по формуле:
т.е. .
Из уравнения (33.1) следует
. (33.3)
Проведем "золотое" сечение относительно точки а, получим
. (33.4)
Из уравнения (33.4) получим формулу для определения точки x2:
. (33.5)
Заметим, что точка x1 производит "золотое" сечение интервала [а,x2], а точка x2 – интервала [x1,b].
Для унимодальной функции, зная значения функции в точках золотого сечения и , можно определить интервал неопределенности, в котором находится . После выбора на оставшемся интервале нужно определить только одну точку, производящую "золотое" сечение. Для выбранного интервала [а,x2] следует положить b=x2, x2=x1 и пересчитать точку x1 по формуле (33.3), а для [x1,b] – a=x1, x1=x2 и пересчитать точку x2 по формуле (33.5). На каждом шаге итерации длина интервала неопределенности уменьшается и составляет примерно 0,62 длины предыдущего интервала неопределенности. Итерационную процедуру следует закончить, когда длина интервала неопределенности станет меньше или равна заданной точности.
Алгоритм метода "золотого" сечения:
1. Ввод a, b, ε. Вычисляем значения x1 и x2 по формулам (33.3), (33.5).
2. Вычисляем и .
3. Если , то находится в интервале [а,x2] (рис.33.1б), т.е. b=x2. Переопределяем точки x2=x1 и f2=f1, пересчитываем точку x1 по формуле (33.3) и вычисляем f1. Переходим на п.4.
Если , то находится в интервале [x1,b] (рис.33.1а), т.е. a=x1, x1=x2, f1=f2. Пересчитываем точку x2 по формуле (33.5) и вычисляем f2.
4. Проверка (b–а)<ε, если нет, то переходим на п.3, да – на п.5.
5. Печать , оптимального значения критерия , для контроля правильности полученных данных.
Рис.33.1
Лекция №34
Дата добавления: 2015-11-06; просмотров: 1047;