ВИ Метод золотого сечения

06.12.2013

Метод золотого сечения.

Пусть $f(x)$ — унимодальная функция одного аргумента на $[a,b]$ . К функции $f(x)$ не предъявляются требования дифференцируемости или непрерывности. Предполагается, что для любого $x \in [a,b]$ значение $f(x)$ может быть вычислено.

Для реализации метода золотого сечения строится следующий итерационный процесс.

Обозначим $a_k$ — левую границу интервала неопределённости, а через $b_k$ — правую границу интервала неопределённости на $k$ -ом шаге итерационного процесса.
Интервалом неопределённости будем называть отрезок числовой оси, на котором находится экстремум целевой функции $f(x)$ . Первоначально предполагается, что интервал неопределённости совпадает с $[a,b]$ , т.е. $a_0=a$ , $b_0=b$ .

Идея метода золотого сечения заключается в организации процедуры последовательного деления интервала неопределённости с использованием решающего правила, позволяющего выделить новый, уменьшённый интервал неопределённости.

Теперь рассмотрим способ размещения внутренних точек на каждом отрезке $[a_k,b_k]$ . Пусть длина интервала неопределенности равна $l$ , а точка деления разбивает его на части $l_1,l_2$ : $l_1>l_2$ , $l=l_1+l_2$ . Золотое сечение интервала неопределенности выбирается так, чтобы отношение длины большего отрезка к длине всего интервала равнялось отношению длины меньшего отрезка к длине большего отрезка:

$\frac {l_1}{l}=\frac {l_2}{l_1}.$

Из этого соотношения можно найти точку деления, вычислив отношения

$\alpha=\frac {l_1}{l} , \beta=\frac {l_2}{l}.$

Так как нас интересуют только положительные значения, то

$\alpha=\frac {-1+\sqrt{5}}{2}, \beta=1- \alpha=\frac {3-\sqrt{5}}{2}.$

Тогда $l_1=\alpha l$ , $l_2=\beta l$ .
Пусть к настоящему моменту уже сделано $k$ шагов метода золотого сечения.

Интервал неопределённости ограничен отрезком $[a_k,b_k]$ . На этом отрезке в точках:

(1) $\begin{equation*} x_1^{(k)}=a_k+\beta(b_k-a_k), \text{ } x_2^{(k)}=b_k-\beta(b_k-a_k) \end{equation*}$

вычислены значения целевой функции $y_1=f(x_1^{(k)})$ и $y_2=f(x_2^{(k)}$ .

$золотое сечение$

Рис.1. Выбор интервала неопределённости для метода золотого сечения

На рис.1. показаны три возможных варианта соотношений $y_1$ и $y_2$ .

1. Если $y_1<y_2$ , то искомое значение минимума функции $f(x)$ очевидно находится на отрезке $[a_k,x_2]$ и, следовательно, интервал неопределённости $[a_k,b_k]$ уменьшается до $[a_k,x_2]$ . Очевидно, что тогда: $a_{k+1}=a_k$ , $b_{k+1}=x_2^{(k)}$ .

В методе золотого сечения пропорции выбраны таким образом, что точка $x_1^{(k)}$ (отстоящая от $a_k$ на $\beta$ относительные единицы длины отрезка $[a_k,b_k]$ ) на отрезке $[a_{k+1},b_{k+1}]$ будет отстоять на те же $\beta$ относительные единицы влево от точки $b_{k+1}$ . Тогда $x_2^{(k+1)}=x_1^{(k)}$ и для выполнения $(k+1)$ -го шага метода золотого сечения нам потребуется вычислить

$x_1^{(k+1)}=a_{k+1}+\beta(b_{k+1}-a_{k+1})$

2. Если $y_1>y_2$ , то искомое значение минимума функции $f(x)$ лежит на отрезке $[x_1,b_k]$ , в этом случае необходимо выполнить следующие действия:

$a_{k+1}=x_1^{(k)},$

$b_{k+1}=b_k},$

$x_1^{(k+1)}=x_2^{(k)},$

$x_2^{(k+1)}=b_{k+1}-\beta(b_{k+1}-a_{k+1}).$

3. Равенство $y_1=y_2$ означает, что точка минимума функции $f(x)$ расположена между $x_1^{(k)}$ и $x_2^{(k)}$ , тогда

$a_{k+1}=x_1^{(k)},$

$b_{k+1}=x_2^{(k)},$

$x_1^{(k+1)}=a_{k+1}+\beta(b_{k+1}-a_{k+1}),$

$x_2^{(k+1)}=b_{k+1}-\beta(b_{k+1}-a_{k+1}).$

Метод золотого сечения хорош тем, что для выполнения каждого шага итерации необходимо выполнить лишь одно дополнительное вычисление функции $f(x)$ . При этом интервал неопределённости уменьшается на $38,2$ %, а в случае равенства $y_1$ и $y_2$ на $76,4$ %. Величина оставшегося интервала неопределённости может служить критерием останова алгоритма оптимизации, то есть если выполняется условие $|b_{(k+1)}-a_{(k+1)}|<\epsilon$ , то можно считать, что искомый оптимум функции найден с точностью $\epsilon$ .

Updated: 20.09.2015 at 06:41

Метки: теория