Метод золотого сечения. Симметричные методы

Материал из MachineLearning.

Версия от 13:43, 7 декабря 2008; Евгения Одинокова (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Содержание

1 Постановка задачи
2 Требования к функции
3 Симметричные методы
- 3.1 Метод деления отрезка пополам
  - 3.1.1 Описание метода
  - 3.1.2 Анализ метода
- 3.2 Метод золотого сечения
4 Числовой пример
5 Заключение
6 Список литературы
7 Внешние ссылки
8 См. также

Постановка задачи

В данной статье рассмотрены симметричные методы поиска экстремума функции одного переменного.

Пусть дана функция $y=f(x)$ , необходимо найти минимум этой функции на заданном отрезке $[a, \quad b]$ (задача максимума решается аналогично). Предполагается, что производная функции либо не существует, либо сложно вычислима, что не позволяет свести задачу к поиску корней производной $f'(x)=0$ .

Методы заключаются в построении последовательности отрезков $[a_n, \quad b_n]$ , стаягивающихся к точке $x^{\ast} = argmin \{ f(x):\: \quad x \quad \in \quad [a,\quad b] \}$ .

Проанализируем симметричные методы поиска и оценим их эффективность и точность.

Требования к функции

Рассматривая все функции, пусть даже непрерывные, можно построить такой пример, что $x^{\ast} \quad \notin \quad [a_n, \quad b_n]$ , хотя $x^{\ast} \quad \in \quad [a_0, \quad b_0]$ .

Гарантировать применимость рассматриваемых методов можно только для унимодальных функций.

Определение : Функция $f(x)$ называется унимодальной на отрезке $[a, \quad b]$ , если ∃! точка минимума $x^{\ast}$ на этом отрезке такая, что для любых точек $x_1, \quad x_2$ этого отрезка

$x^{\ast} \leq x_1 \leq x_2 \quad \Rightarrow \quad f(x^{\ast}) \leq f(x_1) \leq f(x_2)$ , $x^{\ast} \geq x1 \geq x_2 \quad \Rightarrow \quad f(x^{\ast}) \leq f(x1) \leq f(x2)$ .

Другими словами унимодальная функция монотонна на обе стороны от точки минимума $x^{\ast}$ . Аналогично определяется унимодальная функция и для задачи на максимум. Унимодальные функции могут быть непрерывными, разрывными, дискретными...

Далее будем рассматривать только унимодальные функции. При этом предполагаем, что они определены в достаточном количестве точек.

Симметричные методы

В классе симметричных методов на каждом шаге выбирается две точки отрезка $x_1$ и $x_2$ , симметрично расположенных относительно центра этого отрезка. Дальнейшие действия определяются свойством унимодальной функции:
Пусть функция $f(x)$ унимодальна на отрезке $[a, \quad b]$ , а ее минимум достигается в точке $x^{\ast}$ . Для любых точек $x_1$ и $x_2$ этого отрезка и таких, что $a < x_1 < x_2 < b$ верно следующее:

если $f(x_1) > f(x_2)$ , то точка минимума $x^{\ast} \quad \in \quad [x_1, \quad b)$ ,
если $f(x_1) < f(x_2)$ , то точка минимума $x^{\ast} \quad \in \quad (a, \quad x2]$ .

Исходя из определения методов, видно, что всякий симметричный метод полностью определяется заданием отрезка $[a, \quad b]$ и правилом выбора первой точки. Тогда другая точка $x_2$ находится по правилу общему для всех симметричных методов: $x_2=a+b-x_{1}$ .

Соответственно, методы различаются способом выбора симметричных точек $x_1$ и $x_2$ .

Метод деления отрезка пополам

Описание метода

Параметры на входе: $\delta, \quad \epsilon$ - достаточно малые положительные константы.

1. Повторять:

2. $x_1 = \frac{a + b - \delta}{2}, \quad x_2 = \frac{a + b + \delta}{2}$ ;

3. Если $f(x_1) > f(x_2)$ , то $a=x_1$ ;

4. Если $f(x_1) < f(x_2)$ , то $b=x_2$ ;

5. пока $\frac{b-a}{2} \geq \epsilon$ ;

6. $\tilde{x}^{\ast}=\frac{a+b}{2}$ .

Анализ метода

Считаем, что один шаг - это один этап цикла (п. 2-4).

Изначальная длина отрезка составляет $\Delta_0=a-b$ .

После первого шага: $\Delta_1=\frac{a-b}{2}+(1-\frac{1}{2}) \delta$ ,

После $k$ -го шага: $\Delta_k=\frac{a-b}{2^k}+(1-\frac{1}{2^k}) \delta$ .

Если мы останавливаемся на $k$ -м шаге, то погрешность результата составит:

$|x^{\ast}-\tilde{x}^{\ast}| \quad < \quad \frac{1}{2}\Delta_k \quad = \quad \frac{a-b- \delta}{2^{k+1}}+ \frac{\delta}{2}$

Таким образом, чтобы погрешность вычисления была менее $\epsilon$ , должна выполняться оценка на число шагов:

$k>\log_2 (\frac{b - a - \delta}{\epsilon - \frac{\delta}{2} }) - 1$

На каждом шаге необходимо вычислить значение функции в 2х точках, соответственно, при $k$ шагах вычисляется $N=2k$ значений.

Недостаток:

Информация о значении функции в точках $x_1$ и $x_2$ используется только на одном шаге.

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

Определение:

Говорят, что точка $x$ осуществляет золотое сечение отрезка $[a, \quad b]$ , если

$\frac{b-a}{b-x}=\frac{b-x}{x-a}=\phi=\frac{1+\sqrt{5} }{2}$

В качестве $x_1$ и $x_2$ выберем точку золотого сечения отрезка и симметричную ей. Если $a<x_1<x_2<b$ , то при указанном выборе точек получаем, что $x_1$ - точка золотого сечения отрезка $[a, \quad x_2]$ , а $x_2$ - точка золотого сечения отрезка $[x_1, \quad b]$ . Таким образом, на каждом шаге, кроме первого, необходимо вычислять значение только в одной точке, вторая берется из предыдущего шага.

Описание метода

Параметр на входе: $\epsilon$ - достаточно малая положительная константа, погрешность метода.

1. $x_1 = b-\frac{b-a}{\phi}, \quad x_2 = a+\frac{b-a}{\phi}$

2. Повторять:

3. Если $f(x_1) > f(x_2)$ , то $a=x_1, \quad x_1=x_2, \quad x_2=b-(x_1-a)$ ;

4. Если $f(x_1) < f(x_2)$ , то $b=x_2, \quad x_2=x_1, \quad x_1=a+(b-x_2)$ ;

5. пока $\frac{b-a}{2} \geq \epsilon$ ;

6. $\tilde{x}^{\ast}=\frac{a+b}{2}$ .

Анализ метода

Считаем, что один шаг - это один этап цикла (п. 3-4), $\lambda=\frac{1}{\phi}=\frac{\sqrt{5}-1}{2}$ . Тогда, считая длину отрезка на каждом шаге $\Delta_k$ , получаем:

$\Delta_0=a-b$ ;

$\Delta_1=\lambda(b-a)=\lambda\Delta_0$ ;

$\Delta_{k+2}=\Delta_k-\Delta_{k+1}$ ;

Нетрудно проверить, что

(1)

$\Delta_k=\Delta_k(\lambda)=(-1)^{k-1}(F_k\lambda-F_{k-1})\Delta_0$ , где $F_k$ -числа Фибоначчи.

С другой стороны, выполняется равенство:

(2)

$\Delta_k(\lambda)=\lambda^k\Delta_0<0,7^k\Delta_0$

Чтобы погрешность вычисления была менее $\epsilon$ , должна по крайней мере выполняться оценка на число шагов:

$k>\frac{1}{\log_{0,7}\frac{2\Delta_0}{\epsilon}}$

Тогда значение будет вычисляться в $N=k+1$ точках.

Недостаток:

Неустойчивость относительно ошибок округления: мы получаем приблизительные значения чисел $\phi$ и $\lambda$ , дальнейшие вычисления только накапливают ошибки, что может привести к нарушению условия вложенности отрезков $[a_k, \quad b_k]$ и расходимости процесса.

Пусть $\lambda$ вычисляется с погрешностью $\delta$

Тогда имеем: $\tilde{\lambda}=\lambda+\delta$

Из (1):

$\Delta_k(\tilde{\lambda})=(-1)^{k-1}(F_k(\lambda+\delta)-F_{k-1})\Delta_0= \Delta_k(\lambda)+(-1)^{k-1}\delta F_k \Delta_0$ .

Подставляем (2):

(3)

$\Delta_k(\tilde{\lambda})=\lambda^k\Delta_0+(-1)^{k-1}\delta F_k \Delta_0$ .

Известно, что последовательность $\{\Delta_k(\lambda)\}$ сходится при $k \to \infty$ , В то же время $F_k \to +\infty$ , поэтому $|\Delta_k(\tilde{\lambda})| \to +\infty$ .

При этом числа Фибоначчи растут со скоростью геометрической прогрессии, знаменателем которой является число $\phi$ . Вследствие этого при фиксированной точности "раскачка" процесса происходит довольно быстро.

Числовой пример

Заключение

Список литературы

Карманов В.Г. Математическое программирование: Учебное пособие. - М.:ФИЗМАТЛИТ, 2004
Горячев Л.В. Одномерная минимизация. Методические указания к самостоятельной работе студентов по курсу “Методы оптимизации” - кафедра процессов управления ДВГУ, 2003

Внешние ссылки

См. также

Практикум ММП ВМК, 4й курс, осень 2008

Это незавершённая статья. Вы поможете проекту, исправив и дополнив её.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B7%D0%BE%D0%BB%D0%BE%D1%82%D0%BE%D0%B3%D0%BE_%D1%81%D0%B5%D1%87%D0%B5%D0%BD%D0%B8%D1%8F._%D0%A1%D0%B8%D0%BC%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D1%87%D0%BD%D1%8B%D0%B5_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4%D1%8B»

Категории: Незавершённые статьи | Учебные задачи

Метод золотого сечения. Симметричные методы

Материал из MachineLearning.

Содержание

Постановка задачи

Требования к функции

Симметричные методы

Метод деления отрезка пополам

Описание метода

Анализ метода

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

Описание метода

Анализ метода

Рекомендации в выборе параметров

Числовой пример

Заключение

Список литературы

Внешние ссылки

См. также

Просмотры

Личные инструменты

Навигация

Поиск

Инструменты