Метод золотого сечения

Поиск экстремума. Вводные замечания.

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

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

Метод золотого сечения - student2.ru (13.1)

и точку Метод золотого сечения - student2.ru , в которой он достигается.

Заметим, что поиск максимума функции Метод золотого сечения - student2.ru эквивалентен поиску минимума функции Метод золотого сечения - student2.ru . Поэтому далее будем рассматривать задачу минимизации.

Множество Метод золотого сечения - student2.ru выражает ограничения задачи. Например, во многих физических задачах, требуется, чтобы переменные были неотрицательны: Метод золотого сечения - student2.ru . Если Метод золотого сечения - student2.ru совпадает с Метод золотого сечения - student2.ru , то говорят о задаче безусловной оптимизации, в противном случае говорят об условной оптимизации.

Будем говорить, что Метод золотого сечения - student2.ru имеет в точке Метод золотого сечения - student2.ru глобальный минимум, если Метод золотого сечения - student2.ru для любого Метод золотого сечения - student2.ru . Аналогично, Метод золотого сечения - student2.ru имеет в точке Метод золотого сечения - student2.ru локальный минимум, если Метод золотого сечения - student2.ru для любого Метод золотого сечения - student2.ru , где Метод золотого сечения - student2.ru – окрестность точки Метод золотого сечения - student2.ru .

Если локальный минимум (экстремум) достигается во внутренней точке Метод золотого сечения - student2.ru области Метод золотого сечения - student2.ru и функция Метод золотого сечения - student2.ru дифференцируема в этой точке, то Метод золотого сечения - student2.ru является критической точкой, т.е. выполняются условия:

Метод золотого сечения - student2.ru (13.2)

Обратное, вообще говоря, неверно: критическая точка может не быть экстремумом (например, точка перегиба).

Мы ограничимся поиском локальных минимумов в задаче безусловной оптимизации. Отметим, что таких минимумов (как и максимумов) на заданном интервале может быть несколько, поэтому нам необходимо локализовать экстремум, т.е. определять отрезок с единственной экстремальной точкой функции Метод золотого сечения - student2.ru .

13.1. Одномерная оптимизация.

Метод Ньютона

В основе метода Ньютона лежит приближение функции Метод золотого сечения - student2.ru в окрестности экстремума квадратичной функцией Метод золотого сечения - student2.ru . В свою очередь, экстремум квадратичной функции Метод золотого сечения - student2.ru находится явно ( Метод золотого сечения - student2.ru - абсцисса экстремума) и используется в качестве следующего начального приближения.

Пусть некоторая точка Метод золотого сечения - student2.ru – приближение абсциссы экстремума. Запишем разложение функции Метод золотого сечения - student2.ru в ряд Тейлора в окрестности Метод золотого сечения - student2.ru (для квадратичной функции отличны от нуля только первые две производные):



Метод золотого сечения - student2.ru (13.3)

Правая часть выражения (13.3) представляет собой квадратичную функцию относительно Метод золотого сечения - student2.ru ( Метод золотого сечения - student2.ru ), экстремум которой достигается в точке

Метод золотого сечения - student2.ru (13.4)

Раскрывая Метод золотого сечения - student2.ru , в качестве следующего приближения можем взять

Метод золотого сечения - student2.ru

Получаем итерационный процесс:

Метод золотого сечения - student2.ru (13.5)

дающий алгоритм метода Ньютона.

Отметим, что при выборе начального приближения достаточно близко к точке экстремума метод Ньютона гарантированно сходится. Однако метод Ньютона может сходиться как к локальному минимуму, так и к локальному максимуму, поэтому в полученной точке экстремума Метод золотого сечения - student2.ru , если не использовать локализацию, требуется дополнительно вычислить Метод золотого сечения - student2.ru , причем, если Метод золотого сечения - student2.ru , то мы имеет дело с локальным минимумом, если же Метод золотого сечения - student2.ru – с локальным максимумом, если Метод золотого сечения - student2.ru – метод Ньютона завершится делением на 0.

Пример 1.Найти точку минимума функции Метод золотого сечения - student2.ru . Сделать три итерации.

Решение.Для применения формулы (13.5) вычислим производные: Метод золотого сечения - student2.ru , Метод золотого сечения - student2.ru . Подставляя в (13.5), получим: Метод золотого сечения - student2.ru . Выберем в качестве начального приближения Метод золотого сечения - student2.ru . Подставляя в расчётную формулу, последовательно найдём Метод золотого сечения - student2.ru . Точное значение Метод золотого сечения - student2.ru . Если в качестве начального приближения выбрать значение Метод золотого сечения - student2.ru , то остановится, не начавшись, т.к. в этом случае Метод золотого сечения - student2.ru равна нулю (значение Метод золотого сечения - student2.ru является точкой перегиба исходной функции).

Метод золотого сечения.

Метод золотого сечения – метод разбиения отрезка: отношение длины большей части к длине всего отрезка равно отношению длины меньшей части отрезка к длине его большей части, т.е. выполняется пропорция золотого сечения (рис. 2.).

Метод золотого сечения - student2.ru (13.6)

Метод золотого сечения - student2.ru

Рис. 2.

Разрешая пропорцию (13.6) относительно Метод золотого сечения - student2.ru и учитывая тот факт, что длина отрезка не может быть отрицательной, получаем

Метод золотого сечения - student2.ru

Число Метод золотого сечения - student2.ru называется золотым сечением и является фундаментальным числом, возникающим во многих областях науки и техники.

Наши рекомендации