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

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

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

Начнём с базовой конструкции. У нас есть отрезок \( [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 \).

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

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

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

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

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