50626

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

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

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

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

Русский

2014-01-27

54 KB

89 чел.

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

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


 

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

20950. Стеганографічні перетворення 33.98 KB
  h int checkchar; char rmallwschar; int main { int us = 1; char ss1ptr; cout vvedite nabor simvolov ; cin s; cout endl vvedite nabor simvolov dlya poiska i udaleniya ; cin s1; whileptr=0 { int ik; ptr=strstrss1; for i=1;i = strlens1;i { ptr=1; ptr=' '; } s=rmallwss; } return 0; } char rmallwschar str { char obuf nbuf; for obuf = str nbuf = str; obuf obuf; obuf { if isspaceobuf nbuf = obuf; } nbuf = ' 0'; return str; } Висновок: за час виконання практичноъ роботи роздивився тему...
20951. Робота з командним рядком. Мережна активність 377.58 KB
  Мережна активність Ціль роботи: одержання практичних навичок по роботі з Командним рядком і по виявленню шкідливих програм на локальному комп'ютері під керуванням Microsoft Windows XP за допомогою Командного рядка. Завдання: одержати навички роботи з Командним рядком вивчити й проаналізувати мережну активність можна за допомогою Командного рядка. Робота з Командним рядком Cmd.
20952. Захист від несанкціонованого доступу в операційній системі Windows 366.5 KB
  Завдання: Вивчити настроювання Брандмауера Windows .Центру забезпечення безпеки Windows. Брандмауер Windows Меню Пуск Панель керування Брандмауер Windows Рис.
20953. Керування правами користувачів в операційній системі Windows 243 KB
  Домен або глобальні користувачі й групи управляються мережним адміністратором. Операційна система містить кілька вбудованих облікових записів користувачів і груп які не можуть бути вилучені Групи Адміністратори Користувачі що входять у групу Адміністратори мають повний доступ на керування комп'ютером. Оператори архіву Члени групи Оператори архіву можуть архівувати й відновлювати файли на комп'ютері незалежно від усіх дозволів якими захищені ці файли. Досвідчені користувачі Члени групи досвідчених користувачів можуть створювати...
20954. Основні ознаки присутності на комп'ютері шкідливих програм 571.5 KB
  Вивчення настроювань браузера Рис. Значення цього поля збігається з тим адресою яка була автоматично заданий при відкритті браузера Рис. C її допомогою можна в режимі реального часу відслідковувати запущені процеси що виконуються додатки й оцінювати завантаженість системних ресурсів комп'ютера й використання мережі Рис.
20955. Профілактика проникнення шкідливого програмного забезпечення. Реєстр Windows 186.5 KB
  Реєстр Windows Ціль: практичне освоєння студентами науковотеоретичних положень дисципліни з питань захисту інформації від впливу шкідливого програмного забезпечення на основі використання методів і засобів профілактики вірусних атак а також оволодіння ними технікою експериментальних досліджень і аналізу отриманих результатів прищеплювання навичок роботи з обчислювальною технікою. Профілактика проникнення шкідливого програмного забезпечення за допомогою дослідження Реєстру ОС Windows XP Реєстр операційної системи Windows це більша база...
20956. Установка та попереднє настроювання Антивірусу Касперського 949 KB
  Завдання: Вивчити системні вимоги антивірусу й зрівняти їх з параметрами комп'ютера установити й настроїти Антивірус Касперського. Бувають також вимоги до апаратного забезпечення у цьому випадку постулируется необхідність наявності на комп'ютері деякого мінімального обсягу оперативної пам'яті якщо її менше те програма буде дуже повільно працювати або ж не запуститься зовсім вільного простору на диску для розміщення всіх необхідних у роботі додатка файлів тактової частоти процесора від якої залежить продуктивність комп'ютера й інше....
20957. Робота Антивірусу Касперського 593 KB
  Вивчення інтерфейсу У цім завданні вивчається інтерфейс Антивірусу Касперського. У ньому також розташовані посилання на інші вікна  Вікна настроювань призначеного для настроювання завдань і компонентів  Вікна статистики й звітів у якому можна одержати дані про результати роботи антивірусу  Вікна довідкової системи У ході виконання завдання потрібно буде по черзі викликати всі чотири вікна інтерфейсу Антивірусу Касперського й ознайомитися з їхнім зовнішнім виглядом. Після успішного завершення процесу установки Антивірусу Касперського в...