Задачи оптимизации являются краеугольным камнем во многих областях науки и техники, от проектирования инженерных систем до анализа экономических моделей. Одной из фундаментальных и часто встречающихся подзадач является поиск экстремума (минимума или максимума) функции одной переменной на заданном отрезке. Когда аналитическое решение затруднено или невозможно, на помощь приходят численные методы, предоставляющие эффективные инструменты для нахождения приближенного решения с любой требуемой точностью. Данная работа посвящена исследованию и практическому применению одного из таких элегантных и надежных подходов — метода золотого сечения. Целью работы является всестороннее изучение метода для нахождения минимума функции. Для достижения этой цели поставлены следующие задачи: изучить теоретические основы метода, детально описать его пошаговый алгоритм, реализовать его программно и провести анализ полученных результатов.
Глава 1. Теоретические основы и математический аппарат метода
Эффективность метода золотого сечения напрямую связана с одним ключевым требованием к целевой функции — она должна быть унимодальной на исследуемом отрезке. Унимодальная функция — это функция, которая на заданном интервале имеет только один локальный экстремум (в нашем случае — минимум). Это свойство гарантирует, что, отбрасывая часть интервала, мы не рискуем потерять искомую точку минимума.
Название метода происходит от его математической основы — принципа золотого сечения. Золотое сечение — это такое деление отрезка на две неравные части, при котором отношение всего отрезка к большей части равно отношению большей части к меньшей. Эта пропорция, обозначаемая греческой буквой φ (фи), является иррациональным числом и приблизительно равна 1.618. В методе используется обратная величина 1/φ ≈ 0.618.
Суть метода, предложенного американским математиком Джеком Кифером в 1953 году, заключается в итеративном сужении интервала неопределенности. На каждом шаге интервал делится двумя внутренними точками в пропорциях золотого сечения. Сравнивая значения функции в этих точках, мы можем с уверенностью отбросить часть интервала, которая гарантированно не содержит минимума. Главное преимущество такого подхода по сравнению, например, с методом троичного поиска, заключается в его вычислительной эффективности. После первой итерации, где требуются два вычисления функции, на каждом последующем шаге требуется вычислить значение функции лишь в одной новой точке, так как вторая точка из предыдущей итерации переиспользуется благодаря свойствам золотой пропорции.
Глава 2. Пошаговый алгоритм поиска минимума функции
Для практического применения метода золотого сечения необходимо формализовать его логику в виде четкой последовательности действий. Алгоритм поиска минимума унимодальной функции f(x) выглядит следующим образом:
- Инициализация. Задаются границы начального интервала неопределенности
[a, b]и требуемая точность вычисленийε(например, 0.01). - Вычисление внутренних точек. Рассчитываются две внутренние точки
x1иx2по формулам, использующим константу золотого сечения (φ ≈ 1.618):
x1 = b — (b — a) / φ
x2 = a + (b — a) / φ - Первое вычисление функции. На первом шаге необходимо вычислить значения функции в обеих точках:
f(x1)иf(x2). - Итерационный цикл. Запускается основной цикл, который продолжается до тех пор, пока длина текущего интервала не станет меньше заданной точности:
while ((b - a) > ε). Внутри цикла выполняется сравнение значений функции:- Если f(x1) < f(x2), это означает, что минимум находится в левой части интервала. Поэтому правая граница сдвигается:
b = x2. - В противном случае (если f(x1) ≥ f(x2)), минимум локализован в правой части, и сдвигается левая граница:
a = x1.
- Если f(x1) < f(x2), это означает, что минимум находится в левой части интервала. Поэтому правая граница сдвигается:
- Оптимизация вычислений. После сужения интервала на следующей итерации не нужно заново считать обе точки. Одна из старых точек становится новой внутренней точкой, и требуется вычислить лишь одну новую точку. Например, если
b = x2, то старая точкаx1становится новой точкойx2для следующей итерации. - Завершение. Когда условие
(b - a) ≤ εвыполнено, цикл прекращается. Приближенным значением точки минимума считается середина финального, достаточно узкого интервала:(a + b) / 2.
Глава 3. Практический пример расчета вручную
Для наглядной демонстрации работы алгоритма найдем точку минимума для функции f(x) = x² + 2x на начальном интервале [-3, 5]. Зададим требуемую точность ε = 0.1.
Для расчетов нам понадобится константа золотого сечения φ ≈ 1.618.
| Итерация | Интервал [a, b] | x1 | x2 | f(x1) | f(x2) | Сравнение |
|---|---|---|---|---|---|---|
| 1 | [-3.0, 5.0] | 0.056 | 1.944 | 0.115 | 7.667 | f(x1) < f(x2) ⇒ b=x2 |
| 2 | [-3.0, 1.944] | -1.112 | 0.056 | -0.987 | 0.115 | f(x1) < f(x2) ⇒ b=x2 |
| 3 | [-3.0, 0.056] | -1.832 | -1.112 | -0.291 | -0.987 | f(x1) > f(x2) ⇒ a=x1 |
| 4 | [-1.832, 0.056] | -1.112 | -0.664 | -0.987 | -0.887 | f(x1) < f(x2) ⇒ b=x2 |
После нескольких итераций мы бы достигли интервала, длина которого меньше ε = 0.1. Аналитически известно, что минимум функции f(x) = x² + 2x находится в точке x = -1. Как видно из таблицы, интервал поиска последовательно сужается вокруг этого значения, что подтверждает корректность работы алгоритма.
Глава 4. Программная реализация метода на языке Python
Ручные расчеты полезны для понимания логики, но на практике задачи оптимизации решаются с помощью программ. Ниже представлена реализация функции поиска минимума методом золотого сечения на языке Python. Код снабжен комментариями для пояснения каждого шага.
import math
# Константа золотого сечения
GOLDEN_RATIO = (1 + math.sqrt(5)) / 2
def golden_section_search(f, a, b, epsilon=1e-5):
"""
Находит минимум унимодальной функции f на интервале [a, b]
с точностью epsilon методом золотого сечения.
"""
# 1. Инициализация внутренних точек
x1 = b - (b - a) / GOLDEN_RATIO
x2 = a + (b - a) / GOLDEN_RATIO
# 2. Первое вычисление значений функции
f1 = f(x1)
f2 = f(x2)
# 3. Основной итерационный цикл
while (b - a) > epsilon:
if f1 < f2:
# Сдвигаем правую границу
b = x2
# Переиспользуем старые точки для оптимизации
x2 = x1
f2 = f1
x1 = b - (b - a) / GOLDEN_RATIO
f1 = f(x1)
else:
# Сдвигаем левую границу
a = x1
# Переиспользуем старые точки для оптимизации
x1 = x2
f1 = f2
x2 = a + (b - a) / GOLDEN_RATIO
f2 = f(x2)
# 4. Возвращаем середину финального интервала
return (a + b) / 2
# Пример вызова для функции из предыдущей главы
def target_function(x):
return x**2 + 2*x
# Задаем начальные данные
a_start = -3
b_start = 5
tolerance = 0.0001
# Выполняем поиск
min_point = golden_section_search(target_function, a_start, b_start, tolerance)
print(f"Приближенная точка минимума: {min_point:.4f}")
print(f"Значение функции в этой точке: {target_function(min_point):.4f}")
Запуск этого кода для задачи из Главы 3 покажет результат, очень близкий к аналитическому решению x = -1, что демонстрирует практическую применимость и корректность программной реализации.
Глава 5. Анализ эффективности и области применения
Метод золотого сечения занимает важное место в арсенале средств численной оптимизации благодаря удачному балансу между простотой и эффективностью. Его ключевые преимущества и особенности можно оценить в сравнении с другими методами.
По сравнению с троичным поиском, метод золотого сечения выигрывает в производительности. Хотя оба метода имеют линейную скорость сходимости, троичный поиск требует на каждой итерации два новых вычисления функции, в то время как метод золотого сечения (после первого шага) — всего одно. Это делает его почти в два раза быстрее при работе с вычислительно "дорогими" функциями.
Близким по идее является метод чисел Фибоначчи. Он теоретически является самым оптимальным методом поиска среди всех, основанных на сравнении значений функции, но требует заранее заданного числа итераций. Метод золотого сечения можно рассматривать как его асимптотический случай, который не требует этого априорного знания, что делает его более гибким на практике.
Скорость сходимости метода является линейной, с постоянным коэффициентом сжатия интервала на каждой итерации, равным ~0.618. Это гарантирует стабильное и предсказуемое уменьшение интервала неопределенности.
Типичная область применения метода — это задачи одномерной оптимизации, где производная целевой функции либо неизвестна, либо ее вычисление является слишком сложной или затратной операцией.
Благодаря своей надежности и отсутствию требований к гладкости функции (кроме унимодальности), он широко используется как самостоятельный инструмент или как составная часть более сложных многомерных алгоритмов оптимизации.
В ходе данной работы был всесторонне исследован метод золотого сечения для решения задач одномерной оптимизации. Была изучена его теоретическая база, основанная на свойствах золотой пропорции и требовании унимодальности функции. На основе теории был описан и продемонстрирован на конкретном примере пошаговый алгоритм поиска минимума, а также разработана его программная реализация на языке Python. Главный вывод заключается в том, что метод золотого сечения является эффективным, надежным и простым в реализации инструментом. Его практическая ценность особенно высока в ситуациях, когда информация о производных функции отсутствует, что делает его одним из фундаментальных и простейших вычислительных методов решения задач оптимизации.
Список использованной литературы и Приложения
При оформлении курсовой или научной работы необходимо ссылаться на авторитетные источники. Ниже приведен примерный список литературы, который может быть использован для углубленного изучения темы.
- Акулич И. Л. Математическое программирование в примерах и задачах: Учеб. пособие. — М.: Высшая школа, 1986.
- Банди Б. Основы линейного программирования. — М.: Радио и связь, 1989.
- Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. — М.: Мир, 1985.
- Kiefer, J. (1953). Sequential Minimax Search for a Maximum. Proceedings of the American Mathematical Society, 4(3), 502–506.
Приложение А
Полный листинг кода программной реализации на языке Python.
import math
# Константа золотого сечения
GOLDEN_RATIO = (1 + math.sqrt(5)) / 2
def golden_section_search(f, a, b, epsilon=1e-5):
"""
Находит минимум унимодальной функции f на интервале [a, b]
с точностью epsilon методом золотого сечения.
"""
# 1. Инициализация внутренних точек
x1 = b - (b - a) / GOLDEN_RATIO
x2 = a + (b - a) / GOLDEN_RATIO
# 2. Первое вычисление значений функции
f1 = f(x1)
f2 = f(x2)
# 3. Основной итерационный цикл
while (b - a) > epsilon:
if f1 < f2:
# Сдвигаем правую границу
b = x2
# Переиспользуем старые точки для оптимизации
x2 = x1
f2 = f1
x1 = b - (b - a) / GOLDEN_RATIO
f1 = f(x1)
else:
# Сдвигаем левую границу
a = x1
# Переиспользуем старые точки для оптимизации
x1 = x2
f1 = f2
x2 = a + (b - a) / GOLDEN_RATIO
f2 = f(x2)
# 4. Возвращаем середину финального интервала
return (a + b) / 2
# Пример вызова для функции из предыдущей главы
def target_function(x):
return x**2 + 2*x
# Задаем начальные данные
a_start = -3
b_start = 5
tolerance = 0.0001
# Выполняем поиск
min_point = golden_section_search(target_function, a_start, b_start, tolerance)
print(f"Приближенная точка минимума: {min_point:.4f}")
print(f"Значение функции в этой точке: {target_function(min_point):.4f}")
Список литературы
- Джон Г.Мэтьюз, Куртис Д.Финк Численные методы. Использование MATLAB СПб: «Вильямс», 2001. 716 с.
- Васильков Ю.В., Василькова Н.Н. Компьютерные технологии вычислений в математическом моделировании: Учеб. пособие. М.: Финансы и статистика, 2004. 256 с.
- Воробьев Г.Н., Данилова А.Н. Практикум по численным методам. М.: Высшая школа, 2002. 840 с.
- Бахвалов Н.С. Численные методы. М.:БИНОМ, Лаборатория Базовых Знаний, 2004. 435 с.
- Крылов В.И., Бобков В.В., Монастырский П.И. Вычислительные методы. Т.1. М.: Наука, 1976. 304 с.