88
правок
Изменения
→Алгоритм
Рассмотрим одну итерацию алгоритма [[Троичный поиск|троичного поиска]]. Попробуем подобрать такое разбиение отрезка на три части, чтобы на следующей итерации одна из точек нового разбиения совпала с одной из точек текущего разбиения. Тогда в следующий раз не придется считать функцию в двух точках, так как в одной она уже была посчитана.
Точки <tex>x_1</tex> и <tex>x_2</tex> разбивают отрезок на три части, длины <tex>a, b, c</tex> соответственно. Потребуем, чтобы одновременно выполнялось:
<tex> \frac{a + b}{c} = \frac{b + c}{a} = \varphi </tex>
:'''Шаг 1''':
::Определяем границы поиска <tex>lbound</tex> и <tex>rbound</tex>, затем устанавливаем текущее разбиение:
::<tex>x_1 = lbound l + \frac{rbound r - lboundl}{\varphi + 1}</tex> ::<tex>x_2 = rbound r - \frac{rbound r - lboundl}{\varphi + 1}</tex>
::и вычислим функцию на них: <tex>f_1 = f(x_1), f_2 = f(x_2)</tex>
:'''Шаг 2''':
:: если <tex>f_1 < f_2</tex>, тогда
::: <tex>rbound r = x_2</tex>
::: <tex>x_2 = x_1, f_2 = f_1</tex>
::: <tex>x_1 = lbound l + \frac{rbound r - lboundl}{\varphi + 1},\; f_1 = f(x_1)</tex>
:: иначе:
::: <tex>lbound l = x_1</tex>
::: <tex>x_1 = x_2, f_1 = f_2</tex>
::: <tex>x_2 = rbound r - \frac{rbound r - lboundl}{\varphi + 1},\; f_2 = f(x_2)</tex>
:'''Шаг 3''':
:: если точность <tex>|rbound r - lboundl| < \varepsilon</tex> нас устраивает, тогда останавливаемся, и искомая точка <tex>x = \frac{lbound l + rboundr}{2}</tex>, иначе назад к шагу 2
===Псевдокод===
resphi = 2 - phi
goldenSectionSearch(f, lboundl, rboundr, 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:
x2 = x1
f2 = f1
x1 = lbound l + resphi * (rbound r - lboundl)
f1 = f(x1)
else:
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> r - l > \varepsilon</tex>,
