223
правки
Изменения
Нет описания правки
<tex> \frac{c}{b} = \phi </tex>
Где <tex> \phi </tex> - это некоторое отношение, в котором мы делим отрезок (точки <tex>x_1</tex> и <tex>x_2</tex> разбивают отрезок симметрично).
Тогда:
<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> a </tex> и <tex> a + b </tex>. Если <tex> L </tex> - длина исследуемого отрезка, тогда:
<tex> (\frac{b + c}{a} = \phi;\; b + c = L - a) \Rightarrow</tex> <tex> a = \frac{L}{\phi + 1} </tex> <tex> a + b = L - c = L - a = L - \frac{L}{\phi + 1}</tex> Причем, заметим что в силу того что <tex>\phi</tex> - золотое сечение, то <tex>\frac{1}{\phi + 1} = 2 - \phi</tex>. Формально для поиска минимума (для максимума - делается аналогично) функции <tex> f </tex>делаем следующее:
:'''Шаг 1''':
::<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>f_1 < f_2</tex>, тогда::: <tex>rbound = x_2</tex>::: <tex>x_2 = x_1, f_2 = f_1</tex>::: <tex>x_1 = lbound + \frac{rbound - lbound}{\phi + 1},\; f_1 = f(x_1) < /tex> :: иначе:::: <tex>lbound = x_1</tex>::: <tex>x_1 = x_2, f_1 = f_2</tex>::: <tex>x_2 = rbound - \frac{rbound - lbound}{\phi + 1},\; f_2 = f(x_2)</tex>:'''Шаг 3''':::если точность <tex>|rbound - lbound| < \varepsilon</tex> нас устраивает, тогда останавливаемся, и искомая точка <tex>x = \frac{lbound + rbound}{2}</tex>, иначе назад к шагу 2
===Псевдокод===
phi = (1 + sqrt(5)) / 2
resphi = 2 - phi
goldenSectionSearch(f, lbound, rbound, eps)
x1 = lbound + resphi * (rbound - lbound)
x2 = rbound - resphi * (rbound - lbound)
f1 = f(x1)
f2 = f(x2)
do
if f1 < f2:
rbound = x2
x2 = x1
f2 = f1
x1 = lbound + resphi * (rbound - lbound)
f1 = f(x1)
else:
lbound = x1
x1 = x2
f1 = f2
x2 = rbound - resphi * (rbound - lbound)
f2 = f(x2)
while (abs(rbound - lbound) < eps)
return (x1 + x2) / 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 раз по сравнению с неулучшенным троичным поиском.
==АсимптотикаСм также==*[[Троичный поиск]]
==Ссылки==
*[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] (english)
