50626

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

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

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

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

Русский

2014-01-27

54 KB

80 чел.

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

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


 

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

55732. Яку роль відіграє у житті людини родинне коло, сімейні свята і традиції 64.5 KB
  Мета: пояснити зміст понять сімя сімейні обовязки та конфлікт; розвивати вміння характеризувати ієрархію родинних звязків у своїй сімї; розкрити роль родинного кола сімейних свят і традицій у житті людини...
55734. Родинами багата Україна 88 KB
  Мене ви матусю під серцем носили. Ви пестили ніжні слова говорили Та з пелюшок мене розуму вчили. я вдячний матусю за те що ви є За те що до праці привчаєте мене. Мене ви зустрінете і посміхнетесь Я щось запитаю ви зразу озветесь.
55735. Наша шкільна родина 75.5 KB
  Мета: удосконалювати знання учнів про важливість родинних зв’язків; плекати в дитячих душах любов і повагу до батьків, свого роду, гордість за свій народ; розвивати вміння висловлювати свої почуття і вміння бути вдячними;
55736. Виховний захід «Моя родина, я, клас, шкільна сім`я» 59 KB
  Ми зібрались сьогодні на свято. Добрий день всі хто прийшов сьогодні на наше свято Здрастуйте дорога класна родино Дорогі діти Шановні батьки Любі друзі Ми починаємо наше родинне свято.
55737. Нашому роду - нема переводу. Родинне свято 67.5 KB
  Розширити поняття дітей про сім ю, родину, наш український рід, щедрий, багатий своїми традиціями, обрядами, прищеплювати любов до близьких людей, повагу до старших, ровесників та молодших за себе; довести, що найсильніше зігріває родинне вогнище, материнське тепло, батьківська підтримка і порада
55738. Моя сім’я, моя родина – це рідна область, Україно! 52 KB
  Формувати знання дітей про значення здоровя розуміння необхідності дружби зі спортом. Прищеплювати гігієнічні навички встановити взаємозвязок між здоровям дітей та майбутнім країни.
55739. Семья и семейные ценности 104.5 KB
  Цель: показать ценности семьи и семейные традиции в русской классической литературе на примере романа Л.Н. Толстого «Война и мир»; формировать представление о психологических особенностях семьи, помочь в осознании семейных ценностей
55740. Яку роль відіграє у житті людини родинне коло 130.5 KB
  Мета: Уточнити розширити поглибити уявлення дітей про сімю родину рід їх значення в житті людини пробуджувати пізнавальний інтерес до історії свого родоводу формувати навички толерантного поводження в у сімї...