50626

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

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

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

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

Русский

2014-01-27

54 KB

62 чел.

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

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


 

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

59981. ГЕОМЕТРИЧНІ ФІГУРИ І ВСЕСВІТ. БІНАРНИЙ УРОК 175 KB
  Учитель фізики. Учитель математики. Учитель починає вправу словами: посміхніться один одному передайте хорошу енергію своєму другу.
59982. КОНСПЕКТ ІНТЕГРОВАНОГО ЗАНЯТТЯ ДЛЯ ДІТЕЙ СТАРШОГО ДОШКІЛЬНОГО ВІКУ «ПОДОРОЖ У ВСЕСВІТ» 54.5 KB
  Розширити та закріпити знання дітей про супутник Землі Місяць вправляти у визначенні фаз місяця називати народні прикмети про місяць. Що вночі горить а вдень гасне Відгадали загадки Звісно всі вони про Місяць вічний супутник Землі.
59983. Получение тетрахлороцинката аммония и изучение его свойств 134 KB
  Тетрахлорцинкат аммония ((NH4)2[ZnCl4]) относится к ацидокомплексам и представляет собой блестящие ромбические пластинчатые кристаллы с температурой плавления 150°С.
59984. КРОСВОРДИ НА УРОКАХ АСТРОНОМІЇ 27 KB
  Кросворди можна розподілити за темами і використовувати як окремі завдання при опитуванні чи при повторенні закріпленні матеріалу. Залюбки учні розвязують кросворди на уроках – замінах. Кросворди можна креслити тушшю на великих листках кольорового паперу а заповнювати крейдою.
59985. Фінансова оцінка та економічний ефект бізнес-проекту 399.5 KB
  В Україні на даному етапі існує потреба в активізації бізнес-освіти, впровадженні новітніх програм, завданням яких є формування навичок для ефективної діяльності в ринкових умовах.
59987. «Гіркий корінь навчання» має бути солодким 32.5 KB
  Ушинський розглядав мовлення у невід’ємному зв’язку з формуванням особистості дитини визначав основні завдання зміст методику навчання мовлення акцентував увагу на вивченні рідної мови. Він зауважував що вивчення мови має три мети.
59988. Вуглеводи 225.5 KB
  Обладнання: мультимедійний проектор; мікроскопи; зразки крохмалю глюкози целюлози фруктози цукрози молока цукрурафінаду соку; чашки Петрі зі зразками картоплі ковбаси сиру цибулі піпетки розчин йоду фільм Вуглеводи.
59989. Вулканізм і вулкани. Джерела, гейзери 81.5 KB
  А девізом нашого уроку нехай будуть слова Михайла Казимирчука: Напружуй нерв напружуй мозок Сприймай збагни і зрозумій А щоб все вдалося як радять психологи треба налаштуватися тільки на успіх тільки на позитив.