Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Градиентный метод с постоянным шагом
|
|
Основная проблема в градиентных методах – это выбор шага ak. Достаточно малый шаг ak обеспечивает убывание функции, то есть выполнение неравенства: f(xk - akf `(xk))) < f(xk),
 |
но может привести к неприемлемо большому количеству итераций, необходимых для достижения точки минимума. С другой стороны, слишком большой шаг может вызвать неожиданный рост функции (невыполнение условия убывания) либо привести к колебаниям около точки минимума. Однако проверка усл–я убывания на каждой итерации является довольно трудоемкой, поэтому в методе град–го спуска с постоянным шагом задают a=ak пост–м и дост–но малым, чтобы можно было использовать этот шаг на любой итерации. При этом приходится мириться с возможно большим кол–вом итераций. Утешением является лишь то, что трудоемкость каждой итерации, в этом случае, минимальна (нужно вычислять только градиент f`(xk).
Схема алгоритма
Шаг 1. Задаются начальное приближение х0, постоянный шаг a, условия останова алгоритма e3. Вычисляется значение градиента f`(xk) – направление поиска. Присваивается к=0.
Шаг 2. Определяется точка очередного эксперимента:
хк+1 = хк - af’(xk),
или, в координатной форме:
 |
Шаг 3. Вычисляется значение градиента в точке хк+1:
,
или, в координатной форме:
Шаг 4. Если || f ` (xk+1) ||£ e3, то поиск заканчивается, при этом:
Иначе к=к+1 и переходим к шагу 2.
Градиентный метод с дроблением шага
В методе градиентного спуска с дроблением шага величина шага aк выбирается так, чтобы было выполнено неравенство:
f(xk-ak 
)-f(xk)£ -dak|| f ` (xk) ||2, где 0< d< 1 – произвольно выбранная постоянная (одна и та же для всех итераций). Это требование на выбор шага aк более жесткое, чем условие убывания, но имеет тот же смысл: функция должна убывать от итерации к итерации. Однако при выполнении неравенства функция будет уменьшаться на гарантированную величину, определяемую правой частью неравенства.
 |
Процесс выбора шага протекает следующим образом. Выбираем число a> 0, одно и то же для всех итераций. На к-й итерации проверяем вып–е нер–ва при aк=a. Если оно выполнено, полагаем aк=a и переходим к след–ей итерации. Если нет, то шаг aк дробим, напр–р уменьшаем каждый раз в два раза, до тех пор, пока оно не выполнится.
Схема алгоритма
Шаг 1. Задаются х0, e3, d и начальное значение шага a. Вычисляется значение градиента f`(x 0) – направление поиска. Присваивается к=0.
Шаг 2. Проверяется условие: f(xk-a )£ -da|| ||2. Если выполняется, то переходим к шагу 3, иначе дробим значение a (a=a/2) и повторяем шаг 2.
Шаг 3. Определяется точка очередного эксперимента: хк+1 = хк - a f`(xk).
Шаг 4. Вычисляется значение градиента в точке хк+1: f `(хк+1).
Шаг 5. Если || f`(xk+1) ||£ e3, то поиск заканчивается, при этом:
Иначе к=к+1 и переходим к шагу 2.