Поиск с помощью золотого сечения

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян. Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием. Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей. Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить. Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.

meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

Поиск с помощью золотого сечения (англ. Golden section search) — это улучшение наивной реализации троичного поиска, служащего для нахождения минимума/максимума функции. При простом троичном поиске на каждой итерации функция вычисляется в двух точках. Метод же золотого сечения требует вычисления лишь в одной точке (за исключением первой итерации).

Алгоритм

Обоснование

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

Для этого нам потребуется, чтобы одновременно выполнялись равенства:

[math] \dfrac{a + b}{c} = \dfrac{b + c}{a} = \varphi [/math]

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

[math] \dfrac{a}{b} = \varphi [/math]

[math] \dfrac{c}{b} = \varphi [/math]

Где [math] \varphi [/math] — это некоторое отношение, в котором мы делим отрезок (точки [math]x_1[/math] и [math]x_2[/math] разбивают отрезок симметрично).

Тогда:

[math] a + b = \varphi c, a = \varphi b, c = \varphi b[/math], откуда получаем [math] \varphi + 1 = \varphi^2 \Rightarrow \varphi = \dfrac{1 + \sqrt{5}}{2}[/math]   (тот корень уравнения, который меньше нуля, по понятным причинам отбросили).

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

Свойства золотого сечения

Для реализации алгоритма нам потребуется найти [math] a [/math] и [math] a + b [/math]. Если [math] L [/math] — длина исследуемого отрезка, тогда:

[math] \left(\dfrac{b + c}{a} = \varphi;\; b + c = L - a \right) \Rightarrow[/math]

[math] a = \dfrac{L}{\varphi + 1} [/math]

[math] a + b = L - c = L - a = L - \dfrac{L}{\varphi + 1}[/math]

Заметим, что в силу того, что [math]\varphi[/math] — золотое сечение, то [math]\dfrac{1}{\varphi + 1} = 2 - \varphi[/math].

Итоговый алгоритм выбора границ

Формально для поиска минимума (для максимума — делается аналогично) функции [math] f [/math] делаем следующее:

Шаг 1:

Определяем границы поиска [math]l[/math] и [math]r[/math], затем устанавливаем текущее разбиение:

[math]x_1 = l + \dfrac{r - l}{\varphi + 1}[/math]

[math]x_2 = r - \dfrac{r - l}{\varphi + 1}[/math]

и вычислим функцию на них: [math]f_1 = f(x_1), f_2 = f(x_2)[/math]

Шаг 2:

если [math]f_1 \lt f_2[/math], тогда

[math]r = x_2[/math]

[math]x_2 = x_1, f_2 = f_1[/math]

[math]x_1 = l + \dfrac{r - l}{\varphi + 1},\; f_1 = f(x_1)[/math]

иначе:

[math]l = x_1[/math]

[math]x_1 = x_2, f_1 = f_2[/math]

[math]x_2 = r - \dfrac{r - l}{\varphi + 1},\; f_2 = f(x_2)[/math]

Шаг 3:

если точность [math]|r - l| \lt \varepsilon[/math] нас устраивает, тогда останавливаемся, и искомая точка [math]x = \dfrac{l + r}{2}[/math], иначе назад к шагу 2

Псевдокод

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

Ошибки псевдокода

1. Используются вычислительно-неустойчивые формулы. 2. Учитывается только абсолютная длина отрезка. Подробнее: http://mech.math.msu.su/~iliagri/zip/sem2book.pdf

Время работы

Так как на каждой итерации мы считаем одно значение функции и уменьшаем область поиска в [math] \varphi [/math] раз, пока [math] r - l \gt \varepsilon[/math], то время работы алгоритма составит [math] \log_{\varphi}\left(\dfrac{r - l}{\varepsilon}\right)[/math].

Если удельный вес вычисления функции [math] f [/math] достаточно большой, тогда получим ускорение работы по сравнению с неулучшенным троичным поиском ([math] \log_{\varphi}\left(\dfrac{r - l}{\varepsilon}\right)[/math] против [math]2 \log_{\frac32} \left(\dfrac{r - l}{\varepsilon}\right)[/math].

За счет этого достигается выигрыш в производительности, т.к. каждый новый отрезок в [math]\approx 1.618 [/math] раз короче предыдущего (против [math]1.5[/math] у троичного поиска) и сходится он в [math]\log_{\frac32} \left(\dfrac{1 + \sqrt{5}}{2}\right) \approx 1.1868 [/math] быстрее, чем в троичном поиске, соответственно, в [math] \approx 2.3736 [/math] раза меньше вычислений.

См также

• Троичный поиск
• Целочисленный двоичный поиск

Источники информации

• Википедия — Метод золотого сечения
• Wikipedia — Golden section search