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 шагов.
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 шагов.
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 | |
Вивчення інтерфейсу У цім завданні вивчається інтерфейс Антивірусу Касперського. У ньому також розташовані посилання на інші вікна Вікна настроювань призначеного для настроювання завдань і компонентів Вікна статистики й звітів у якому можна одержати дані про результати роботи антивірусу Вікна довідкової системи У ході виконання завдання потрібно буде по черзі викликати всі чотири вікна інтерфейсу Антивірусу Касперського й ознайомитися з їхнім зовнішнім виглядом. Після успішного завершення процесу установки Антивірусу Касперського в... | |||