Метод золотого сечения. Симметричные методы
Материал из MachineLearning.
(→Анализ метода) |
(→Метод деления отрезка пополам) |
||
Строка 49: | Строка 49: | ||
5. пока <tex>\frac{b-a}{2} \geq \epsilon</tex>; | 5. пока <tex>\frac{b-a}{2} \geq \epsilon</tex>; | ||
- | 6. <tex> \ | + | 6. <tex> \tilde{x}^{\ast}=\frac{a+b}{2}</tex>. |
====Анализ метода==== | ====Анализ метода==== | ||
Строка 62: | Строка 62: | ||
Если мы останавливаемся на <tex>k</tex>-м шаге, то погрешность результата составит: <br /> | Если мы останавливаемся на <tex>k</tex>-м шаге, то погрешность результата составит: <br /> | ||
- | + | :<tex>|x^{\ast}-\tilde{x}^{\ast}| \quad < \quad \frac{1}{2}\Delta_k \quad = \quad \frac{a-b- \delta}{2^{k+1}}+ \frac{\delta}{2}</tex> | |
+ | |||
+ | Таким образом, чтобы погрешность вычисления была менее <tex>\epsilon</tex>, должна выполняться оценка на число шагов: | ||
+ | |||
+ | :<tex>k>\log_2 (\frac{b - a - \delta}{\epsilon - \frac{\delta}{2} }) - 1</tex> | ||
+ | |||
+ | На каждом шаге необходимо вычислить значение функции в 2х точках, соответственно, при <tex>k</tex> шагах вычисляется <tex>N=2k</tex> значений. | ||
+ | |||
+ | ''Недостаток'': | ||
+ | |||
+ | *Информация о значении функции в точках <tex>x_1</tex> и <tex>x_2</tex> используется только на одном шаге. | ||
====Рекомендации в выборе параметров==== | ====Рекомендации в выборе параметров==== | ||
Строка 69: | Строка 79: | ||
---- | ---- | ||
+ | |||
===Метод золотого сечения=== | ===Метод золотого сечения=== | ||
====Описание метода==== | ====Описание метода==== |
Версия 13:38, 19 ноября 2008
Содержание |
Постановка задачи
В данной статье рассмотрены некоторые методы поиска экстремума функции одного переменного.
Пусть дана функция , необходимо найти минимум этой функции на заданном отрезке
(задача максимума решается аналогично).
Предполагается, что производная функции либо не существует, либо сложно вычислима, что не позволяет свести задачу к поиску корней производной
.
Методы заключаются в построении последовательности отрезков , стаягивающихся к точке
.
Проанализируем симметричные методы поиска и оценим их эффективность и точность.
Требования к функции
Рассматривая все функции, пусть даже непрерывные, можно построить такой пример, что , хотя
.
Гарантировать применимость рассматриваемых методов можно только для унимодальных функций.
Определение : Функция называется унимодальной на отрезке
, если ∃! точка минимума
на этом отрезке такая, что для любых точек
этого отрезка
Другими словами унимодальная функция монотонна на обе стороны от точки минимума . Аналогично определяется унимодальная функция и для задачи на максимум. Унимодальные функции могут быть непрерывными, разрывными, дискретными...
Далее будем рассматривать только унимодальные функции. При этом предполагаем, что они определены в достаточном количестве точек.
Симетричные методы
В классе симметричных методов на каждом шаге выбирается две точки отрезка и
, симметрично расположенных относительно центра этого отрезка. Дальнейшие действия определяются свойством унимодальной функции:
Пусть функция унимодальна на отрезке
, а ее минимум достигается в точке
. Для любых точек
и
этого отрезка и таких, что
верно следующее:
- если
, то точка минимума
,
- если
, то точка минимума
.
Исходя из определения методов, видно, что всякий симметричный метод полностью определяется заданием отрезка и правилом выбора первой точки. Тогда другая точка
находится по правилу общему для всех симметричных методов:
.
Соответственно, методы различаются способом выбора симметричных точек и
.
Метод деления отрезка пополам
Описание метода
Параметры на входе: - достаточно малые положительные константы.
1. Повторять:
- 2.
;
- 3. Если
, то
;
- 4. Если
, то
;
5. пока ;
6. .
Анализ метода
Считаем, что один шаг - это один этап цикла (п. 2-4).
Изначальная длина отрезка составляет .
После первого шага: ,
После -го шага:
.
Если мы останавливаемся на -м шаге, то погрешность результата составит:
Таким образом, чтобы погрешность вычисления была менее , должна выполняться оценка на число шагов:
На каждом шаге необходимо вычислить значение функции в 2х точках, соответственно, при шагах вычисляется
значений.
Недостаток:
- Информация о значении функции в точках
и
используется только на одном шаге.
Рекомендации в выборе параметров
Метод золотого сечения
Описание метода
Анализ метода
Рекомендации в выборе параметров
Улучшение метода Золотого сечения
Описание метода
Анализ метода
Рекомендации в выборе параметров
Числовой пример
Заключение
Список литературы
- Карманов В.Г. Математическое программирование: Учебное пособие. - М.:ФИЗМАТЛИТ, 2004
- Горячев Л.В. Одномерная минимизация. Методические указания к самостоятельной работе студентов по курсу “Методы оптимизации” - кафедра процессов управления ДВГУ, 2003