50626

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

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

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

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

Русский

2014-01-27

54 KB

72 чел.

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

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


 

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

14691. ОСНОВЫ ДОЗИМЕТРИИ 119 KB
  ЛАБОРАТОРНАЯ РАБОТА №26 ОСНОВЫ ДОЗИМЕТРИИ Дозиметрия радиоактивного излучения есть один из разделов прикладной физики ядра и элементарных частиц. Дозиметрия первоначально возникла в связи с открытием рентгеновских лучей и их вредным воздействием на живой организм. ...
14692. ИЗУЧЕНИЕ РАБОТЫ СЦИНТИЛЛЯЦИОННОГО СЧЕТЧИКА ИОНИЗИРУЮЩИХ ИЗЛУЧЕНИЙ 59 KB
  ЛАБОРАТОРНАЯ РАБОТА №25 ИЗУЧЕНИЕ РАБОТЫ СЦИНТИЛЛЯЦИОННОГО СЧЕТЧИКА ИОНИЗИРУЮЩИХ ИЗЛУЧЕНИЙ Задание для подготовки к лабораторной работе: По указанной литературе изучите устройство и принцип работы сцинтилляционного счетчика иониз
14693. ИЗУЧЕНИЕ РАБОТЫ ГАЗОРАЗРЯДНОГО СЧЕТЧИКА ИОНИЗИРУЮЩИХ ИЗЛУЧЕНИЙ 75 KB
  ЛАБОРАТОРНАЯ РАБОТА №24 ИЗУЧЕНИЕ РАБОТЫ ГАЗОРАЗРЯДНОГО СЧЕТЧИКА ИОНИЗИРУЮЩИХ ИЗЛУЧЕНИЙ Задание для подготовки к лабораторной работе По указанной литературе изучите устройство и принцип работы газоразрядного счетчика ионизирующих излучений...
14694. ОПРЕДЕЛЕНИЕ ПРОЦЕНТНОГО СОДЕРЖАНИЯ KCl В СМЕСИ KCl+NaCl 32 KB
  ЛАБОРАТОРНАЯ РАБОТА №23 ОПРЕДЕЛЕНИЕ ПРОЦЕНТНОГО СОДЕРЖАНИЯ KCl В СМЕСИ KClNaCl Природный калий представляет собой смесь изотопов: К3993 К4003 К4167. Изотопы К39 и К41 стабильны изотоп К40 радиоактивен с периодом полураспада 14109 лет. Радиоактивное превращение калий40 прот
14695. ОПРЕДЕЛЕНИЕ ЭНЕРГИИ α-ЧАСТИЦ ПО ВЕЛИЧИНЕ ИХ ПРОБЕГА В ВОЗДУХЕ 53 KB
  ЛАБОРАТОРНАЯ РАБОТА №22 ОПРЕДЕЛЕНИЕ ЭНЕРГИИ αЧАСТИЦ ПО ВЕЛИЧИНЕ ИХ ПРОБЕГА В ВОЗДУХЕ Ядра некоторых изотопов как естественных так и искусственных могут самопроизвольно превращаться в другие ядра. Такие превращения ядер называют радиоактивным распадом. При испу...
14696. ОБРАБОТКА РЕЗУЛЬТАТОВ ИЗМЕРЕНИЙ В ЭКСПЕРИМЕНТЕ ЯДЕРНОЙ ФИЗИКИ 40.5 KB
  ЛАБОРАТОРНАЯ РАБОТА №21 ОБРАБОТКА РЕЗУЛЬТАТОВ ИЗМЕРЕНИЙ В ЭКСПЕРИМЕНТЕ ЯДЕРНОЙ ФИЗИКИ Вероятность того что за данный промежуток времени ∆t распадётся k атомов из n равна где pk число групп из n атомов в каждой из которых произошло к радиоактивных распадов a q об
14697. ОПРЕДЕЛЕНИЕ СКОРОСТИ ЗВУКА В ВОЗДУХЕ МЕТОДОМ СТОЯЧЕЙ ВОЛНЫ 408 KB
  Лабораторная работа № 5 ОПРЕДЕЛЕНИЕ СКОРОСТИ ЗВУКА В ВОЗДУХЕ МЕТОДОМ СТОЯЧЕЙ ВОЛНЫ Цель работы: ознакомиться с основными характеристиками волновых процессов; изучить условия образования и особенности стоячей волны; определить скорость звука в воздухе метод...
14698. Определение характеристик двухполюсных резистивных элементов 189.5 KB
  ЛАБОРАТОРНАЯ РАБОТА №3 Определение характеристик двухполюсных резистивных элементов Цель работы: Генератор и нагрузка собираются по схеме звезды. Исследуются зависимые и независимые схемы соединения генератора и нагрузки. Объект и средства измерения: