Блок-схема метода деления на три равных отрезка

начало F2<F3 x, f(x) a, b, ε || f(x). x1 := a; x4:=b: Z=1/3 x1:=x2 x4:=x3 x2:=x1+Z(x4-x1); x3:=x4-Z(x4-x1) F2:=f(x2); F3:=f(x3) |x4-x1|£2ε конец x:=(x1+x4)/2 нет да

Программа. Одномерная оптимизация. Метод «на три равных отрезка»

function DATA

global a b eps;

a=-5;

b=5;

eps=0.01;

end

 

function [ fx ] = f(x)

fx=x.^2-5;

end

 

function [ x,fx ] = fun_Odnom_Opt_Tri_Otr(a,b,eps)

x1=a;

x4=b;

for i=1:100

x2=x1+(x4-x1)/3;

x3=x4-(x4-x1)/3;

f2=f(x2);

f3=f(x3);

if f2<f3

   x4=x3;

else

   x1=x2;

end %if

if abs(x4-x1)<=2*eps

   i

   break;

end %if

end %for i

x=(x1+x4)/2;

fx=f(x);       

end % function

 

function GLAV_Odnom_Opt_Tri_Otr

global a b eps x fx;

DATA;

[ x,fx ] = fun_Odnom_Opt_Tri_Otr(a,b,eps);

REPORT;

end

 

function REPORT

global a b eps x fx;

disp('Odnomern Optimizat Tri Otrezka');

disp(' ');

disp('Arguments');

disp(['a = ' num2str(a,'%10.5f') ]);

disp(['b = ' num2str(b,'%10.5f') ]);

disp(['eps = ' num2str(eps,'%10.5f') ]);

disp('Results');

disp(['x = ' num2str(x,'%10.5f') ]);

disp(['fx = ' num2str(fx,'%10.5f') ]);

h=(b-a)/(100);

for i=1:100

if i==1

   xmas(i)=a;

else

   xmas(i)=xmas(i-1)+h;

end %if

fmas(i)=f(xmas(i));

end

disp(' i       x         fx '); 

disp(' ________________________________')

i=0;

for i=1:length(xmas)

xx=xmas(i);

ffx=fmas(i);

disp(sprintf('%10.3f\t%10.3f\t %10.3f',i,xx,ffx));

end %for

plot(xmas,fmas,'r.');

grid on;

xlabel('x');

ylabel('y');

title('Odnomern Optimizat Tri Otrezka');

end

Попробуем увеличить долю сокращения отрезка. Метод деления отрезка пополам.

1) Дан отрезок [a;b] на котором определена функция f(x) и точность e. Надо уточнить точку минимума с заданной точностью. Введём новое обозначение точек x₁=a и x₅=b. Делим отрезок [x_1;x₅] пополам и определяем точку середины x₃=(x₅+x₁)/2 и значение функции F3=f(x ₃).

2) Делим отрезок [x_1;x₃] пополам и определяем точку середины x₂=(x₁+x₃)/2 и значение функции F2=f(x₂). Делим отрезок [x_3;x₅] пополам и определяем точку середины x₄=(x₃+x₅)/2 и значение функции F4=f(x₄). 

3) Определяем новый отрезок, содержащий точку экстремума, сравнив значения функций F2 и F3. Если F2 < F3, то границы нового отрезка определим как: x₁=x₁, x₅=x₃, x₃=x₂ и F3=F2 иначе если F4<F3, то x₁=x₃, x₅=x₅, x₃=x₄ и F3=F4 иначе x₁=x₂, x₅=x₄. Проверяем условие окончания итерационного процесса | x₅-x₁ | £ 2e. Если оно выполняется, то определим решение, как x=x₃ и значение функции в этой точке f(x). Иначе перейдем на пункт 2. Эффективность метода Q≈0,5/2=0,25

Программа. Одномерная оптимизация. Деление на два равных отрезка

function DATA

global a b eps;

a=-5;

b=5;

eps=0.01;

end

 

function [ fx ] = f(x)

fx=x.^2-5;

end

 

function [ x,fx ] = fun_Odnom_Opt_Dva_Otr(a,b,eps)

x1=a;

x5=b;

x3=(a+b)/2;

f3=f(x3);

for i=1:100

if abs(x5-x1)>2*eps

   x2=(x1+x3)/2;

   x4=(x3+x5)/2;

   f2=f(x2);

   f4=f(x4);

   if f2<f3

       x5=x3;

       x3=x2;

   else

       if f4<f3

           x1=x3;

           x3=x4;

           f3=f4;

       else

           x1=x2;

           x5=x4;

       end %if

   end %if

else

   i

   break;

end %if

end %for i

x=x3;

fx=f3;         

end % function

 

function GLAV_Odnom_Opt_Dva_Otr

global a b eps x fx;

DATA;

[ x,fx ] = fun_Odnom_Opt_Dva_Otr(a,b,eps);

REPORT;

end % function

 

function REPORT

global a b eps x fx;

disp('Odnomern Optimizat Dva Otrezka');

disp(' ');

disp('Arguments');

disp(['a = ' num2str(a,'%10.5f') ]);

disp(['b = ' num2str(b,'%10.5f') ]);

disp(['eps = ' num2str(eps,'%10.5f') ]);

disp('Results');

disp(['x = ' num2str(x,'%10.5f') ]);

disp(['fx = ' num2str(fx,'%10.5f') ]);

h=(b-a)/(100);

for i=1:100

if i==1

   xmas(i)=a;

else

   xmas(i)=xmas(i-1)+h;

end %if

fmas(i)=f(xmas(i));

end

disp(' i       x       fx '); 

disp(' ______________________________')

i=0;

for i=1:length(xmas)

xx=xmas(i);

ffx=fmas(i);

disp(sprintf('%10.3f\t%10.3f\t %10.3f',i,xx,ffx));

end %for

plot(xmas,fmas,'r.');

grid on;

xlabel('x');

ylabel('y');

title('Odnomern Optimizat Dva Otrezka');

end % function

Попробуем разбивать отрезок (рис.2.9.1) на такие части, чтобы одну из двух точек и соответствующее значение функции мы могли использовать на следующей итерации. Метод Золотого сечения.

 

D D d d L x1  x2  x3  x4  x4  x3  x2  x1