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

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

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

Версия 13:38, 19 ноября 2008

Содержание

1 Постановка задачи
2 Требования к функции
3 Симетричные методы
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$ используется только на одном шаге.