Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






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






Желание уменьшить объем вычислительной работы, требуемой для осуществления одной итерации метода наискорейшего спуска, привело к созданию методов покоординатного спуска.

Пусть - нач–ое приближение. Вычислим частную производную по первой координате и примем:

где е1={1, 0, …, 0}T – единичный вектор оси х(1). Следующая итерация состоит в вычислении точки х2 по формуле:

где е2={0, 1, 0, …, 0}T – единичный вектор оси х(2) и т. д.

Таким образом, в методах координатного спуска мы спускаемся по ломанной, состоящей из отрезков прямых, параллельных координатным осям.


Спуск по всем координатам составляет одну «внешнюю» итерацию. Пусть к – номер очередной внешней итерации, а j – номер той координаты, по которой производится спуск. Тогда формула, определяющая следующее приближение к точке минимума, имеет вид:

 
 

где к=0, 1, 2, …; j=1, 2, …n.

В координатной форме формула выглядит так:

 

 

После j=n счетчик числа внешних итераций к увеличивается на единицу, а j принимает значение равное единице.

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

Схема алгоритма покоординатного спуска с постоянным шагом

Шаг 1. При к=0 вводятся исходные данные х0, e1, a.

Шаг 2. Осуществляется циклический по j (j=1, 2, …, n) покоординатный спуск из точки хkn по формуле:

Шаг 3. Если ||x(k+1)n – xkn||£ e1, то поиск минимума заканчивается, причем:

Иначе к=к+1 и переходим к шагу 2.

 
 

Если же шаг aк выбирается из условия минимума функции:

 
 

 

 
 

то мы получаем аналог метода наискорейшего спуска, называемый обычно методом Гаусса – Зейделя.

Схема метода Гаусса – Зейделя

Шаг 1. При к=0 вводятся исходные данные х0, e1.

Шаг 2. Осуществляется циклический по j (j=1, 2, …, n) покоординатный спуск из точки хkn по формулам:

 
 

где akn+j-1 является решением задачи одномерной минимизации функции:

Шаг 3. Если ||x(k+1)n – xkn||£ e1, то поиск минимума заканчивается, причем:

 
 

Иначе к=к+1 и переходим к шагу 2.


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.006 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал