50626

Метод сопряженных градиентов

Лабораторная работа

Математика и математический анализ

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

Русский

2014-01-27

54 KB

64 чел.

Лабораторная работа

6

Тема

Метод сопряженных градиентов

Ф.И.О.

Пастухова Светлана Владимировна

Группа

403

Вариант

15

Минимизировать функцию f(x,y)=ax + by + exp(cx2 + dy2 ) методом градиентного спуска.

 N

a

b

c

d

15

15

-0.0

1.96

0.25

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

Например, минимизация "овражной" функции

F(x1 ,x2)=-(x1 ) 2 exp[1  (x1)2 20.25(x1-x2) 2 ] (1)

градиентным методом потребовала более 100 итераций. Спуск начинался из точки (0.1,0.1) с начальным шагом =1 и =10 -.Такое число итераций очень велико, т.к. минимум функции находится в точке (1,1).

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

1. Вычисляем S 0=-gradF(X0 ) в точке X0.

2. На k-м шаге (k=1,2,... ) решаем задачу минимизации по a функции F(Xk + aSk ), в результате чего определяем величину шага a и точку Xk+1=Xk + k Sk.

3. Вычисляем величины F(Xk+1 ) и gradF(Xk+1 ).

4. Если -gradF(Xk+1 < ε, то точка Xk+1 - решение задачи, в противном случае определяем коэффициент k по формуле

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

  1.  Вычисляем Sk+1 по формуле

Sk+1=-gradF(Xk+1) + kSk.

При обновлении процесс повторяют с п.1, в противном случае с п.2. При реализации данного алгоритма для функции (1) требуемая точность достигается за 7 итераций.

Порядок выполнения работы:

  1.  Построим график заданной функции:

[x,y]=meshgrid(-7:0.5:7,-7:0.5:7);

u=a*x+b*y+exp(c*x.^2+d*y.^2);

surfc(x,y,u);

  1.  Напишем программу минимизации данной функции методом сопряженных градиентов:

clear;

x=sym('x');

y=sym('y');

a=15; b=-0.0; c=1.96; d=0.25;

%находим градиент функции

F=a*x+b*y+exp(c*x^2+d*y^2);

Fx = diff(F,x);

Fy = diff(F,y);

%устанавливаем начальное решение

u(:,1)=[0;0];

x=u(1,1);

y=u(2,1);

fx=eval(Fx);

fy=eval(Fy);

dJ(:,1)=[fx;fy];

p(:,1)=dJ(:,1);

alpha = 0.15;

u(:,2)=u(:,1)-alpha*p(:,1);

epsilon=0.001;

i=1;

while (sqrt(fx^2+fy^2)>epsilon)&&(i<30)

   i=i+1;

   x=u(1,i);

   y=u(2,i);

   fx=eval(Fx);

   fy=eval(Fy);

   dJ(:,i)=[fx;fy];

   if mod(i,2)==0 beta(i)=0; else beta(i)=(dJ(1,i)*(dJ(1,i-1)-dJ(1,i))+dJ(2,i)*(dJ(2,i-1)-dJ(2,i)))/((dJ(1,i-1)^2)+(dJ(2,i-1)^2));end;

   p(:,i)=dJ(:,i)-beta(i)*p(:,i-1);

aj=0;

bj=1;

n=0;

delta=0.0005;

epsilon1=0.001;

while (bj-aj)>=epsilon1

   alpha1=(aj+bj-delta)/2;

   alpha2=(aj+bj+delta)/2;

   x1j=u(1,i)-alpha1*p(1,i);

   y1j=u(2,i)-alpha1*p(2,i);    

   x2j=u(1,i)-alpha2*p(1,i);

   y2j=u(2,i)-alpha2*p(2,i);  

   j1=a*x1j+b*y1j+exp(c*x1j^2+d*y1j^2);

   j2=a*x2j+b*y2j+exp(c*x2j^2+d*y2j^2);    

   if (j1)<=(j2)  bj=alpha2;

   end;

   if (j1)>(j2)  aj=alpha1;

   end;

   n=n+1;

end;

   alpha=(alpha1+alpha2)/2;

%находим следующее приближение u_(i+1)

u(:,i+1)=u(:,i)-alpha*p(:,i);

end;

u

a*u(1,i)+b*u(2,i)+exp(c*u(1,i).^2+d*u(2,i).^2)

Получим:

min =[-1.0167, 0.0974]

f(xmin)=  -8.7965

Заданная точность eps=0.001 достигнута за n=11 шагов.

  1.  При минимизации функции стандартными средствами MatLab

x = [0,-6];

min = fminsearch(@my_fun,x)

где x=[0,-6] – начальное приближение, а @my_fun:

function f = my_fun(x)

f =15*x(1)-0*x(2)+exp(1.96*x(1)^2+0.25*x(2)^2); 

Получим:

min =[-1.0167, 0.0974]

f(xmin)=  -8.7965


 

А также другие работы, которые могут Вас заинтересовать

25983. Философия Гераклита. Принципы диалектики. Диалектика и метафизика 25.3 KB
  Принципы диалектики. Согласно его рассуждениям мудрый тот кто не дает названия предметамони меняются Основные принципы диалектики. Гегель расширил понимание диалектики вывел ее из рамки движения мыслиувидел столкновение и объединение противоположностей в самой действительности в истории в культуре. В современных вариантах диалектики практически отсутствует понимания ее как о развитии.
25984. Философия и жизнь Сократа 19.09 KB
  Философия и жизнь Сократа О жизни и деятельности Сократа одного из величайших философов Древней Греции можно узнать лишь по произведениям его современников и учеников в первую очередь Платона потому что сам Сократ письменных источников после себя не оставил. Платон же познакомился с Сократом за восемь лет до гибели последнего когда Сократу было уже за шестьдесят и встреча эта произвела революцию в душе будущего знаменитого философа. Платон же написал и Апологию Сократа из которой можно узнать о некоторых аспектах сократовской...
25985. Платон. Сущность философского идеализма 18.03 KB
  Выделить в творчестве Платона какойлибо аспект и систематически изложить его довольно сложно так как приходится реконструировать мысли Платона из отдельных высказываний которые настолько динамичны что в процессе эволюции мысли порой превращаются в свою противоположность.Систематическое широкое использование математического материала имеет место у Платона начиная с диалога Менон где Платон подводит к основному выводу с помощью геометрического доказательства. Значительно в большей мере чем в гносеологии влияние математики...
25986. Философия Аристотеля, ученого-энциклопедиста 38.02 KB
  Проблема человека Познание человека – центральная проблема философии. Стремление человека познавать свою собственную природу является одним из главных стимулов развития философии мысли. В современной науке насчитывается более 800 дисциплин изучающих человека. – неделимый соединяет в себе черты: 1 ОБЩЕЧЕЛОВЕЧЕСКИЕ присущие всем людям как членам человеческого рода вида homo sapiens; 2 СОЦИАЛЬНОТИПИЧЕСКИЕ свойственные ему как представителю конкретного общества определенной культуры народа социальной группы; 3 ИНДИВИДУАЛЬНЫЕ...
25987. Философия эллинизма 20.28 KB
  Жизнь и деятельность ВойноЯсенецкого. ВойноЯсенецкого Валентин Феликсович ВойноЯсенецкий родился в 1877 г. Его отец провизор Феликс Станиславович ВойноЯсенецкий происходил из известного с 16 века обедневшего дворянского рода. Отец ВойноЯсенецкого был католиком мать Мария Дмитриевна Кудрина православной.
25988. Основные принципы философии средневековья. Номинализм и реализм 16.6 KB
  Основные принципы философии средневековья. Возникновение средневековой философии очень частосвязывают с падением Западной Римской империи 476 год н. В средневековой философии напротив реальностью определяющей все сущщее есть Бог.э конкурируют между собой философские учения стоиков эпикурейцев неоплатоников и в это же время формируются очаги новой веры и мысли которые в последствии составят основу средневековой философии.
25989. Философия Фомы Аквинского, Наука в жизни общества 32.58 KB
  Платоническое представление Августина о человеческой душе как независимой от тела духовной субстанции обладающей способностью непосредственно усматривать вечные несотворенные истины Идеи в свете Божественного просвещения Фома заменяет восходящим к Аристотелю понятием души как формы тела. Воздействие объектов приводит к образованию в душе их чувственных образовподобий от которых интеллект абстрагирует умопостигаемые формы универсалии следы творения вещей с помощью Божественных Идей. разумная часть человеческой души являются...
25990. Возрождение Основные вопросы философии 24.92 KB
  Соловьёв Владимир Сергеевич [1628. Сын Соловьёв Владимир Сергеевич М. После речи против смертной казни в марте 1881 в связи с убийством Александра II народовольцами Соловьёв Владимир Сергеевич был вынужден оставить преподавательскую работу.Как мыслитель и утопист Соловьёв Владимир Сергеевич оказался на пересечении разных духовных течений.
25991. Основные принципы гуманизма. Э. Роттердамский и др 20.79 KB
  В данной работе мы не будем говорить ни о христианской догматике ни о христианской мистике. Мы будем говорить лишь о христианской морали то есть о том насколько христианство отвечает высоким моральным стремлениям человеческого духа здесь на земле. Уже одно то что из всех евангельских догматов самым главным является догмат о том что Бог именно изза любви к человеку Сам становится человеком терпит все человеческие невзгоды лишения и страдания вплоть до мучительной и позорной смерти и все это повторяем именно изза любви к...