223
правки
Изменения
Нет описания правки
'''Поиск с помощью золотого сечения''' (''Golden section search'') - это улучшение наивной реализации [[Троичный поиск|троичного поиска]], служащий для поиска минимума/максимума функции. При простом троичном поиске на каждой итерации функция вычисляется в двух точках. Метод же золотого сечения требует вычисления лишь в одной точке (за исключением первой итерации). За счет этого достигается выйгрыш выигрыш в производительности.
==Алгоритм==
Тогда:
<tex> a + b = \phi c, a = \phi b, c = \phi b</tex>, откуда получаем <tex> \phi + 1 = \phi^2 \Rightarrow \phi = \frac{1 + \sqrt{5}}{2}</tex> (тот корень уравнения, который меньше нуля, по понятным причнам причинам отбросили).
Это число совпадает с золотым сечением. Отсюда название метода.
::<tex>x_1 = lbound + \frac{rbound - lbound}{\phi + 1}</tex>
::<tex>x_2 = rbound - \frac{rbound - lbound}{\phi + 1}</tex>
::и вычислем вычислим функцию на них: <tex>f_1 = f(x_1), f_2 = f(x_2)</tex>
[[Файл:Nextsection.gif|thumb|380px|Старая точка x1 уже делит отрезок в нужном отношении, поэтому нет необходимости вычислять ее заново (красным отмечены новые значения точек).]]
:'''Шаг 2''':
На каждой итерации исследуемый отрезок сокращается в <tex>\phi</tex> раз и делается один расчет функции, до тех пор, пока не станет <tex>|L| < \varepsilon</tex>. Если считать, что одна итерация выполняется за 1 времени, то потребуется <tex> n </tex> операций, чтобы: <tex>L \cdot (\frac{1}{\phi})^n < \varepsilon \Rightarrow n = [log_{\phi}(\frac{L}{\varepsilon})]</tex>.
Значит , время работы можно оценивать как <tex> log_{\phi}(\frac{L}{\varepsilon})</tex>.
Если удельный вес вычисления функции <tex> f </tex> достаточно большой, тогда получим ускорение работы примерно в 2,3 раз по сравнению с неулучшенным троичным поиском.
