Интервал сглаживания при использовании скользящей средней равен. Сглаживание динамических рядов. Сглаживание временного ряда

Градиентом дифференцируемой функции f(x) в точке х называется n -мерный вектор f(x ) , компоненты которого являются частными производными функции f(х), вычисленными в точке х , т. е.

f"(x) = (дf(х )/дх 1 , …, дf(х )/дх n) T .

Этот вектор перпендикулярен к плоскости, проведенной через точку х , и касательной к поверхности уровня функции f(x), проходящей через точку х .В каждой точке такой поверхности функция f(x) принимает одинаковое значение. Приравнивая функцию различным постоянным величинам С 0 , С 1 , ... , получим серию поверхностей, характеризующих ее топологию (Рис. 2.8).

Вектор-градиент направлен в сторону наискорейшего возрастания функции в данной точке. Вектор, противоположный градиенту (-f’(х )) , называется антиградиентом и направлен в сторону наискорейшего убывания функции. В точке минимума градиент функции равен нулю. На свойствах градиента основаны методы первого порядка, называемые также градиентным и методами минимизации. Использование этих методов в общем случае позволяет определить точку локального минимума функции.

Очевидно, что если нет дополнительной информации, то из начальной точки х разумно перейти в точку х , лежащую в направлении антиградиента - наискорейшего убывания функции. Выбирая в качестве направления спуска р [k ] антиградиент -f’(х [k]) в точке х [k ], получаем итерационный процесс вида

х[k+ 1] = x [k ]-a k f"(x [k]) , а k > 0; k =0, 1, 2, ...

В координатной форме этот процесс записывается следующим образом:

x i [k +1]=х i [k ] - a k f(x [k]) /x i

i = 1, ..., n ; k = 0, 1, 2,...

В качестве критерия останова итерационного процесса используют либо выполнение условия малости приращения аргумента || x [k +l] - x [k ] || <= e , либо выполнение условия малости градиента

|| f’(x [k +l]) || <= g ,

Здесь e и g - заданные малые величины.

Возможен и комбинированный критерий, состоящий в одновременном выполнении указанных условий. Градиентные методы отличаются друг от друга способами выбора величины шага а k .

При методе с постоянным шагом для всех итераций выбирается некоторая постоянная величина шага. Достаточно малый шаг а k обеспечит убывание функции, т. е. выполнение неравенства

f(х[k +1]) = f(x [k] – a k f’(x [k])) < f(x [k]) .

Однако это может привести к необходимости проводить неприемлемо большое количество итераций для достижения точки минимума. С другой стороны, слишком большой шаг может вызвать неожиданный рост функции либо привести к колебаниям около точки минимума (зацикливанию). Из-за сложности получения необходимой информации для выбора величины шага методы с постоянным шагом применяются на практике редко.

Более экономичны в смысле количества итераций и надежности градиентные методы с переменным шагом, когда в зависимости от результатов вычислений величина шага некоторым образом меняется. Рассмотрим применяемые на практике варианты таких методов.

При использовании метода наискорейшего спуска на каждой итерации величина шага а k выбирается из условия минимума функции f(x) в направлении спуска, т. е.
f(x [k ] –a k f’(x [k ])) = f(x [k] – af"(x [k ])) .

Это условие означает, что движение вдоль антиградиента происходит до тех пор, пока значение функции f(x) убывает. С математической точки зрения на каждой итерации необходимо решать задачу одномерной минимизации по а функции
j (a) = f(x [k ] - af"(x [k ])) .

Алгоритм метода наискорейшего спуска состоит в следующем.

1. Задаются координаты начальной точки х .

2. В точке х [k ], k = 0, 1, 2, ... вычисляется значение градиента f’(x [k ]) .

3. Определяется величина шага a k , путем одномерной минимизации по а функции j (a) = f(x [k ] - af"(x [k ])).

4. Определяются координаты точки х [k+ 1]:

х i [k+ 1] = x i [k ] – а k f’ i (х [k ]), i = 1 ,..., п.

5. Проверяются условия останова стерационного процесса. Если они выполняются, то вычисления прекращаются. В противном случае осуществляется переход к п. 1.

В рассматриваемом методе направление движения из точки х [k ] касается линии уровня в точке x [k+ 1] (Рис. 2.9). Траектория спуска зигзагообразная, причем соседние звенья зигзага ортогональны друг другу. Действительно, шаг a k выбирается путем минимизации по а функции?(a) = f(x [k] - af"(x [k ])) . Необходимое условие минимума функции d j (a)/da = 0. Вычислив производную сложной функции, получим условие ортогональности векторов направлений спуска в соседних точках:

dj (a)/da = -f’(x [k+ 1]f’(x [k ]) = 0.

Градиентные методы сходятся к минимуму с высокой скоростью (со скоростью геометрической прогрессии) для гладких выпуклых функций. У таких функций наибольшее М и наименьшее m собственные значения матрицы вторых производных (матрицы Гессе)

мало отличаются друг от друга, т. е. матрица Н(х) хорошо обусловлена. Напомним, что собственными значениями l i , i =1, …, n , матрицы являются корни характеристического уравнения

Однако на практике, как правило, минимизируемые функции имеют плохо обусловленные матрицы вторых производных (т/М << 1). Значения таких функций вдоль некоторых направлений изменяются гораздо быстрее (иногда на несколько порядков), чем в других направлениях. Их поверхности уровня в простейшем случае сильно вытягиваются (Рис. 2.10), а в более сложных случаях изгибаются и представляют собой овраги. Функции, обладающие такими свойствами, называют овражными. Направление антиградиента этих функций (см. Рис. 2.10) существенно отклоняется от направления в точку минимума, что приводит к замедлению скорости сходимости.

Скорость сходимости градиентных методов существенно зависит также от точности вычислений градиента. Потеря точности, а это обычно происходит в окрестности точек минимума или в овражной ситуации, может вообще нарушить сходимость процесса градиентного спуска. Вследствие перечисленных причин градиентные методы зачастую используются в комбинации с другими, более эффективными методами на начальной стадии решения задачи. В этом случае точка х находится далеко от точки минимума, и шаги в направлении антиградиента позволяют достичь существенного убывания функции.

Рассмотренные выше градиентные методы отыскивают точку минимума функции в общем случае лишь за бесконечное число итераций. Метод сопряженных градиентов формирует направления поиска, в большей мере соответствующие геометрии минимизируемой функции. Это существенно увеличивает скорость их сходимости и позволяет, например, минимизировать квадратичную функцию

f(x) = (х, Нх) + (b, х) + а

с симметрической положительно определенной матрицей Н за конечное число шагов п, равное числу переменных функции. Любая гладкая функция в окрестности точки минимума хорошо аппроксимируется квадратичной, поэтому методы сопряженных градиентов успешно применяют для минимизации и неквадратичных функций. В таком случае они перестают быть конечными и становятся итеративными.

По определению, два n -мерных вектора х и у называют сопряженными по отношению к матрице H (или H -сопряженными), если скалярное произведение (x , Ну) = 0. Здесь Н - симметрическая положительно определенная матрица размером п хп.

Одной из наиболее существенных проблем в методах сопряженных градиентов является проблема эффективного построения направлений. Метод Флетчера-Ривса решает эту проблему путем преобразования на каждом шаге антиградиента -f(x [k ]) в направление p [k ], H -сопряженное с ранее найденными направлениями р , р , ..., р [k -1]. Рассмотрим сначала этот метод применительно к задаче минимизации квадратичной функции.

Направления р [k ] вычисляют по формулам:

p[k ] = -f’(x [k ]) +b k-1 p [k -l], k >= 1;

p = -f ’(x ) .

Величины b k -1 выбираются так, чтобы направления p [k ], р [k -1] были H -сопряженными:

(p [k ], Hp [k- 1])= 0.

В результате для квадратичной функции

,

итерационный процесс минимизации имеет вид

x[k +l] =x [k ] +a k p [k ],

где р [k ] - направление спуска на k- м шаге; а k - величина шага. Последняя выбирается из условия минимума функции f(х) по а в направлении движения, т. е. в результате решения задачи одномерной минимизации:

f(х[k ] + а k р [k ]) = f(x [k ] + ар [k ]) .

Для квадратичной функции

Алгоритм метода сопряженных градиентов Флетчера-Ривса состоит в следующем.

1. В точке х вычисляется p = -f’(x ) .

2. На k- м шаге по приведенным выше формулам определяются шаг а k . и точка х [k+ 1].

3. Вычисляются величины f(x [k +1]) и f’(x [k +1]) .

4. Если f’(x ) = 0, то точка х [k +1] является точкой минимума функции f(х). В противном случае определяется новое направление p [k +l] из соотношения

и осуществляется переход к следующей итерации. Эта процедура найдет минимум квадратичной функции не более чем за п шагов. При минимизации неквадратичных функций метод Флетчера-Ривса из конечного становится итеративным. В таком случае после (п+ 1)-й итерации процедуры 1-4 циклически повторяются с заменой х на х [п +1] , а вычисления заканчиваются при , где - заданное число. При этом применяют следующую модификацию метода:

x[k +l] = x [k ] +a k p [k ],

p[k ] = -f’(x [k ])+ b k- 1 p [k -l], k >= 1;

p = -f’(x );

f(х[k ] + a k p [k ]) = f(x [k ] + ap [k ];

.

Здесь I - множество индексов: I = {0, n, 2п, Зп, ...} , т. е. обновление метода происходит через каждые п шагов.

Геометрический смысл метода сопряженных градиентов состоит в следующем (Рис. 2.11). Из заданной начальной точки х осуществляется спуск в направлении р = -f"(x ). В точке х определяется вектор-градиент f"(x ). Поскольку х является точкой минимума функции в направлении р , то f’(х ) ортогонален вектору р . Затем отыскивается вектор р , H -сопряженный к р . Далее отыскивается минимум функции вдоль направления р и т. д.

Методы сопряженных направлений являются одними из наиболее эффективных для решения задач минимизации. Однако следует отметить, что они чувствительны к ошибкам, возникающим в процессе счета. При большом числе переменных погрешность может настолько возрасти, что процесс придется повторять даже для квадратичной функции, т. е. процесс для нее не всегда укладывается в п шагов.

Метод наискорейшего спуска является градиентным методом с переменным шагом. На каждой итерации величина шага k выбирается из условия минимума функции f(x) в направлении спуска, т.е.

Это условие означает, что движение вдоль антиградиента происходит до тех пор, пока значение функции f (x) убывает. С математической точки зрения на каждой итерации необходимо решать задачу одномерной минимизации по функции

()=f (x (k) -f (x (k)))

Воспользуемся для этого методом золотого сечения.

Алгоритм метода наискорейшего спуска состоит в следующем.

Задаются координаты начальной точки x (0) .

В точке x (k) , k = 0, 1, 2, …, вычисляется значение градиентаf (x (k)).

Определяется величина шага k путем одномерной минимизации по функции

()=f (x (k) -f (x (k))).

Определяются координаты точки x (k) :

x i (k+1) = x i (k) - k f i (x (k)), i=1, …, n.

Проверяется условие останова итерационного процесса:

||f (x (k +1))|| .

Если оно выполняется, то вычисления прекращаются. В противном случае осуществляется переход к п. 1. Геометрическая интерпретация метода наискорейшего спуска представлена на рис. 1.

Рис. 2.1. Блок схема метода наискорейшего спуска.

Реализация метода в программе:

Метод наискорейшего спуска.

Рис. 2.2. Реализация метода наискорейшего спуска.

Вывод: В нашем случае метод сошёлся за 7 итераций. Точка А7 (0,6641; -1,3313) является точкой экстремума. Метод сопряженных направлений. Для квадратичных функций можно создать градиентный метод, при котором время сходимости будет конечным и равно числу переменных n.

Назовем некоторое направление исопряженными по отношению к некоторой положительно определенной матрице ГессаH, если выполняется:

Тогда т.е.. Значит при единичнойH, сопряженное направление означает их перпендикуляр. В общем же случае H неединичная. В общем случае сопряженность - это применение матрицы Гесса к вектору - означает поворот этого вектора на некоторый уголи его растяжение или сжатие.

А теперь вектору векторортогонален т. е. сопряженность это не ортогональность векторови, а ортогональность повернутого векторат.е.и.

Рис. 2.3. Блок-схема метода сопряженных направлений.

Реализация метода в программе: Метод сопряженных направлений.

Рис. 2.4. Реализация метода сопряженных направлений.

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

Вывод: Точка А3 (0,6666; -1,3333), была найдена за 3 итерации и является точкой экстремума.

3. Анализ методов определения минимального, максимального значения функции при наличии ограничений

Напомним, что общая задача условной оптимизациивыглядит так

f(x) ® min, x Î W,

где W - собственное подмножество R m . Подкласс задач с ограничениями типа равенств выделяется тем, что множество  задается ограничениями вида

f i (x) = 0, где f i: R m ®R (i = 1, …, k).

Таким образом,W = {x Î R m: f i (x) = 0, i = 1, …, k}.

Нам будет удобно писать у функции f индекс "0". Таким образом, задача оптимизации с ограничениями типа равенств записывается в виде

f 0 (x) ® min, (3.1)

f i (x) = 0, i = 1, …, k. (3.2)

Если обозначить теперь через f функцию на R m со значениями в R k , координатная запись которой имеет вид f(x) = (f 1 (x), …, f k (x)), то (3.1)–(3.2)можно также записать в виде

f 0 (x) ® min, f(x) = Q.

Геометрически задача с ограничениями типа равенств - это задача о поиске наинизшей точки графика функции f 0 над многообразием  (см. рис. 3.1).

Точки, удовлетворяющие всем ограничениям (т. е. точки множества ), обычно называют допустимыми. Допустимая точка x* называется условным минимумом функции f 0 при ограничениях f i (x) = 0, i = 1, ..., k (или решением задачи (3.1)–(3.2)), если при всех допустимых точкахx f 0 (x*)  f 0 (x). (3.3)

Если (3.3)выполняется только для допустимыхx, лежащих в некоторой окрестности V x * точки x*, то говорят о локальном условном минимуме. Естественным образом определяются понятия условных строгих локального и глобального минимумов.