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

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

(Различия между версиями)

Текущая версия

Содержание

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://www.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»

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

@@ Строка 1: / Строка 1: @@
 == Постановка задачи ==
-В данной статье рассмотрены некоторые методы поиска экстремума функции одного переменного.
+В данной статье рассмотрены [[#Симметричные методы| симметричные методы]] поиска экстремума функции одного переменного.
 Пусть дана функция <tex>y=f(x)</tex>, необходимо найти минимум этой функции на заданном отрезке <tex>[a, \quad b]</tex> (задача максимума решается аналогично).
@@ Строка 22: / Строка 22: @@
 '''''Далее будем рассматривать только унимодальные функции. При этом предполагаем, что они определены в достаточном количестве точек.'''''
-== Описание методов ==
+== Симметричные методы ==
 В классе '''симметричных методов''' на каждом шаге выбирается две точки отрезка <tex>x_1</tex> и <tex>x_2</tex>, симметрично расположенных относительно центра этого отрезка. Дальнейшие действия определяются свойством унимодальной функции: <br />
 Пусть функция <tex>f(x)</tex> унимодальна на отрезке <tex>[a, \quad b]</tex>, а ее минимум достигается в точке <tex>x^{\ast}</tex>. Для любых точек <tex>x_1</tex> и <tex>x_2</tex> этого отрезка и таких, что <tex>a < x_1 < x_2 < b</tex> верно следующее:
@@ Строка 34: / Строка 34: @@
 Соответственно, методы различаются способом выбора симметричных точек <tex>x_1</tex> и <tex>x_2</tex>.
+----
 ===Метод деления отрезка пополам===
+====Описание метода====
 Параметры на входе: <tex>\delta, \quad \epsilon</tex> - достаточно малые положительные константы.
@@ Строка 47: / Строка 49: @@
 . пока <tex>\frac{b-a}{2} \geq \epsilon</tex>;
-. <tex>x^{\ast}=\frac{a+b}{2}</tex>.
+. <tex> \tilde{x}^{\ast}=\frac{a+b}{2}</tex>.
+====Анализ метода====
+Считаем, что один шаг - это один этап цикла (п. 2-4).
+Изначальная длина отрезка составляет <tex>\Delta_0=a-b</tex>.
+После первого шага: <tex>\Delta_1=\frac{a-b}{2}+(1-\frac{1}{2}) \delta</tex>,
+После <tex>k</tex>-го шага: <tex>\Delta_k=\frac{a-b}{2^k}+(1-\frac{1}{2^k})  \delta</tex>.
+Если мы останавливаемся на <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> используется только на одном шаге.
+----
 ===Метод золотого сечения===
-== Анализ методов и оценка ошибок ==
-==Улучшение метода Золотого сечения==
+'''Определение: '''
+Говорят, что точка <tex>x</tex> осуществляет золотое сечение отрезка <tex>[a, \quad b]</tex>, если
+<center><tex>\frac{b-a}{b-x}=\frac{b-x}{x-a}=\phi=\frac{1+\sqrt{5} }{2}</tex></center>
+В качестве <tex>x_1</tex>  и <tex>x_2</tex>  выберем точку золотого сечения отрезка и симметричную ей. Если <tex>a<x_1<x_2<b</tex>, то при указанном выборе точек получаем, что <tex>x_1</tex> - точка золотого сечения отрезка <tex>[a, \quad x_2]</tex>, а <tex>x_2</tex> - точка золотого сечения отрезка <tex>[x_1, \quad b]</tex>. Таким образом, на каждом шаге, кроме первого, необходимо вычислять значение только в одной точке, вторая берется из предыдущего шага.
+====Описание метода====
+Параметр на входе: <tex> \epsilon</tex> - достаточно малая положительная константа, погрешность метода.
+. <tex>x_1 = b-\frac{b-a}{\phi}, \quad x_2 = a+\frac{b-a}{\phi}</tex>
+. Повторять:
+:3.     Если <tex>f(x_1) > f(x_2)</tex>, то <tex>a=x_1, \quad x_1=x_2, \quad x_2=b-(x_1-a)</tex>;
+:4.     Если <tex>f(x_1) < f(x_2)</tex>, то <tex>b=x_2, \quad x_2=x_1, \quad x_1=a+(b-x_2)</tex>;
+. пока <tex>\frac{b-a}{2} \geq \epsilon</tex>;
+. <tex> \tilde{x}^{\ast}=\frac{a+b}{2}</tex>.
+====Анализ метода====
+Считаем, что один шаг - это один этап цикла (п. 3-4), <tex>\lambda=\frac{1}{\phi}=\frac{\sqrt{5}-1}{2}</tex>. Тогда, считая длину отрезка на каждом шаге <tex>\Delta_k </tex>, получаем:
+:<tex>\Delta_0=a-b</tex>;
+:<tex>\Delta_1=\lambda(b-a)=\lambda\Delta_0 </tex>;
+:<tex>\Delta_{k+2}=\Delta_k-\Delta_{k+1}</tex>;
+Нетрудно проверить, что
+{{eqno|1}}
+:<tex>\Delta_k=\Delta_k(\lambda)=(-1)^{k-1}(F_k\lambda-F_{k-1})\Delta_0</tex>, где <tex>F_k</tex>-[http://ru.wikipedia.org/wiki/Числа_Фибоначчи числа Фибоначчи].
+С другой стороны, выполняется равенство:
+{{eqno|2}}
+:<tex>\Delta_k(\lambda)=\lambda^k\Delta_0<0,7^k\Delta_0</tex>
+Чтобы погрешность вычисления была менее <tex>\epsilon</tex>, должна по крайней мере выполняться оценка на число шагов:
+:<tex>k>\frac{1}{\log_{0,7}\frac{2\Delta_0}{\epsilon}}</tex>
+Тогда значение будет вычисляться в <tex>N=k+1</tex>точках.
+'''Недостаток''':
+*Неустойчивость относительно ошибок округления: мы получаем приблизительные значения чисел <tex>\phi</tex> и <tex>\lambda</tex>, дальнейшие вычисления только накапливают ошибки, что может привести к нарушению условия вложенности отрезков <tex>[a_k, \quad b_k]</tex> и расходимости процесса.
+Пусть <tex>\lambda</tex> вычисляется с погрешностью <tex>\delta</tex>
+Тогда имеем: <tex>\tilde{\lambda}=\lambda+\delta</tex>
+Из {{eqref|1}}:
+:<tex>\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</tex>.
+Подставляем {{eqref|2}}:
+{{eqno|3}}
+:<tex>\Delta_k(\tilde{\lambda})=\lambda^k\Delta_0+(-1)^{k-1}\delta F_k \Delta_0</tex>.
+Известно, что последовательность <tex>\{\Delta_k(\lambda)\}</tex> сходится при <tex>k \to \infty</tex>, В то же время <tex>F_k \to +\infty</tex>, поэтому <tex>|\Delta_k(\tilde{\lambda})| \to +\infty</tex>.
+При этом числа Фибоначчи растут со скоростью геометрической прогрессии, знаменателем которой является число <tex>\phi</tex>. Вследствие этого при фиксированной точности "раскачка" процесса происходит довольно быстро.
+====Рекомендации в выборе параметров====
+Для сходимости процесса необходимо согласовывать точность <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>
 == Числовой пример ==
-== Рекомендации в выборе параметров ==
 == Заключение ==
 == Список литературы ==

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

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

Текущая версия

Содержание

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

См. также

Просмотры

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

Навигация

Поиск

Инструменты