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

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

Метод золотого сечения — алгоритм одномерной минимизации, на каждом шаге сужающий интервал неопределённости в $\varphi\approx 1.618$ раза, требуя лишь одного нового вычисления функции на итерацию.

Идея

Держим отрезок $[a,b]$ с минимумом внутри. Поставим две внутренние точки $c<d$. Если $f(c)<f(d)$, минимум не может быть правее $d$ (функция унимодальна), значит отбрасываем $(d,b]$ и новый отрезок — $[a,d]$. Иначе отбрасываем $[a,c)$. Отрезок сжимается. Вопрос: где ставить $c,d$, чтобы при сжатии одну из старых точек можно было переиспользовать и не считать $f$ заново?

Магия числа $\varphi$

Ответ даёт золотое сечение $\varphi=\dfrac{1+\sqrt5}{2}\approx 1.618$. Если ставить точки на расстоянии $\rho=1/\varphi\approx 0.618$ от концов:

$$c=b-\rho(b-a),\qquad d=a+\rho(b-a),$$

то после отбрасывания одна из новых пробных точек уже совпадает со старой, и на каждой итерации нужно лишь одно новое вычисление $f$. Интервал стабильно умножается на $\rho\approx 0.618$, то есть за каждые $\sim 5$ итераций сокращается на порядок.

Реализация

import math

def phi_fun(x):
    return (x - 2) ** 2 + math.sin(3 * x)

def golden(f, a, b, tol=1e-5):
    invphi = (math.sqrt(5) - 1) / 2          # 1/φ ≈ 0.618
    c = b - invphi * (b - a)
    d = a + invphi * (b - a)
    fc, fd = f(c), f(d)
    step = 0
    while (b - a) > tol:
        step += 1
        if fc < fd:
            b, d, fd = d, c, fc
            c = b - invphi * (b - a)
            fc = f(c)
        else:
            a, c, fc = c, d, fd
            d = a + invphi * (b - a)
            fd = f(d)
        if step <= 5 or step % 5 == 0:
            print(f"шаг {step:2d}: интервал=[{a:.4f}, {b:.4f}] ширина={b-a:.5f}")
    return (a + b) / 2

x_star = golden(phi_fun, 0.0, 4.0)
print("Минимум x* ≈", round(x_star, 5))
print("f(x*)    ≈", round(phi_fun(x_star), 5))

Вывод:

шаг  1: интервал=[0.0000, 2.4721] ширина=2.47214
шаг  2: интервал=[0.9443, 2.4721] ширина=1.52786
шаг  3: интервал=[0.9443, 1.8885] ширина=0.94427
шаг  4: интервал=[1.3050, 1.8885] ширина=0.58359
шаг  5: интервал=[1.5279, 1.8885] ширина=0.36068
шаг 10: интервал=[1.6331, 1.6656] ширина=0.03252
шаг 15: интервал=[1.6485, 1.6514] ширина=0.00293
шаг 20: интервал=[1.6493, 1.6496] ширина=0.00026
шаг 25: интервал=[1.6494, 1.6494] ширина=0.00002
Минимум x* ≈ 1.64943
f(x*)    ≈ -0.8494

Заметьте: ширина интервала на каждом шаге множится примерно на $0.618$ — это и есть постоянная скорость золотого сечения. Найденный минимум $x^*\approx 1.649$ глубже ($f\approx-0.849$), чем грубая оценка перебора из прошлого урока ($x\approx1.6$, $f\approx-0.836$), потому что сетка была слишком редкой.

Сравнение с перебором

Метод	Вызовов $f$ для точности $10^{-5}$ на $[0,4]$
Равномерная сетка	$\sim 4\cdot 10^5$ точек
Золотое сечение	$\sim 27$ вызовов

Как работает под капотом

Скорость сходимости золотого сечения линейная: ошибка убывает как $\rho^k$ с $\rho\approx 0.618$. Это медленнее, чем у методов на основе производных (метод секущих, парабол), но зато золотое сечение надёжно работает без производных и не требует гладкости — только унимодальности. Поэтому его выбирают, когда функция «чёрный ящик»: задана кодом, шумна или негладка, а считать производные нельзя или дорого.

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

Пересчитывать обе точки каждый шаг. Весь смысл $\varphi$ — переиспользовать одну; иначе теряется половина выигрыша.
Применять к мультимодальной функции. Метод гарантирует минимум только при унимодальности на $[a,b]$.
Слишком грубый $tol$. Останавливаемся по ширине интервала, а не по значению $f$ — следите за нужной точностью аргумента.

Итоги

Золотое сечение сужает интервал в $\varphi\approx 1.618$ раз за шаг, делая лишь одно новое вычисление $f$.
Сходимость линейная ($\rho\approx 0.618$), без производных, требует унимодальности.
Идеален для негладких «чёрных ящиков»; на порядки экономнее перебора.