Скачать:  mns.zip [96,61 Kb] (cкачиваний: 15)

КАФЕДРА АИТ

ЛАБОРАТОРНАЯ РАБОТА №3

ПО ДИСЦИПЛИНЕ «МОДЕЛИРОВАНИЕ СИСТЕМ»

НА ТЕМУ:

«МЕТОД НАИСКОРЕЙШЕГО СПУСКА»

Градиентные методы.

Во всех градиентных методах вычисляются и анализируются производные целевой функции R(x). Если аналитический вид целевой функции R(x) известен, то вычисление производных не составляет особого труда. Если же зависимость в явном аналитическом виде записать нельзя или же аналитические выражения для производных получаются слишком сложными для практического использования в расчетах, то единственным способом определения производных является численный метод.

К градиентным методам 1 порядка относят следующие методы:

1) метод релаксации;

2) метод градиента;

3) метод наискорейшего спуска (или крутого восхождения).

Метод наискорейшего спуска.

Этот метод сочетает в себе основные идеи методов релаксации и градиента. Алгоритм метода заключается в следующем. После нахождения в начальной точке градиента оптимизируемой функции выполняется первый шаг спуска (восхождения). Если значение функции в результате этого шага уменьшилось, то производится следующий шаг в том же направлении. И так до тех пор, пока в этом направлении не будет найден минимум. После чего вычисляется градиент и определяется новое направление наибыстрейшего убывания целевой функции.

Рис.1. Характер движения к оптимуму в методе наискорейшего спуска.

Критерием окончания поиска является условие grad(x)=0

Важной особенностью метода наискорейшего спуска является то, что при его применении каждое новое направление движения к оптимуму ортогонально предшествующему. Это объясняется тем, что движение в одном направлении производится до тех пор, пока направление движения не окажется касательным к какой-либо линии постоянного уровня (см. первый в этой части рис.). Тем самым, метод наискорейшего спуска имеет сходство с методом релаксации, для которого направление также ортогонально предшествующему, однако в отличие от метода релаксации скорость сходимости к оптимуму не зависит от ориентации системы координат.

В качестве критерия окончания поиска может использоваться следующее условие:

где - координаты начальной и конечной точек последнего отрезка спуска (второй в этой части рис.1).

Этот же критерий может использоваться в сочетании с контролем значений целевой функции в точках :

Рис.2. К определению окончания поиска в методе наискорейшего спуска.

Program MNS;

label l;

label n;

var x1,x2,e,y,z,q2:real;

function d1(x1,x2:real):real;

begin

d1:=2*x1+x2

end;

function d2(x1,x2:real):real;

begin

d2:=4*x2+x1

end;

function k(d1,d2:real):real;

begin

k:=d1/d2

end;

function q1(k:real):real;

begin

q1:=k*q2

end;

begin

write ('x1=');

read (x1);

write ('x2=');

read (x2);

write ('e=');

read (e);

q2:=0.5;

y:=x1*x1+2*x2*x2+x1*x2;

l: z:=y;

n: if d1(x1,x2)>0 then x1:=x1-q1(k(d1(x1,x2),d2(x1,x2))) else x1:=x1+q1(k(d1(x1,x2),d2(x1,x2)));

if d2(x1,x2)>0 then x2:=x2-q2 else x2:=x2+q2;

if abs(y-z)<=e then write (y,x1,x2) else

begin if y<z then goto l else

begin y:=z;

if q2>=0.1 then q2:=q2-0.2 else q2:=q2/2;

goto n;

end;

end;

end.

Проверка верности полученного минимума целевой функции может быть произведена путем построения графика целевой функции в пространстве, что позволяет уравнение функции, зависящей от 2-х переменных.

Покажем на координатной плоскости ход поиска минимума (штриховой линией обозначены ложные ходы, ортогональность искажена неравномерными шкалами осей):