Метод золотого сечения программирование

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

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

Алгоритм

Обоснование

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

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

Расстояние от [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 [/math] , то получится [math] \dfrac = \dfrac[/math] .

[math] \dfrac = \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>[/math] (тот корень уравнения, который меньше нуля, по понятным причинам отбросили).

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

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

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

[math] a + b = L — c = L — a = L — \dfrac[/math]

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

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

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

Шаг 1: Определяем границы поиска [math]l[/math] и [math]r[/math] , затем устанавливаем текущее разбиение: [math]x_1 = l + \dfrac[/math] [math]x_2 = r — \dfrac[/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,\; 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,\; f_2 = f(x_2)[/math] Шаг 3: если точность [math]|r — l| \lt \varepsilon[/math] нас устраивает, тогда останавливаемся, и искомая точка [math]x = \dfrac[/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_\left(\dfrac\right)[/math] .

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

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

См также

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

Источник

Программирование на C, C# и Java

Уроки программирования, алгоритмы, статьи, исходники, примеры программ и полезные советы

ОСТОРОЖНО МОШЕННИКИ! В последнее время в социальных сетях участились случаи предложения помощи в написании программ от лиц, прикрывающихся сайтом vscode.ru. Мы никогда не пишем первыми и не размещаем никакие материалы в посторонних группах ВК. Для связи с нами используйте исключительно эти контакты: vscoderu@yandex.ru, https://vk.com/vscode

Метод золотого сечения на Java

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

Метод золотого сечения — это итеративный метод поиска экстремумов (минимума или максимума) функции одной переменной на заданном отрезке [a; b]. Метод золотого сечения был продемонстрирован в 1953 году Джеком Кифером. В его основе лежит принцип деления отрезка в пропорции золотого сечения.

Теоретические сведения

Пусть задана функция f(x) и отрезок [a; b], на котором требуется найти экстремум. Рассматриваемый отрезок делится в оба направления точками x1 и x2 в отношении золотого сечения. То есть:

φ — это пропорция золотого сечения.

Следовательно координаты x1 и x2 находятся по формулам:

Таким образом точки x1 и x2 делят отрезки [a; x2] и [x1; b] соответственно в пропорции золотого сечения. Это свойство далее будет использоваться для построения итеративного процесса вычисления экстремума функции.

Описание алгоритма

1. Задаются начальные параметры: границы отрезка [a; b] и точность вычислений ε.
2. Рассчитываются координаты точек деления: . Затем вычисляется значение функции f(x) в этих точках: . ЕСЛИ (случай поиска минимума функции. Для поиска точки максимума изменить неравенство на ), ТО . ИНАЧЕ .
3. ЕСЛИ требуемая точность достигнута: , ТО и конец алгоритма. ИНАЧЕ возврат к шагу 2.

Реализация алгоритма

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

Класс GoldenSection, позволяющий выполнить поиск экстремума функции на отрезке [a; b] с точностью ε, содержит (по порядку): определение константы пропорции золотого сечения φ, метод, вычисляющий значение целевой функции f(x), метод, выполняющий поиск минимума функции и метод, выполняющий поиск максимума функции.

Источник