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 шагов.
- Вычисляем Sk+1 по формуле
Sk+1=-gradF(Xk+1) + kSk.
При обновлении процесс повторяют с п.1, в противном случае с п.2. При реализации данного алгоритма для функции (1) требуемая точность достигается за 7 итераций.
Порядок выполнения работы:
- Построим график заданной функции:
[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);
- Напишем программу минимизации данной функции методом сопряженных градиентов:
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 шагов.
- При минимизации функции стандартными средствами 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
