СКАЧАТЬ:  3-laba-1.zip [58,77 Kb] (cкачиваний: 43)

О Т Ч Е Т

по лабораторной работе

по дисциплине «Оптимизация и оптимальное управление»

на тему: «Метод поиска с использованием градиентных методов»

Цель работы – Ознакомление с поиском экстремума функции с использованием методов дробления шага, наискорейшего спуска и Ньютона.

Постановка задачи:

Дана функция . Необходимо найти корни данного уравнения и уточнить их с помощью методов поиска с использованием методов дробления шага, наискорейшего спуска и Ньютона.

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

Градиентные методы являются численными методами решения задач безусловной минимизации. Исходя из начальной заданной точки . Градиентные методы позволяют получать последовательность согласно условию

                                                      (1)

В общей схеме методов последовательность выбирается по правилу:

Где  - направление изменения; вектор, определяющий направление убывания функции в точке ;

- скаляр, определяющий длину шага вдоль направления  .

Градиентные методы отличаются способами выбора шага . В градиентных методах в качестве направления спуска  выбирается антиградиент функции в точке .

 - методы I порядка.

Существует два способа определения величины шага:

1 – метод с дроблением шага;

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

Метод с дроблением шага

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

Определим алгоритм решения задачи безусловной минимизации с дроблением шага:

Шаг 1 – задается  вычисляются значения функции в точке  и первая производная в этой точке, а также , при этом к=1.

Шаг 2 – принимаем .

Шаг 3 – вычисляется приращение  и новое значение

 Шаг 4 – проверяется условие выбора :

Если оно выполняется, то осуществляется переход к шагу 5. Если условие не выполняется, то производится дробление шага, то есть  и переходим к пункту 3.

Шаг 5 – вычисляется .

Шаг 6 – проверяется условие окончания вычислений:

Если условие выполняется, то вычисления завершаются. Если не выполняются, то переходим к шагу 2.

Блок-схема:

Листинг программы:

program dsh;

uses crt;

var

a,b,e,l,dx1,dx2,x1,x2,md,pf,y: real;

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

begin

f:= x1*x1-4*x2*x2-5*x1+3*x2+1

end;

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

begin

f1:=2*x1-5 end;

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

begin

f2:=-8*x2+3 end;

label m1;

begin clrscr;

writeln('задайте последовательно a,b,e,x1,x2');

readln(a,b,e,x1,x2);

l:=a;

m1:

md:=sqrt(sqr(f1(x1,x2))+sqr(f2(x1,x2)));

pf:=f(x1,x2);

dx1:=-l*f1(x1,x2)/md;

dx2:=-l*f2(x1,x2)/md;

x1:=x1+dx1;

x2:=x2+dx2;

if f(x1,x2)>pf then begin l:=l*b; goto m1 end;

if md<e then writeln(f(x1,x2):5:3) else

goto m1;

readln

end.

Метод Ньютона

Метод Ньютона так же, как и градиентные методы, относится к методам спуска и предназначен для численного решения задач безусловной минимизации. Алгоритм решения задачи методом Ньютона заключается в следующем:

Шаг 1 – задаются , вычисляются ,, , к=1.

Шаг 2 – вычисляется вторая производная .

Шаг 3 – определяется .

Шаг 4 – вычисляются:

Шаг 5 – окончание поиска, проверка условия:

Если условие выполняется, то вычисления завершаются. Если условие не выполняется, тогда к=к+1 и переходит к пункту 2.

Блок-схема:

Листинг программы:

program dsh;

uses crt;

var

A: array[1..2,1..2] of real;

B: array[1..2] of real;

d,e,dx1,dx2,x1,x2,md,pf,y: real;

i,j: integer;

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

begin

f:= x2*x2*x2+x1*x2+2*x1*x1-x1-5*x2+3

end;

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

begin

f1:= x2+4*x1-1

end;

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

begin

f2:= 6*x2*x2+x1-5

end;

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

begin

f11:=4

end;

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

begin

f22:=12*x2

end;

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

begin

f12:=1

end;

label m1;

begin

clrscr;

writeln('задайте последовательно e,x1,x2');

readln(e,x1,x2);

m1:

md:=sqrt(sqr(f1(x1,x2))+sqr(f2(x1,x2)));

if md<=e then

writeln('f(x1,x2)= ',f(x1,x2):5:3)

else begin

A[1,1]:=f11(x1,x2);

A[1,2]:=f12(x1,x2);

A[2,1]:=f12(x1,x2);

A[2,2]:=f22(x1,x2);

d:=1/(A[1,1]*A[2,2]-A[1,2]*A[2,1]);

A[1,1]:=f22(x1,x2)*d;

A[1,2]:=-f12(x1,x2)*d;

A[2,1]:=-f12(x1,x2)*d;

A[2,2]:=f11(x1,x2)*d;

B[1]:=-f1(x1,x2);

B[2]:=-f2(x1,x2);

dx1:=B[1]*A[1,1]+B[2]*A[2,1];

dx2:=B[1]*A[1,2]+B[2]*A[2,2];

x1:=x1+dx1;

x2:=x2+dx2;

goto m1

end;

readln

end.

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

В данном случае на каждой итерации шаг  выбирается из условия минимума функции f(x) в направлении движения:

Условие нахождения h:

Алгоритм:

Шаг 1: задается , вычисляются , ,  при к=1

Шаг 2: определяется

Шаг 3: вычисляются , , :

Шаг 4: проверяется условие окончания вычислений:

Если условие не выполняется, то тогда к=к+1 и осуществляется переход к пункту 2.

Блок-схема:

Листинг программы:

program nsp;

uses crt;

var e,l,dx1,dx2,x1,x2,md: real;

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

begin

f:= 3*x1*x1+2*x2*x2+6*x1+2*x2

end;

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

begin

f1:= 6*x1+6

end;

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

begin

f2:=4*x2+2

end;

label m1;

begin

clrscr;

writeln('задайте последовательно e,x1,x2');

readln(e,x1,x2);

l:=1/3;

m1:

md:=sqrt(sqr(f1(x1,x2))+sqr(f2(x1,x2)));

dx1:=-l*f1(x1,x2);

dx2:=-l*f2(x1,x2);

x1:=x1+dx1;

x2:=x2+dx2;

if md<e then writeln(f(x1,x2):5:3) else

goto m1;

readln

end.