ID: 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