Математика / Начала анализа

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

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

Опубликовано: 22 октября 2026 г.Обновлено: 22 октября 2026 г.

Оптимизация и исследование операций Численные методы Математический анализ Страницы с задачами и решениями Есть историческая справка

Формула

\tau=\frac{\sqrt5-1}{2},\quad u=a+(1-\tau)(b-a),\quad v=a+\tau(b-a),\quad L_n=\tau^nL_0

Схема Первое сокращение золотым сечением

Интервал хранит минимум; τ задаёт отношение новой длины к старой.

Обозначения

$a,b$: границы текущего интервала, единица аргумента
$u,v$: внутренние пробные точки, единица аргумента
$τ$: коэффициент сокращения длины, безразмерно
$L_n$: длина интервала после n сокращений, единица аргумента
$f$: минимизируемая функция, единица целевой величины

Условия применения

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

Ограничения

Для нескольких локальных минимумов одно сравнение может удалить глобально лучшую область. Шум способен изменить порядок значений и разрушить гарантию. Метод оценивает положение точки через длину интервала; малая длина сама по себе не даёт заданной точности значения функции без дополнительных свойств.

Подробное объяснение

Пусть u < v. Если f(u) > f(v), минимум не может лежать левее u: там унимодальная функция ещё должна убывать к своей нижней точке. Остаётся [u,b]. При f(u) < f(v) сохраняют [a,v]. При точном равенстве можно оставить [u,v], но стандартное правило с одной из внешних частей также безопасно при строгой унимодальности.

Положение пробных точек выбирают симметрично. После отбрасывания левой части прежняя правая точка должна совпасть с одной из новых внутренних точек. Из этого требования получается τ² = 1−τ. Положительный корень равен примерно 0,618034. Благодаря ему после первого шага нужен лишь один новый вызов функции.

Если всегда оставлять стандартный интервал длиной τL, после n сокращений длина будет τⁿL₀. Середина такого интервала отличается от содержащегося в нём минимума не более чем на L/2. Это честная оценка ошибки аргумента, которая не требует знания производной.

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

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

Как пользоваться формулой

Зафиксируйте интервал [a,b] и обоснуйте единственный минимум на нём; запишите требуемую точность именно аргумента.
Вычислите две внутренние точки с коэффициентом τ и сравните значения функции, сохраняя пары точка–значение.
Если левое значение больше, замените a на u; иначе замените b на v и перенесите сохранённую внутреннюю точку.
Продолжайте до длины не более удвоенного допуска; верните середину и половину длины как границу ошибки.

Историческая справка

В вычислительной математике XX века поиск экстремума стал самостоятельной задачей: значение функции могло требовать эксперимента или длительного расчёта, а производная оставалась недоступной. Поэтому сравнивали стратегии размещения пробных точек и количество новых наблюдений. В современной университетской традиции золотое сечение разбирается как метод сокращения интервала, сохраняющий одно из прежних значений. Учебник CS 357 Иллинойсского университета выводит коэффициент из равенства τ² = 1−τ и сопоставляет метод с бисекцией. Название относится к пропорции отрезков, а не к историческому авторству самого золотого отношения. Здесь используется учебная форма алгоритма; отдельное утверждение о единственном изобретателе не требуется.

Историческая линия формулы

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

Пример

Найдём минимум f(x) = (x−1)² на [0,3]. Все величины безразмерны. При τ ≈ 0,618034 получаем u ≈ 1,145898 и v ≈ 1,854102. Значения равны примерно 0,021286 и 0,729490. Левое меньше, поэтому оставляем [0;1,854102]. Его длина равна 3τ, и точный минимум x = 1 действительно внутри. Прежняя точка u становится правой внутренней точкой следующего шага; заново нужно вычислить только левую. После десяти стандартных сокращений длина будет 3τ¹⁰ ≈ 0,024392, поэтому середина гарантированно отличается от минимума не более чем на 0,012196. Эта оценка относится к x; для данного квадрата ошибка значения равна квадрату ошибки аргумента.

Частая ошибка

Не применяйте правило знаков из метода бисекции: здесь нужна пара высот. Не округляйте внутренние точки до целых до сравнения. Не считайте τ числом 1,618: это обратное отношение. Не обещайте глобальный минимум у многомодальной функции и не путайте длину интервала с ошибкой его середины.

Практика

Задачи с решением

Число сокращений

Условие. Начальная длина равна 1. Сколько стандартных сокращений нужно для длины не более 0,1?

Решение. τ⁴ ≈ 0,145898 > 0,1, а τ⁵ ≈ 0,090170 ≤ 0,1. Следовательно, минимальное число сокращений равно пяти.

Ответ. 5 сокращений.

Ошибка середины

Условие. Итоговый интервал равен [2;2,06] и содержит минимум. Какую оценку имеет ошибка середины?

Решение. Середина равна 2,03. Любая точка интервала удалена от неё не более чем на (2,06−2)/2 = 0,03.

Ответ. Не более 0,03.

Дополнительные источники

https://cs357.cs.illinois.edu/textbook/notes/optimization.html
https://courses.grainger.illinois.edu/cs357/fa2019/references/ref-12-opt-nd/

Связанные формулы

Математика

Тернарный поиск минимума непрерывной унимодальной функции

$u=a+\frac{b-a}{3},\quad v=b-\frac{b-a}{3},\quad [a,b]\leftarrow\begin{cases}\left[u,b\right],&f(u)>f(v),\\\left[a,v\right],&f(u)\le f(v),\end{cases}\quad L_n=(2/3)^nL_0$

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

Математика

Параболическая интерполяция для поиска минимума функции

$A=\frac{(f_3-f_2)/(x_3-x_2)-(f_2-f_1)/(x_2-x_1)}{x_3-x_1},\quad B=\frac{f_2-f_1}{x_2-x_1}-A(x_1+x_2),\quad x_p=-\frac{B}{2A}$

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

Математика

Градиентный спуск с постоянным шагом: условие убывания

$x_{k+1}=x_k-\alpha\nabla f(x_k),\quad 0<\alpha<2/L,\quad f(x_{k+1})\le f(x_k)-\alpha(1-L\alpha/2)\|\nabla f(x_k)\|^2$

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

Математика

Правило Армихо: обратный поиск длины шага спуска

$f(x+\alpha p)\le f(x)+c\alpha\nabla f(x)^Tp,\quad \nabla f(x)^Tp<0,\quad \alpha\leftarrow\beta\alpha,\quad 0<c<1,\ 0<\beta<1$

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