50626

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

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

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

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

Русский

2014-01-27

54 KB

59 чел.

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

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


 

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

69419. Графічне подання різних видів обчислювальних процесів 21.85 KB
  Схематично лінійний алгоритм зображується так: Початок b c у = а bс y Кінець Початок b c у = а bс y Кінець Введення значень b c Обчислення значень у Друкування значення у Розгалужений алгоритм описує процес обчислення такого виразу: Схематично розгалужений алгоритм...
69420. Шпальта: введення та редагування тексту. Вікно діалогу “Колонки” 147.35 KB
  Word дає змогу створювати документи двома способами: або з допомогою шаблону Обычный (Normal.dot), або з допомогою шаблону, який укаже користувач. На початковій стадії оволодіння технологією роботи з Word користувач, звичайно, створює документи, які задовольняє шаблон...
69421. Вставка в текст спеціальних символів. Створення і вставка автотексту. Вставка в документ Word діаграм 49.84 KB
  Для вставлення тих символів, аналогів яких нема на клавіатурі потрібно вибрати пункт меню Вставка, Символ. У таблиці символів вибираємо потрібний символ і натискаємо Вставить. Над таблицею символів розташована таблиця шрифтів.
69422. Друк документів в Word. Стилі документів 99.29 KB
  Для отримання твердої копії можна скористатись кнопкою піктографічного меню яка забезпечує швидкий спосіб друкування але має суттєвий недолік друкується увесь документ або виконати команду File Файл Print Печать.
69423. Робота з об’єктами в текстовому редакторі Word. Форматування об’єктів 113.32 KB
  У Word передбачені опції для форматування різноманітних елементів документа символів абзаців сторінок і розділів. При форматуванні символа будьякі типи форматування будуть застосовуватися до всіх символів виділеної частини тексту чи до всіх символів що будуть введені після...
69424. Сортування і фільтрація даних в Excel 181.22 KB
  Сортування може відбуватися за двома напрямками: за збільшенням значення ключової ознаки; за зменшенням значення ключової ознаки. Сортування даних по одній графі Наприклад необхідно впорядкувати список студентів за алфавітом.
69425. Послуги комп’ютерних мереж. Світова глобальна комп’ютерна мережа Internet 30.77 KB
  Internet утворює немовби ядро яке забезпечує взаємодію інформаційних мереж що належать різним установам у всьому світі. Таким чином Internet можна розглядати як деякий глобальний інформаційний простір.
69426. Загальна схема ПЗ. Операційні системи 17.36 KB
  Команди всіх операційних систем призначені для створення знищення копіювання переміщення файлів тощо. Операційна система стежить щоб ці помилки не були фатальними ні для файлів користувача ні для комп’ютерної системи вцілому.
69427. Структура MS-DOS. Особливості організації файлової системи 18.85 KB
  Операційна система виконує такі функції: керування пам’яттю введенням-виведенням файловою системою взаємодією процесів; захист інформації; облік використання ресурсів оброблення командної мови; виявлення різних моментів що виникають у процесі роботи і відповідну реакцію...