Изменения

{{В разработке}}'''Поиск с помощью золотого сечения''' (англ. ''Golden section search'') {{--- }} это улучшение наивной реализации [[Троичный поиск|троичного поиска]], служащий служащего для поиска нахождения минимума/максимума функции. При простом троичном поиске на каждой итерации функция вычисляется в двух точках. Метод же золотого сечения требует вычисления лишь в одной точке (за исключением первой итерации). За счет этого достигается выйгрыш в производительности.

===Мотивация===Рассмотрим одну итерацию алгоритма [[Троичный поиск|троичного поиска]]. Попробуем подобрать такое разбиение отрезка на три части, чтобы на следующей итерации одна из точек нового разбиения совпала с одной из точек текущего разбиения. Тогда в следующий раз не придется считать функцию в двух точках, так как в одной она уже была посчитана.

[[Файл:Goldensectionnew_seg.gif|220pxright|450px|Старая точка x1 уже делит отрезок в нужном отношении, поэтому нет необходимости вычислять ее заново (красным отмечены новые значения точек).]]

Точки <tex>x_1</tex> и <tex>x_2</tex> разбивают отрезок на три части. ПотребуемДля этого нам потребуется, чтобы одновременно выполнялосьвыполнялись равенства:

<tex> \fracdfrac{a + b}{c} = \fracdfrac{b + c}{a} = \phi varphi </tex>

Расстояние от <tex>l</tex> до <tex>x1 = a + b - c = a' </tex>, от <tex>x2 </tex> до <tex> r = b = c'</tex>, от <tex>х1 </tex> до <tex> х2 = c - b = b'</tex>. Т.е. если мы подставим <tex>a', b', c'</tex> в старое соотношение <tex> \dfrac{a + b}{c} </tex>, то получится <tex> \fracdfrac {a+ b - c + c - b}{b} = \phi dfrac{a}{b}</tex>.

<tex> \fracdfrac{ca}{b} = \phi varphi </tex>

<tex> \dfrac{c}{b} = \varphi </tex> Где <tex> \phi varphi </tex> {{--- }} это некоторое отношение, в котором мы делим отрезок (точки <tex>x_1</tex> и <tex>x_2</tex> разбивают отрезок симметрично).

<tex> a + b = \phi varphi c, a = \phi varphi b, c = \phi varphi b</tex>, откуда получаем <tex> \phi varphi + 1 = \phivarphi^2 \Rightarrow \phi varphi = \fracdfrac{1 + \sqrt{5}}{2}</tex> &nbsp; (тот корень уравнения, который меньше нуля, по понятным причнам причинам отбросили).

Это число совпадает с золотым сечением. Отсюда название метода.

===Свойства золотого сечения===Для реализации алгоритма нам потребуется найти <tex> a </tex> и <tex> a + b </tex>. Если <tex> L </tex> {{- --}} длина исследуемого отрезка, тогда:

<tex> \left(\fracdfrac{b + c}{a} = \phivarphi;\; b + c = L - a\right) \Rightarrow</tex>

<tex> a = \fracdfrac{L}{\phi varphi + 1} </tex>

<tex> a + b = L - c = L - a = L - \fracdfrac{L}{\phi varphi + 1}</tex>

ПричемЗаметим, заметим что в силу того , что <tex>\phivarphi</tex> {{- --}} золотое сечение, то <tex>\fracdfrac{1}{\phi varphi + 1} = 2 - \phivarphi</tex>.

===Итоговый алгоритм выбора границ===Формально для поиска минимума (для максимума {{- --}} делается аналогично) функции <tex> f </tex> делаем следующее:

::Определяем границы поиска <tex>lboundl</tex> и <tex>rboundr</tex>, затем устанавливаем текущее разбиение:::<tex>x_1 = lbound l + \fracdfrac{rbound r - lboundl}{\phi varphi + 1}</tex> ::<tex>x_2 = rbound r - \fracdfrac{rbound r - lboundl}{\phi varphi + 1}</tex>::и вычислем вычислим функцию на них: <tex>f_1 = f(x_1), f_2 = f(x_2)</tex>[[Файл:Nextsection.gif|thumb|380px|Старая точка x1 уже делит отрезок в нужном отношении, поэтому нет необходимости вычислять ее заново (красным отмечены новые значения точек).]]

::: <tex>rbound r = x_2</tex>

::: <tex>x_1 = lbound l + \fracdfrac{rbound r - lboundl}{\phi varphi + 1},\; f_1 = f(x_1)</tex>

::: <tex>lbound l = x_1</tex>

::: <tex>x_2 = rbound r - \fracdfrac{rbound r - lboundl}{\phi varphi + 1},\; f_2 = f(x_2)</tex>

:: если точность <tex>|rbound r - lboundl| < \varepsilon</tex> нас устраивает, тогда останавливаемся, и искомая точка <tex>x = \fracdfrac{lbound l + rboundr}{2}</tex>, иначе назад к шагу 2

  '''double''' goldenSectionSearch(f: '''double -> double''', l: '''double''', r: '''double''', eps: '''double'''): phi = (1 + sqrt(5)) / 2 resphi = 2 - phi goldenSectionSearch(f, lbound, rbound, eps) x1 = lbound l + resphi * (rbound r - lboundl) x2 = rbound r - resphi * (rbound r - lboundl) f1 = f(x1) f2 = f(x2) '''do''' '''if ''' f1 < f2: rbound r = x2 x2 = x1 f2 = f1 x1 = lbound l + resphi * (rbound r - lboundl) f1 = f(x1) '''else:''' lbound l = x1 x1 = x2 f1 = f2 x2 = rbound r - resphi * (rbound r - lboundl) f2 = f(x2) '''while (''' abs(rbound r - lboundl) < > eps) '''return ''' (x1 + x2) / 2 

На Так как на каждой итерации исследуемый отрезок сокращается мы считаем одно значение функции и уменьшаем область поиска в <tex>\phivarphi </tex> раз и делается один расчет функции, до тех пор, пока не станет <tex>|L| r - l > \varepsilon</tex>,то время работы алгоритма составит < tex> \log_{\varphi}\left(\dfrac{r - l}{\varepsilon}\right)</tex>.  Если считать, что одна итерация выполняется за 1 времени, то потребуется удельный вес вычисления функции <tex> n f </tex> операцийдостаточно большой, чтобы: тогда получим ускорение работы по сравнению с неулучшенным [[Троичный поиск|троичным поиском]] (<tex>L \cdot log_{\varphi}\left(\fracdfrac{1r - l}{\phivarepsilon}\right)^n < /tex> против <tex>2 \varepsilon \Rightarrow n = [log_{\phifrac32}\left(\fracdfrac{Lr - l}{\varepsilon}\right)]</tex>.

Значит время работы можно оценивать как За счет этого достигается выигрыш в производительности, т.к. каждый новый отрезок в <tex>\approx 1.618 </tex> раз короче предыдущего (против <tex>1.5</tex> у троичного поиска) и сходится он в <tex> \log_{\phifrac32}\left(\fracdfrac{L1 + \sqrt{5}}{2}\varepsilon}right)\approx 1.1868 </tex>.Если удельный вес вычисления функции быстрее, чем в троичном поиске, соответственно, в <tex> f \approx 2.3736 </tex> достаточно большой, тогда получим ускорение работы примерно в 2,3 раз по сравнению с неулучшенным троичным поискомраза меньше вычислений.

==СсылкиИсточники информации==*[http://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B7%D0%BE%D0%BB%D0%BE%D1%82%D0%BE%D0%B3%D0%BE_%D1%81%D0%B5%D1%87%D0%B5%D0%BD%D0%B8%D1%8F Википедия {{- --}} Метод золотого сечения]*[http://en.wikipedia.org/wiki/Golden_section_search Wikipedia {{---}} Golden section search]

*[http[Категория://en.wikipedia.org/wiki/Golden_section_search Wikipedia - Golden section searchДискретная математика и алгоритмы]][[Категория:Алгоритмы поиска]] (english)