Метод золотого сечения: поиск минимума функции

Метод золотого сечения - это способ численно найти минимум функции одной переменной на отрезке, когда производную считать неудобно или невозможно. Идея простая: мы не вычисляем градиент, а лишь сравниваем значения функции в двух пробных точках и за счёт этого отбрасываем часть отрезка, где минимума точно нет. Точки выбираются не случайно, а в пропорции золотого сечения - именно это позволяет на каждом шаге пересчитывать только одну новую точку и быстро ужимать интервал неопределённости. Ниже разберём, какие условия нужны функции, как вывести формулы пробных точек, почему интервал сужается ровно в $\rho \approx 0{,}618$ раз за шаг, сколько итераций требуется для заданной точности и где студенты чаще всего ошибаются. Чтобы сразу почувствовать механику, покрути калькулятор: он показывает параболу, обе пробные точки и отбрасываемую долю на каждом шаге.

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

Метод золотого сечения относится к методам одномерной оптимизации нулевого порядка: он использует только значения самой функции, без производных. Это его главное достоинство - функция может быть задана таблицей, результатом эксперимента или громоздкой формулой, для которой производную брать дорого.

Ключевое требование - унимодальность функции на рассматриваемом отрезке $[a, b]$. Функция $f(x)$ называется унимодальной, если на отрезке у неё ровно один минимум: слева от точки минимума она убывает, справа возрастает. Если внутри отрезка несколько локальных минимумов, метод честно сойдётся к одному из них, но не гарантирует, что найдёт глобальный. Поэтому перед запуском метода важно убедиться, что минимум на отрезке единственный, либо разбить область на участки унимодальности.

Метод золотого сечения часто сравнивают с похожими по идее способами сужения отрезка - например, с методом дихотомии (половинного деления) или методом Фибоначчи. Все они работают по одной логике: держать минимум внутри сужающегося интервала, но золотое сечение даёт удобный компромисс между скоростью и числом вычислений функции.

Формулы пробных точек

Пусть минимум унимодальной функции лежит на отрезке $[a, b]$. Возьмём внутри две пробные точки $x_1$ и $x_2$, расположенные симметрично относительно середины:

$x_1 = b - \rho\,(b - a), \qquad x_2 = a + \rho\,(b - a),$

где $\rho = \dfrac{1}{\varphi} = \dfrac{\sqrt{5} - 1}{2} \approx 0{,}618$ - величина, обратная золотому сечению $\varphi = \dfrac{1 + \sqrt{5}}{2}$. По построению $x_1 < x_2$, и эти точки делят отрезок в золотой пропорции: каждая из них отсекает от своего края долю $1 - \rho \approx 0{,}382$ длины интервала.

Рассчитать для своей задачи

Дальше сравниваем значения функции. Если $f(x_1) < f(x_2)$, то минимум лежит левее точки $x_2$ (правее неё функция уже растёт), и правую долю $[x_2, b]$ можно отбросить - новый отрезок становится $[a, x_2]$. Если же $f(x_1) \ge f(x_2)$, отбрасываем левую долю $[a, x_1]$ и переходим к отрезку $[x_1, b]$. В любом случае длина отрезка умножается на $\rho$, а минимум остаётся внутри.

Почему именно золотое сечение

Главная экономия метода спрятана в свойстве числа $\rho$. После того как мы отбросили одну долю, внутри нового отрезка одна из старых пробных точек уже стоит ровно там, где должна быть новая пробная точка золотого сечения. Это значит, что на каждом шаге, кроме первого, нужно вычислить функцию только в одной новой точке, а вторую взять из предыдущего шага.

Работает это благодаря определяющему уравнению золотого сечения $\rho^2 = 1 - \rho$, или, что то же самое, $\rho = \dfrac{1}{1 + \rho}$. Именно из этого соотношения следует, что точка, делящая большой отрезок в пропорции $\rho$, после сужения делит в той же пропорции и меньший отрезок. Никакая другая пропорция таким самоподобием не обладает, поэтому метод и берёт золотое сечение, а не, скажем, деление пополам.

Рассчитать для своей задачи

На схеме видно, как именно делится отрезок: точка $x_1$ отстоит от левого края на $1 - \rho$, а $x_2$ - на $1 - \rho$ от правого, поэтому большие доли $[a, x_2]$ и $[x_1, b]$ равны и составляют по $\rho \approx 0{,}618$ всей длины. Эта симметрия и обеспечивает переиспользование точки.

Сколько шагов до нужной точности

Поскольку за каждый шаг длина интервала умножается на $\rho$, после $n$ шагов она равна:

$L_n = (b - a)\,\rho^{\,n}.$

Чтобы зажать минимум в окно точности $\varepsilon$, нужно решить неравенство $(b - a)\,\rho^{\,n} \le \varepsilon$ относительно числа шагов:

$n \ge \frac{\ln\!\big(\varepsilon / (b - a)\big)}{\ln \rho}.$

Поскольку $\ln \rho < 0$, при делении знак неравенства переворачивается, а результат округляют вверх до целого. Например, для стартового отрезка длины $5$ и точности $\varepsilon = 0{,}01$ нужно $13$ шагов, а для $\varepsilon = 0{,}001$ - уже $18$. Сходимость линейная: каждый шаг убирает примерно $38\%$ оставшегося интервала. За окончательную оценку минимума обычно берут середину итогового отрезка $\dfrac{a + b}{2}$ - так максимальная ошибка не превышает половины ширины интервала.

Сравните это поведение в калькуляторе выше: увеличивайте число шагов и следите, как ширина интервала падает, а оценка минимума приближается к $x = 2$. По той же логике строится и метод касательных Ньютона для корня, только там используется производная, а здесь - лишь значения функции; разбор этой связки есть в статье про метод касательных Ньютона.

Алгоритм по шагам

Чтобы не путаться в индексах, метод удобно записать как короткую последовательность действий:

1. Задать отрезок $[a, b]$, на котором функция унимодальна, и требуемую точность $\varepsilon$.
2. Вычислить пробные точки $x_1 = b - \rho(b - a)$ и $x_2 = a + \rho(b - a)$ и значения $f(x_1)$, $f(x_2)$.
3. Если $f(x_1) < f(x_2)$, положить $b = x_2$, перенести старую $x_1$ в $x_2$ и вычислить только новую левую точку. Иначе положить $a = x_1$, перенести $x_2$ в $x_1$ и вычислить новую правую точку.
4. Повторять шаг 3, пока длина отрезка не станет меньше $\varepsilon$.
5. Вернуть середину итогового отрезка как приближение точки минимума.

За счёт переиспользования точки на каждой итерации после первой считается лишь одно новое значение функции - это и делает метод экономичным.

Частые ошибки

• Запуск на неунимодальной функции. Если на отрезке несколько минимумов, метод сойдётся к одному из них, и это может быть локальный, а не глобальный минимум. Сначала убедитесь, что минимум единственный.
• Перепутаны направления отбрасывания. При $f(x_1) < f(x_2)$ отбрасывают правую долю, а не левую. Ошибка в этом сравнении уводит интервал в сторону от минимума.
• Пересчёт обеих точек каждый шаг. Главное преимущество метода теряется, если на каждом шаге заново считать и $x_1$, и $x_2$. Одна точка всегда наследуется с предыдущего шага.
• Точность путают с числом шагов. Точность $\varepsilon$ - это ширина итогового интервала, а не значение функции в нём. Минимум функции при этом найден лишь приближённо, с погрешностью до $\varepsilon / 2$.
• Метод применяют к поиску корня. Золотое сечение ищет минимум функции, а не её ноль. Для корня берут другие методы - бисекцию или касательные.

FAQ

Чем метод золотого сечения лучше дихотомии? В методе дихотомии за шаг считают два новых значения функции около середины, а в золотом сечении - только одно (вторая точка наследуется). При сравнимом сужении интервала золотое сечение тратит примерно вдвое меньше вычислений функции, что важно, когда каждое вычисление дорогое.

Можно ли искать максимум этим методом? Да. Поиск максимума сводится к поиску минимума функции $-f(x)$: достаточно поменять знак сравнения значений. Логика сужения интервала остаётся той же.

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

Коротко

Метод золотого сечения находит минимум унимодальной функции на отрезке, сравнивая значения в двух пробных точках золотого сечения и отбрасывая долю, где минимума нет. За каждый шаг интервал сужается в $\rho \approx 0{,}618$ раз, а новая точка считается только одна - в этом и экономия. Число шагов до точности $\varepsilon$ задаёт формула $n \ge \ln(\varepsilon/(b-a)) / \ln \rho$, а ответом служит середина итогового отрезка.