Метод золотого сечения.
[latexpage]
Пусть $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]$. На этом отрезке в точках:
\begin{equation} \label{eq: 1}
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$.