Введение

Техника поиска экстремума функции

Поиск золотого сечения — это техника для нахождения экстремума (минимума или максимума) функции на заданном интервале. Для строго унимодальной функции с экстремумом внутри интервала, он будет найден, а для интервала, содержащего несколько экстремумов (включая, возможно, границы интервала), алгоритм сойдется к одному из них. Если единственный экстремум на интервале находится на его границе, алгоритм сойдется к этой граничной точке. Метод работает путем последовательного сужения диапазона значений на заданном интервале, что делает его относительно медленным, но очень устойчивым. Название техника получила благодаря тому, что алгоритм поддерживает значения функции в четырех точках, ширины интервалов между которыми соотносятся как φ:1:φ, где φ — золотое сечение. Эти соотношения поддерживаются на каждой итерации и обеспечивают максимальную эффективность. За исключением граничных точек, при поиске минимума центральная точка всегда меньше или равна крайним точкам, что гарантирует нахождение минимума между крайними точками. Обратное верно при поиске максимума. Алгоритм является пределом метода Фибоначчи (описанного ниже) при большом количестве вычислений значений функции. Метод Фибоначчи и поиск золотого сечения были открыты Кифером (1953) (см. также Авриэль и Уайльд, 1966).

Основная идея

Дискуссия здесь представлена в терминах поиска минимума (поиск максимума аналогичен) унимодальной функции. В отличие от поиска нуля, где для заключения корня достаточно двух вычислений функции с противоположными знаками, при поиске минимума необходимо три значения. Метод золотого сечения – эффективный способ последовательного сужения интервала, содержащего минимум. Ключевым моментом является наблюдение, что независимо от количества уже выполненных вычислений, минимум находится в интервале, определяемом двумя точками, соседними с точкой, имеющей наименьшее из вычисленных значений. Диаграмма выше иллюстрирует один шаг в технике поиска минимума. Значения функции отложены по вертикальной оси, а параметр x – по горизонтальной. Значение уже вычислено в трех точках: , , и Поскольку меньше, чем либо или , очевидно, что минимум лежит внутри интервала от до Следующий шаг в процессе минимизации – "проверить" функцию, вычислив её в новой точке x, а именно. Наиболее эффективно выбирать где-то внутри наибольшего интервала, то есть между и Из диаграммы видно, что если функция возвращает , то минимум лежит между и , и новая тройка точек будет , , и Однако, если функция возвращает значение , то минимум лежит между и , и новая тройка точек будет , , и Таким образом, в любом случае мы можем построить новый, более узкий интервал поиска, который гарантированно содержит минимум функции.

Условие прекращения

В зависимости от применения может быть использовано любое количество условий завершения. Интервал ΔX = X4 − X1 является мерой абсолютной погрешности при оценке минимума X и может быть использован для завершения алгоритма. Значение ΔX уменьшается в r = φ − 1 раз на каждой итерации, поэтому число итераций, необходимых для достижения абсолютной погрешности ΔX, составляет примерно ln(ΔX/ΔX0) / ln(r), где ΔX0 – начальное значение ΔX. Поскольку гладкие функции близки к горизонтальным (их первая производная близка к нулю) в окрестности минимума, необходимо учитывать, что не следует ожидать слишком высокой точности при определении минимума. Условие завершения, представленное в книге Numerical Recipes in C, основано на проверке разностей между , , и , при этом алгоритм завершается, когда значения находятся в пределах границ относительной точности:

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

Алгоритм

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

Поиск Фибоначчи

Очень похожий алгоритм также может быть использован для нахождения экстремума (минимума или максимума) последовательности значений, имеющей единственный локальный минимум или локальный максимум. Чтобы аппроксимировать позиции проб при поиске золотым сечением, исследуя только целочисленные индексы последовательности, вариант алгоритма для этого случая обычно поддерживает интервал, содержащий решение, длина которого является числом Фибоначчи. По этой причине вариант поиска золотым сечением для последовательностей часто называют поиском Фибоначчи. Поиск Фибоначчи был впервые предложен Кифером (1953) как minimax-поиск максимума (минимума) унимодальной функции на интервале.

Метод бисекции

Метод бисекции — аналогичный алгоритм для нахождения корня функции. Следует отметить, что для заключения корня в интервал достаточно двух точек, а не трех. Соотношение сторон интервала уменьшается в 2 раза на каждом шаге, а не на золотое сечение.