Метод Золотого Сечения: Как Найти Минимум

Минимизация функции одной переменной — это задача, в которой на отрезке нужно найти такую точку, где значение функции будет наименьшим. Звучит просто, но как сделать это быстро и без лишних вычислений? Именно здесь хорошо работает метод золотого сечения. Он позволяет последовательно сужать промежуток поиска и не действовать наугад. В этой статье разберём, откуда берутся ключевые числа метода и как работает сам алгоритм на отрезке.

Метод Золотого Сечения: Пропорция Деления Отрезка

Начнём с базовой конструкции. У нас есть отрезок \( [a,b] \), и мы хотим разделить его точкой так, чтобы части были неравными, но само деление обладало особым свойством. Пусть \( c\in(a,b) \). Тогда «золотым» называют такое деление, при котором отношение всего отрезка к большей части равно отношению большей части к меньшей:

\[
\frac{b-a}{b-c}=\frac{b-c}{c-a}=r.
\]

Здесь \( r \) — постоянный коэффициент, который задаёт пропорцию деления. Теперь сделаем важный шаг: выразим \( r \) из этого условия.

Обозначим длины частей:

\[
L=b-a,\qquad x=b-c,\qquad L-x=c-a.
\]

Тогда из условия золотого сечения получаем:

\[
\frac{L}{x}=\frac{x}{L-x}.
\]

Перемножим крест-накрест:

\[
L \cdot (L-x)=x^2.
\]

Раскроем скобки:

\[
L^2-L \cdot x=x^2.
\]

Перенесём всё в одну сторону:

\[
x^2+L \cdot x-L^2=0.
\]

Это квадратное уравнение относительно \( x \). Решим его:

\[
x=\frac{-L+\sqrt{L^2+4 \cdot L^2}}{2}=\frac{-L+\sqrt{5} \cdot L}{2}=L\cdot\frac{\sqrt{5}-1}{2}.
\]

Следовательно, отношение \( \frac{x}{L} \) равно:

\[
\frac{x}{L}=\frac{\sqrt{5}-1}{2}.
\]

А коэффициент \( r \) равен:

\[
r=\frac{L}{x}=\frac{1}{\frac{\sqrt{5}-1}{2}}=\frac{2}{\sqrt{5}-1}=\frac{\sqrt{5}+1}{2}.
\]

То есть

\[
r=\frac{1+\sqrt{5}}{2}\approx 1.618.
\]

Именно это число и определяет, как мы будем выбирать точки в алгоритме минимизации. Удобно, правда?

Запуск Алгоритма: Выбор Двух Точек и Первое Сравнение

Хорошо, теперь переходим к минимизации \( f(x) \) на отрезке \( [a,b] \). Нам нужны две внутренние точки, чтобы сравнить значения функции и отбросить часть отрезка. Обозначим их \( c \) и \( d \), где \( a<c<d<b \).

В методе золотого сечения точки выбирают так, чтобы они делили отрезок в «золотой» пропорции. Удобнее всего записать это через \( r \):

\[
d=a+\frac{1}{r} \cdot (b-a),
\qquad
c=b-\frac{1}{r} \cdot (b-a).
\]

Здесь важно понимать: точки симметричны относительно середины по долям длин, а не по расстояниям. Хотите увидеть ту же запись без \( r \)? Тогда просто подставим \( \frac{1}{r}=\frac{\sqrt{5}-1}{2} \):

\[
d=a+\frac{\sqrt{5}-1}{2} \cdot (b-a),
\qquad
c=b-\frac{\sqrt{5}-1}{2} \cdot (b-a).
\]

Дальше делаем именно то, что и определяет метод: вычисляем и сравниваем \( f(c) \) и \( f(d) \). И тут возникает главный вопрос: какую часть отрезка можно уверенно отбросить?

Если \( f(c)>f(d) \), то минимум не лежит в \( [a,c] \). Тогда оставляем \( [a_1,b_1]=[c,b] \).
Если \( f(d)>f(c) \), то минимум не лежит в \( [d,b] \). Тогда оставляем \( [a_1,b_1]=[a,d] \).

Почему это работает? Потому что метод применяют к унимодальной функции на \( [a,b] \): у неё есть только один минимум на этом отрезке. Значит, сравнение значений в двух точках показывает, в какой стороне находится минимум. Логика очень практичная: сравнили — отбросили — сузили.

Метод Золотого Сечения: Уменьшение Интервала, Критерий Остановки и Приближённый Ответ

Теперь самое приятное: после первого шага интервал становится короче с постоянным коэффициентом уменьшения. Посмотрим это прямо из формул.

Начальная длина:

\[
L_0=b-a.
\]

После отбрасывания части отрезка остаётся отрезок длины

\[
L_1=b_1-a_1=\frac{1}{r} \cdot (b-a)=\frac{L_0}{r}.
\]

Значит, на каждом шаге, если всё делать по правилам, длина «интервала неопределённости» умножается на \( \frac{1}{r} \). Тогда после \( n \) шагов:

\[
L_n=b_n-a_n=\frac{b-a}{r^n}.
\]

Это уже готовая оценка скорости сужения. И здесь естественно возникает практический вопрос: когда нужно остановиться?

Обычно задают точность \( \varepsilon>0 \) и останавливают процесс, когда

\[
b_n-a_n<\varepsilon.
\]

Тогда из формулы для \( L_n \) получаем условие на число шагов:

\[
\frac{b-a}{r^n}<\varepsilon \quad\Longrightarrow\quad r^n>\frac{b-a}{\varepsilon}.
\]

Логарифмируем это выражение. Основание можно взять любое, но удобно использовать натуральный логарифм:

\[
n>\frac{\ln\left(\frac{b-a}{\varepsilon}\right)}{\ln(r)}.
\]

То есть число итераций можно оценить заранее — нужно взять наименьшее целое \( n \), которое удовлетворяет этому неравенству. Это очень удобно, потому что вы сразу понимаете, сколько раз придётся вычислять \( f(x) \).

И ещё один важный момент. Начиная со второго шага, обычно не нужно заново считать оба значения. Одна из точек переходит в новый интервал, и её значение уже известно. Значит, на каждом следующем шаге часто требуется только одно новое вычисление \( f(x) \). Именно поэтому этот подход так популярен в численных методах.

А как получить ответ в виде конкретной точки?

После остановки у нас есть маленький интервал \( [a_n,b_n] \), внутри которого находится минимум. Тогда в качестве простого приближения часто берут:

\[
x^*\approx \frac{a_n+b_n}{2},
\]

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

Практика Метода: Пошаговые Вычисления

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

Пример 1. Найти минимум функции \( f(x)=(x-2)^2+1 \) на отрезке \( [a,b]=[1,3] \) с точностью \( \varepsilon=0.1 \), используя метод золотого сечения

Рассмотрим функцию \( f(x)=(x-2)^2+1 \) на отрезке \( [1,3] \). На этом отрезке она унимодальна, потому что имеет только один минимум вблизи \( x=2 \). Это означает, что сравнение \( f(c) \) и \( f(d) \) позволяет безопасно отбрасывать часть интервала.

Берём

\[
r=\frac{1+\sqrt{5}}{2}\approx 1.618,
\qquad
\frac{1}{r}\approx 0.618.
\]

Начинаем с \( [a_0,b_0]=[1,3] \). Строим две точки:

\[
\begin{gathered}
d_0=a_0+\frac{1}{r}(b_0-a_0)=1+0.618\cdot 2=2.236,
\\[6pt]
c_0=b_0-\frac{1}{r}(b_0-a_0)=3-0.618\cdot 2=1.764.
\end{gathered}
\]

Вычисляем:

\[
\begin{gathered}
f(c_0)=(1.764-2)^2+1=1.056,
\\[6pt]
f(d_0)=(2.236-2)^2+1=1.056.
\end{gathered}
\]

Получаем равенство \( f(c_0)=f(d_0) \), поэтому интервал можно сузить любым из двух симметричных способов. Для определённости оставим

\[
[a_1,b_1]=[1,2.236].
\]

Теперь важная деталь. Точка \( c_0=1.764 \) принадлежит новому интервалу \( [a_1,b_1] \), поэтому её можно использовать как рабочую точку следующего шага без повторного вычисления. То есть

\[
d_1=c_0=1.764,
\qquad
f(d_1)=f(c_0)=1.056.
\]

Вторую точку находим по формуле:

\[
c_1=b_1-\frac{1}{r}(b_1-a_1)=2.236-0.618\cdot 1.236=1.472,
\]

и вычисляем новое значение:

\[
f(c_1)=(1.472-2)^2+1=1.279.
\]

Так как \( f(c_1)>f(d_1) \), минимум находится правее, поэтому

\[
[a_2,b_2]=[c_1,b_1]=[1.472,2.236].
\]

Далее переносим точку, значение которой уже известно. В новом интервале остаётся \( d_1=1.764 \), поэтому

\[
c_2=d_1=1.764,
\qquad
f(c_2)=f(d_1)=1.056.
\]

Теперь определяем другую точку:

\[
d_2=a_2+\frac{1}{r}(b_2-a_2)=1.472+0.618\cdot 0.764=1.944,
\]

и вычисляем:
\[
f(d_2)=(1.944-2)^2+1=1.003.
\]

Так как \( f(c_2)>f(d_2) \), оставляем

\[
[a_3,b_3]=[c_2,b_2]=[1.764,2.236].
\]

Теперь в этом интервале остаётся точка \( d_2=1.944 \), поэтому

\[
c_3=d_2=1.944,
\qquad
f(c_3)=f(d_2)=1.003.
\]

Другую точку вычисляем:

\[
d_3=a_3+\frac{1}{r}(b_3-a_3)=1.764+0.618\cdot 0.472=2.056,
\]

а затем:

\[
f(d_3)=(2.056-2)^2+1=1.003.
\]

Получаем равенство \( f(c_3)=f(d_3) \), поэтому для определённости возьмём следующий интервал:

\[
[a_4,b_4]=[1.764,2.056].
\]

В этом интервале остаётся точка \( c_3=1.944 \), поэтому

\[
d_4=c_3=1.944,
\qquad
f(d_4)=f(c_3)=1.003,
\]

а другую точку находим так:

\[
c_4=b_4-\frac{1}{r}(b_4-a_4)=2.056-0.618\cdot 0.292=1.876,
\]

и вычисляем:

\[
f(c_4)=(1.876-2)^2+1=1.015.
\]

Так как \( f(c_4)>f(d_4) \), берём

\[
[a_5,b_5]=[c_4,b_4]=[1.876,2.056].
\]

Далее остаётся точка \( d_4=1.944 \), поэтому

\[
c_5=d_4=1.944,
\qquad
f(c_5)=f(d_4)=1.003.
\]

Другую точку определяем так:

\[
d_5=a_5+\frac{1}{r}(b_5-a_5)=1.876+0.618\cdot 0.180=1.987,
\]

и вычисляем:

\[
f(d_5)=(1.987-2)^2+1=1.
\]

Так как \( f(c_5)>f(d_5) \), получаем

\[
[a_6,b_6]=[c_5,b_5]=[1.944,2.056].
\]

Теперь

\[
b_6-a_6=2.056-1.944=0.112,
\]

поэтому делаем ещё один шаг. Точка \( d_5=1.987 \) остаётся в интервале, следовательно,

\[
c_6=d_5=1.987,
\qquad
f(c_6)=f(d_5)=1.
\]

Другую точку вычисляем:

\[
d_6=a_6+\frac{1}{r}(b_6-a_6)=1.944+0.618\cdot 0.112=2.013,
\]

а затем:

\[
f(d_6)=(2.013-2)^2+1=1.
\]

При равенстве интервал можно сузить в любую сторону. Для определённости возьмём

\[
[a_7,b_7]=[1.944,2.013],
\qquad
b_7-a_7=0.069<0.1.
\]

Значит, условие точности выполнено. В качестве стандартного приближения точки минимума берём середину:

\[
x^*\approx \frac{a_7+b_7}{2}=\frac{1.944+2.013}{2}=1.979.
\]

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

\[
x^*\approx 1.987,
\qquad
f(x^*)\approx 1.
\]

Это согласуется с тем, что минимум этой функции достигается при \( x=2 \) и равен \( f_{\min}=1 \). То есть метод дал близкий ответ благодаря последовательному и контролируемому сужению отрезка.

Пример 2. Определить количество итераций, необходимых для нахождения минимума функции \( f(x)=(x-2)^2+1 \) на отрезке \( [a,b]=[1,3] \) с точностью \( \varepsilon=0.1 \), используя метод золотого сечения

Теперь проверим, согласуется ли число шагов с тем, что мы получили в предыдущем примере. Используем оценку

\[
n>\frac{\ln\left(\frac{b-a}{\varepsilon}\right)}{\ln(r)},
\qquad
r=\frac{1+\sqrt{5}}{2}.
\]

Для \( [1,3] \) имеем \( b-a=2 \), поэтому

\[
\frac{b-a}{\varepsilon}=\frac{2}{0.1}=20,
\qquad
n>\frac{\ln(20)}{\ln(r)}.
\]

Берём \( r\approx 1.618 \). Тогда \( \ln(20)\approx 2.996 \), \( \ln(1.618)\approx 0.481 \), откуда

\[
n>\frac{2.996}{0.481}\approx 6.225.
\]

Следовательно, достаточно \( n=7 \) итераций. Это хорошо согласуется с практическим результатом: после седьмого шага мы получили интервал длины \( 0.069 \), который уже меньше, чем \( \varepsilon=0.1 \).

Куда Двигаться Дальше: Ещё Несколько Методов Минимизации

Мы разобрали метод золотого сечения и увидели, как он шаг за шагом сужает интервал. А что, если хочется иметь и другие варианты и понимать, в каком случае какой способ даёт лучший результат? Вот темы, которые логично продолжают эту статью.

Метод Фибоначчи: Точный план шагов — Поговорим о том, как числа Фибоначчи задают последовательность проверок и помогают заранее спланировать поиск минимума.
Метод дихотомии: Простое деление интервала — Разберём идею проверки двух точек, расположенных близко к середине, и покажем, как быстро сузить область поиска.
Равномерный поиск: Стартовое приближение — Объясним, как пройти интервал равными шагами, найти лучший промежуток и подготовить основу для более точных методов.

Метод Золотого Сечения в Коде: Напишите Свой Поиск Минимума

А теперь представьте, что блок-схема ниже — это не просто картинка, а готовый план для вашего небольшого учебного задания. Почему бы не взять её как подсказку и не написать на любимом языке программирования компактную программу, которая находит минимальное значение унимодальной функции методом золотого сечения? Такой проект хорошо показывает, как теория быстро превращается в практический инструмент, который можно запускать снова и снова для разных функций. А ещё это отличный способ проверить себя: одинаково ли уверенно вы понимаете метод и на бумаге, и в коде?

Метод Золотого Сечения: Минимизация Функции Одной Переменной