50626

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

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

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

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

Русский

2014-01-27

54 KB

71 чел.

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

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


 

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

81669. Литературно-критическое тв-во Н.В.Гоголя. Типологический анализ одной из статей 40.33 KB
  Статья Плетнева Чичиков или Мертвые души Гоголя опубликованная в июльском номере Современника за 1842 г. Плетнев как и Белинский ставил Гоголя в первый ряд среди современных писателей отмечая удивительную верность автора действительности. В произведениях Гоголя П. Вяземский решительно противился тому что именем Гоголя теоретики натуральной школы пытались придать ей идейную и эстетическую целостность.
81670. Особенности развития литературной критики в 1840-е гг. Литер.критика «Отечественных записок». Славянофильская критика. Литературно-критическая позиция журнала «Современник» 34.72 KB
  Анненков определялись противостоянием двух сформировавшихся на рубеже 1830 1840х годов течений русской общественной мысли западничества и славянофильства. отстаивали необходимость исторического движения России по европейскому пути выдвигали на первый план идею свободы и самоценности человеческой личности подчеркивали исчерпанность тех начал которые составляли основу древнерусской жизни. – публиковали свои статьи на страницах Москвитянина Московских литературных и ученых сборниковРусской беседы выступили против перенесения...
81671. Понятие о литературной критике, ее происхождение. Значение термина «критика» 28.26 KB
  Значение термина критика. В широком общекультурном смысле литературная критика обозначение восходящей к глубокой древности филологической рефлексии по поводу любого словесно-организованного текста. В современной западной культуре понятия литературная наука и литературная критика часто совпадают и употребляются на правах синонимов. В специальном литературоведческом смысле закрепленном отечественной гуманитарной традицией литературная критика род литературно-творческой и литературно-коммуникативной деятельности направленной на...
81672. Природа и предмет литературной критики. Взаимодействие критики с различными отраслями искусства и науки. Соотношение критики и литературоведения. Основные функции критики 31.97 KB
  Литературная критика двойственна по своей природе. Литературная критика естественно соотносится со многими областями науки и культуры: с филологией философией историей эстетикой герменевтикой культурологией психологией социологией книговедением с публицистикой и журналистикой с критикой художественное музыкальной театральной с кинокритикой телевизионной критикой и др. Испытывая непосредственное влияние близких или смежных гуманитарных сфер литературная критика в слою очередь способствует их развитию. Литературная критика одна...
81673. Типология литературной критики с точки зрения субъекта критической деятельности 38.99 KB
  Для критики словесного искусства нужны люди которые бы показывали бессмыслицу отыскивания мыслей в художественном произволении м постоянно руководили бы читателем в том бесконечном лабиринте сцеплений в котором и состоит сущность искусства и к тем законам которые служат основанием этих сцеплений. Сопряжение собственного эстетического опыта и литературной неизведанности явленной в оцениваемых словеснохудожественных произведениях одна из постоянно одолеваемых сложностей профессиональной литературной критики. Лидеров профессиональной...
81674. Типология литературной критики с точки зрения ее соотношения с определенными литературными направлениями 33.54 KB
  эстетические взгляды критика; Его соц. Классицистическая критика. Ломоносов Тредиаковский Сумароков Державин Херасков Лукин Плавильщиков Сентименталистская критика.Реакционная критика лагеря официальной народности.
81675. Типология литературной критики с точки зрения метода литературно-критической деятельности 31.86 KB
  эстетические взгляды критика; Его соц. В качестве рабочих определений можно предложить следующие: публицистическая филологическая и философская критика. Публицистическая критика в оценке литературных явлений идет от жизни выясняя в первую очередь их общественное звучание. Такова декабристская критика критика Белинского 1840х годов революционнодемократическая критика шестидесятников народническая марксистская критика.
81676. Типология литературной критики с точки зрения идеологической основы, принципиальных позиций анализа и оценки литературного произведения 36.18 KB
  Достоевского с характерными для неё призывами вернуться к своей почве к народным национальным началам. Достоевского. пример: Статья Михайловскогомарксистская редактора Отечественных записок против Достоевского Жестокий талант 1882 выглядит ясной по мысли политической позиции хотя и односторонней по выводам. Он чутко уловил в 1902 году что звезда Достоевского повидимому вновь загорается.