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

s cy8ucmVsc1BLAQItABQABgAIAAAAIQClFsKWvQcAACxcAAAOAAAAAAAAAAAAAAAAAC4CAABkcnMv ZTJvRG9jLnhtbFBLAQItABQABgAIAAAAIQDlEJWe3QAAAAUBAAAPAAAAAAAAAAAAAAAAABcKAABk cnMvZG93bnJldi54bWxQSwUGAAAAAAQABADzAAAAIQsAAAAA "> начало 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

 

 

Рис.2.9.1. Разбиение отрезка так, чтобы использовать одну из точек затем еще раз.

 

делим на  Заменяем

Решая получим

Алгоритм.

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

2) Делим отрезок на три части и определяем точку x₂=x₁+Z(x₄-x₁) и точку x₃=x₄-Z(x₄-x₁). Вычисляем значения функции в этих точках F2=f(x₂) F3=f(x₃).

3) Определяем новый отрезок, содержащий точку экстремума, сравнив значения функций F2 и F3. Если F2 < F3, то границы нового отрезка определим как x₁=x₁, x₄=x₃ , x₃=x₂, F3=F2 x₂=x₁+z(x₄-x₁) F2=f(x₂) иначе x₁=x₂, x₄=x₄, x₂=x₃ F2=F3 x₃=x₄-z(x₄-x₁)
F3= f(x₃).

4) Проверяем условие окончания итерационного процесса | x₄-x₁ | £ 2e. Если оно выполняется, то определим решение, как x=(x₄+x₁)/2 и значение функции в этой точке f(x). Иначе перейдем на пункт 3.

Эффективность, как отношение доли сокращения отрезка к количеству вычисления функции на одной итерации: Q=0,3819/1≈0,3819

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

Программа. Одномерная оптимизация. Золотое Сечение.

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_Zolot(a,b,eps)

x1=a;

x4=b;

Z=(3-sqrt(5))/2;

x2=x1+Z*(x4-x1);

x3=x4-Z*(x4-x1);

f2=f(x2);

f3=f(x3);

for i=1:100

if f2<f3

   x4=x3;

   x3=x2;

   f3=f2;

   x2=x1+Z*(x4-x1);

   f2=f(x2);

else

   x1=x2;

   x2=x3;

   f2=f3;

   x3=x4-Z*(x4-x1);

   f3=f(x3);

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_Zolot

global a b eps x fx;

DATA;

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

REPORT;

end % function

 

function REPORT

global a b eps x fx;

disp('Odnomern Optimizat Zolotoe Sechenije');

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 Zolotoe Sechenije');

end % function

Операторами МАТЛАБа можно написать так:

f=inline(‘3*sin(2*x)-1.5*x-1');

[x,y]=fminbnd(f,1.2,-0.4)

Метод с обратным переменным шагом.

1) Дан отрезок [a;b] на котором определена функция f(x) и точность e. Надо уточнить точку минимума с заданной точностью. Определим значения xmin=a и Fmin=f(xmin). Вычислим начальное значение шага h=(b-a)/5.

2) Вычисляем значения x=xmin+h и Fx=f(x).

3) Сравниваем значения функция в точках x и xmin Fx<Fmin. Если условие выполняется, то присвоим xmin = x, а Fmin =Fx, иначе примем h=-h/3

4) Проверяем условие окончания итерационного процесса h£ e. Если оно выполняется, то примем за решение xmin и Fmin. Иначе перейдем на пункт 2.

начало Fx<Fmin xmin, Fmin a, b, ε || f(x). xmin=a; Fmin=f(xmin); h=(b-a)/5 h=-h/3 xmin=x; Fmin=Fx x=xmin+h; Fx=f(x) |3*h|£ε конец нет да

Программа Одномерн Оптим Обратный Переменный шаг

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_Obr_Shag(a,b,eps)

xmin=a;

fmin=f(xmin);

h=(b-a)/5;

for i=1:100

x=xmin+h;

fx=f(x);

if fx<fmin

   xmin=x;

   fmin=fx;

else

   h=-h/3;

end %if

if abs(3*h)<=eps

   i

   break;

end %if

end %for i

end % function

 

function GLAV_Odnom_Opt_Obr_Shag

global a b eps x fx;

DATA;

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

REPORT;

end % function

 

function REPORT

global a b eps x fx;

disp('Odnomern Optimizat Obratnij Peremennij Shag');

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 Obratnij Peremennij Shag');

end % function

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

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

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

Поэтому необходимо заранее выбирать, как будет завершен процесс поиска экстремума.

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

Основным достоинством данного метода является возможность найти глобальный экстремум, а недостатком – большой объем вычислений.

Программа одномерной оптимизации сканирование

function DATA

global xl xr n m;

xl=-5;

xr=5;

n=5;

m=3;

end

 

function [ fx ] = f(x)

fx=x.^2-5;

end

 

function [ x,fx, xl, xr ] = fun_Odnom_Opt_Scanir(xl,xr,n,m)

for i=1:m

h=(xr-xl)/n;

for j=1:n+1

   if j==1

       x(j)=xl;

   else

       x(j)=x(j-1)+h;

   end %if

   y(j)=f(x(j));

end %for j

[ymin,k]=min(y);

xl=x(k)-h;

xr=x(k)+h;

end %for m

x=x(k);

fx=ymin;

end % function

 

function GLAV_Odnom_Opt_Scanir

global xl xr n m x fx;

DATA;

[ x,fx, xl, xr ] = fun_Odnom_Opt_Scanir(xl,xr,n,m);

REPORT;

end

 

function REPORT

global xl xr n x fx;

disp('Odnomern Optimizat Scanirovanie');

disp(' ');

disp('Results');

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

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

h=(xr-xl)/n;

for j=1:n+1

if j==1

   x(j)=xl;

else

   x(j)=x(j-1)+h;

end %if

y(j)=f(x(j));

end % for j

plot(x,y,'r*');

grid on;

xlabel('x');

ylabel('y');

title('Scanirovanije');

end

Метод чисел Фибоначчи.Последовательность чисел Фибоначчи используется в процессе уменьшения шагов поиска при приближении к экстремуму функции. Последовательность чисел Фибоначчи определяется рекуррентным соотношением:   F_n = F_{n – 1} + F_{n – 2};               F ₀ = 1.

Алгоритм поиска минимума функции методом чисел Фибоначчи:

1) По заданной точности поиска Δ, где Δ = (X _max – X _min)/ F_s – абсолютная погрешность при поиске экстремума определяется по формуле, а F_s – число Фибоначчи под номером s, сначала рассчитывается вспомогательное число:   N = (X _max – X _min)/Δ;

2) Находится число Фибоначчи F_s, удовлетворяющее условию:

F_{s – 1} < N ≤ F_s;

3) Определяется минимальный шаг поиска: h _min= (X _max – X _min)/ F_s;

4) Рассчитывается значение критерия R в точке, определяемой соотношением X ₁ = X _min + h _min F_{s – 2};

5) Рассчитывается значение критерия R в точке, определяемой соотношением X ₂ = X ₁ + h _min F_{s – 3};

6) Если R (X ₂) < R (X ₁), то X ₃ = X ₂ + h _min F_{s – 4.}Иначе Х ₃ = X ₁ – h _min F_{s – 4} и в этой точке рассчитывается новое значение R.

Процедура продолжается до тех пор, пока не будут исчерпаны все числа Фибоначчи в убывающей последовательности.