Изменения
Нет описания правки
'''Поиск с помощью золотого сечения''' (''Golden section search'') {{- --}} это улучшение наивной реализации [[Троичный поиск|троичного поиска]], служащего для нахождения минимума/максимума функции. При простом троичном поиске на каждой итерации функция вычисляется в двух точках. Метод же золотого сечения требует вычисления лишь в одной точке (за исключением первой итерации). За счет этого достигается выигрыш в производительности.
==Алгоритм==
Пусть <tex>l</tex> и <tex>r</tex> левая и правая граница исследуемого отрезка.
Точки <tex>x_1</tex> и <tex>x_2</tex> разбивают отрезок на три части, длины <tex>a, b, c</tex> соответственно. Потребуем, чтобы одновременно выполнялось:
<tex> \frac{a + b}{c} = \frac{b + c}{a} = \varphi </tex>
<tex> \frac{c}{b} = \varphi </tex>
Где <tex> \varphi </tex> {{- --}} это некоторое отношение, в котором мы делим отрезок (точки <tex>x_1</tex> и <tex>x_2</tex> разбивают отрезок симметрично).
Тогда:
<tex> a + b = L - c = L - a = L - \frac{L}{\varphi + 1}</tex>
Причем, заметим что в силу того что <tex>\varphi</tex> {{- --}} золотое сечение, то <tex>\frac{1}{\varphi + 1} = 2 - \varphi</tex>.
Формально для поиска минимума (для максимума {{- --}} делается аналогично) функции <tex> f </tex> делаем следующее:
:'''Шаг 1''':
x2 = r - resphi * (r - l)
f2 = f(x2)
while (abs(r - l) > eps)
return (x1 + x2) / 2
