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