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


 

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

82964. Медицинская этика 92.5 KB
  Тактика медицинского работника в терапевтическом отделении В самых распространенных в клинической медицине терапевтических отделениях как правило находятся больные самого различного профиля с заболеваниями сердечно-сосудистой системы желудочно-кишечного тракта органов дыхания почек и другие.
82965. Іноземні інвестиції в Україні 33.67 KB
  Правовий режим іноземного інвестування в Україні регулюється національним законодавством України та міжнародними договорами України що після їх схвалення Верховною Радою України імплементуються у національне законодавство.
82966. Семья и психическое здоровье ребенка 40.68 KB
  Тема взаимосвязи психологической атмосферы в семье и уровня психического развития ребенка, рассмотренная в данной курсовой работе, по своей актуальности заслуживает внимания не только специалистов в областях психологии, педагогики, но и, прежде всего, родителей, воспитателей детских дошкольных учреждений.
82967. Микробиология приготовления обыкновенного сена 64.79 KB
  При их участии происходит разложение различных органических веществ в почве водоемах они обуславливают круговорот веществ и энергии в природе. При их активном участии постоянно осуществляется два противоположных процесса: синтез из минеральных веществ сложных органических соединений...
82968. Парниковый эффект 38.14 KB
  Экологи всех стран отмечают резкое потепление климата Земли. Данное изменение климата носит название парникового эффекта. Хотя изменения климата естественные или вызванные деятельностью человека так называемые антропогенные происходят сравнительно медленно они охватывают огромные регионы...
82969. Планирование персонала 83.5 KB
  Термин планирование персонала включает в себя все проблемы сферы персонала которые могут возникнуть в будущем. Планирование персонала во-первых служит целевому планированию потребностей в области персонала и во-вторых планированию мероприятий которые должны проводиться...
82970. ФИЗИОЛОГИЯ РЕФЛЕКСОВ 32.62 KB
  Большинство видов нервной регуляции эффекторов осуществляется через такие дуги которые широко варьируют по сложности. Более сложные формы нервной интеграции в основном имеют ту же природу. Однако межнейронные связи центральной нервной системы широко варьируют по сложности и благодаря...
82971. Функции и виды прибыли 152 KB
  Для каждого студента факультета экономики и финансов важнейшим и приоритетным направлением является глубокое изучение экономических дисциплин, в частности такого предмета, как экономика предприятия. Для достижения должного уровня познания данной дисциплины необходим системный подход к ее исследованию.
82972. Гигиена ротовой полости и питания 848.42 KB
  Цель гигиены состоит в предотвращении заболеваний, сохранении и укреплении здоровья, создании оптимальных условий для жизнедеятельности человека методами профилактики. Результатом поставленной цели можно считать оптимизацию условий труда и жизни человека вследствие снижения заболеваемости и т.п.