50626

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

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

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

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

Русский

2014-01-27

54 KB

83 чел.

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

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


 

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

69643. Повышение эффективности продажи рыбных консервов и пресервов в магазине «Квартал» № 1 7.63 MB
  проведена оценка эффективности продаж рыбных консервов и пресервов, соответствия ассортимента рыбных консервов и пресервов, реализуемых в магазине «Квартал» № 1 современным тенденциям развития рынка, организации торгово-технологического процесса в магазине по продаже рыбных консервов и пресервов, а также сравнительная товароведная характеристика рыбных пресервов.
69644. МЕЖЛИЧНОСТНЫЕ И ВНУТРИГРУППОВЫЕ ОТНОШЕНИЯ В УЧЕБНОЙ ГРУППЕ ПЕРВОКЛАССНИКОВ 190 KB
  Межличностные отношения сверстников младшего школьного возраста зависят от многих социально-психологических факторов, а, прежде всего, от таких как взаимная симпатия, общность интересов, внешние жизненные обстоятельства, гендерные отличия.
69645. Исследование малой рекламы как продвижение ресторанных услуг калининграда 784 KB
  Изучить теоретический материал по специальным дисциплинам: маркетингу и рекламной деятельности ресторана, сервисному обслуживанию ресторана, обобщить теоретический материал, ознакомиться с деятельностью рекламных агентств полного цикла, исследовать рекламную деятельность предприятий общественного питания...
69646. Творчий проект: Таця 7.59 MB
  Перші підноси були величезними - розміром зі стіл, називалися «скатертними» і призначалися для багатьох страв. Потім їх розміри поступово зменшилися. Якщо ж шлях від кухні до їдальні порівняно довгий, необхідно використати підноси з прорізами або ручками.
69647. Виготовлення настінного календаря 576 KB
  Розробка технічного завдання Призначення виробу. Настінний календар призначений для повсякденного використання в побуті та на робочих місцях. Основними вимогами повинні бути практичність та естетичний вигляд.
69648. ОБРЯДОВИЙ РУШНИК 342 KB
  Експлуатаційні показники застосування виробу виду роботи на практиці виходячи призначення виробу цей рушник використовується при обряді хрещення а також функція оберегу. Вплив виробу на якість і ефективність реалізації ним експлуатаційних показників рушник є оберегом для дитини...
69649. Виготовлення іграшкової машинки 1.4 MB
  Розробка технічного завдання Призначення виробу. Цей виріб призначено для дітей віком від 6 до 10 років, Вимоги до матеріалів. Матеріали повинні бути екологічно чисті та нешкідливі для дітей. Ще Машинку треба зробити так щоб дитина ненароком не проковтнула яку не будь деталь...
69650. Розробка творчого проекту на виготовлення декоративної тарелі 5.49 MB
  Призначення проектованого виробу: У наш час декоративні тарелі можна використовувати як посуд для святкового столу що слугує для подання печива цукерок солодощів горіхів різноманітних фруктів а також для підношення на весіллі чарок з напоями медом вином хлібасолі тощо.