Метод золотого сечения. Симметричные методы
Материал из MachineLearning.
(→Анализ метода) |
(→Рекомендации в выборе параметров) |
||
Строка 154: | Строка 154: | ||
====Рекомендации в выборе параметров==== | ====Рекомендации в выборе параметров==== | ||
+ | Для сходимости процесса необходимо согласовывать точность <tex>\delta</tex> вычисления величины <tex>\lambda</tex> с заданной точностью <tex>\epsilon</tex> результата. | ||
+ | |||
+ | Из {{eqref|3}} получаем, что при | ||
+ | :<tex>\big(\frac{\sqrt{5}-1}{2}\big)^k\Delta_0 \leq \frac{\epsilon}{2}</tex> и <tex>|\delta| \leq \frac{\epsilon}{2F_k\Delta_0}</tex>, | ||
+ | будет выполняться <tex>\Delta_k(\tilde{\lambda}) \leq \epsilon</tex> | ||
Версия 19:19, 22 ноября 2008
Содержание |
Постановка задачи
В данной статье рассмотрены некоторые методы поиска экстремума функции одного переменного.
Пусть дана функция , необходимо найти минимум этой функции на заданном отрезке (задача максимума решается аналогично). Предполагается, что производная функции либо не существует, либо сложно вычислима, что не позволяет свести задачу к поиску корней производной .
Методы заключаются в построении последовательности отрезков , стаягивающихся к точке .
Проанализируем симметричные методы поиска и оценим их эффективность и точность.
Требования к функции
Рассматривая все функции, пусть даже непрерывные, можно построить такой пример, что , хотя .
Гарантировать применимость рассматриваемых методов можно только для унимодальных функций.
Определение : Функция называется унимодальной на отрезке , если ∃! точка минимума на этом отрезке такая, что для любых точек этого отрезка
Другими словами унимодальная функция монотонна на обе стороны от точки минимума . Аналогично определяется унимодальная функция и для задачи на максимум. Унимодальные функции могут быть непрерывными, разрывными, дискретными...
Далее будем рассматривать только унимодальные функции. При этом предполагаем, что они определены в достаточном количестве точек.
Симетричные методы
В классе симметричных методов на каждом шаге выбирается две точки отрезка и , симметрично расположенных относительно центра этого отрезка. Дальнейшие действия определяются свойством унимодальной функции:
Пусть функция унимодальна на отрезке , а ее минимум достигается в точке . Для любых точек и этого отрезка и таких, что верно следующее:
- если , то точка минимума ,
- если , то точка минимума .
Исходя из определения методов, видно, что всякий симметричный метод полностью определяется заданием отрезка и правилом выбора первой точки. Тогда другая точка находится по правилу общему для всех симметричных методов:
.
Соответственно, методы различаются способом выбора симметричных точек и .
Метод деления отрезка пополам
Описание метода
Параметры на входе: - достаточно малые положительные константы.
1. Повторять:
- 2. ;
- 3. Если , то ;
- 4. Если , то ;
5. пока ;
6. .
Анализ метода
Считаем, что один шаг - это один этап цикла (п. 2-4).
Изначальная длина отрезка составляет .
После первого шага: ,
После -го шага: .
Если мы останавливаемся на -м шаге, то погрешность результата составит:
Таким образом, чтобы погрешность вычисления была менее , должна выполняться оценка на число шагов:
На каждом шаге необходимо вычислить значение функции в 2х точках, соответственно, при шагах вычисляется значений.
Недостаток:
- Информация о значении функции в точках и используется только на одном шаге.
Рекомендации в выборе параметров
Метод золотого сечения
Определение:
Говорят, что точка осуществляет золотое сечение отрезка , если
В качестве и выберем точку золотого сечения отрезка и симметричную ей. Если , то при указанном выборе точек получаем, что - точка золотого сечения отрезка , а - точка золотого сечения отрезка . Таким образом, на каждом шаге, кроме первого, необходимо вычислять значение только в одной точке, вторая берется из предыдущего шага.
Описание метода
Параметр на входе: - достаточно малая положительная константа, погрешность метода.
1.
2. Повторять:
- 3. Если , то ;
- 4. Если , то ;
5. пока ;
6. .
Анализ метода
Считаем, что один шаг - это один этап цикла (п. 3-4), . Тогда, считая длину отрезка на каждом шаге , получаем:
- ;
- ;
- ;
Нетрудно проверить, что
- , где -числа Фибоначчи.
С другой стороны, выполняется равенство:
Чтобы погрешность вычисления была менее , должна по крайней мере выполняться оценка на число шагов:
Тогда значение будет вычисляться в точках.
Недостаток:
- Неустойчивость относительно ошибок округления: мы получаем приблизительные значения чисел и , дальнейшие вычисления только накапливают ошибки, что может привести к нарушению условия вложенности отрезков и расходимости процесса.
Пусть вычисляется с погрешностью
Тогда имеем:
Из (1):
- .
Подставляем (2):
- .
Известно, что последовательность сходится при , В то же время , поэтому .
При этом числа Фибоначчи растут со скоростью геометрической прогрессии, знаменателем которой является число . Вследствие этого при фиксированной точности "раскачка" процесса происходит довольно быстро.
Рекомендации в выборе параметров
Для сходимости процесса необходимо согласовывать точность вычисления величины с заданной точностью результата.
Из (3) получаем, что при
- и ,
будет выполняться
Улучшение метода Золотого сечения
Описание метода
Анализ метода
Рекомендации в выборе параметров
Числовой пример
Заключение
Список литературы
- Карманов В.Г. Математическое программирование: Учебное пособие. - М.:ФИЗМАТЛИТ, 2004
- Горячев Л.В. Одномерная минимизация. Методические указания к самостоятельной работе студентов по курсу “Методы оптимизации” - кафедра процессов управления ДВГУ, 2003