делим на Заменяем
Решая получим
Алгоритм.
1) Дан отрезок [a;b] на котором определена функция f(x) и точность e. Надо уточнить точку минимума с заданной точностью. Введём новое обозначение точек x1=a и x4=b и вычислим Z=(3-√5)/2.
2) Делим отрезок на три части и определяем точку x2=x1+Z(x4-x1) и точку x3=x4-Z(x4-x1). Вычисляем значения функции в этих точках F2=f(x2) F3=f(x3).
3) Определяем новый отрезок, содержащий точку экстремума, сравнив значения функций F2 и F3. Если F2 < F3, то границы нового отрезка определим как x1=x1, x4=x3 , x3=x2, F3=F2 x2=x1+z(x4-x1) F2=f(x2) иначе x1=x2, x4=x4, x2=x3 F2=F3 x3=x4-z(x4-x1)
F3= f(x3).
4) Проверяем условие окончания итерационного процесса | x4-x1 | £ 2e. Если оно выполняется, то определим решение, как x=(x4+x1)/2 и значение функции в этой точке f(x). Иначе перейдем на пункт 3.
Эффективность, как отношение доли сокращения отрезка к количеству вычисления функции на одной итерации: Q=0,3819/1≈0,3819
|
Программа. Одномерная оптимизация. Золотое Сечение.
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.
|
Программа Одномерн Оптим Обратный Переменный шаг
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
Метод чисел Фибоначчи.Последовательность чисел Фибоначчи используется в процессе уменьшения шагов поиска при приближении к экстремуму функции. Последовательность чисел Фибоначчи определяется рекуррентным соотношением: Fn = Fn – 1 + Fn – 2; F 0 = 1.
Алгоритм поиска минимума функции методом чисел Фибоначчи:
1) По заданной точности поиска Δ, где Δ = (X max – X min)/ Fs – абсолютная погрешность при поиске экстремума определяется по формуле, а Fs – число Фибоначчи под номером s, сначала рассчитывается вспомогательное число: N = (X max – X min)/Δ;
2) Находится число Фибоначчи Fs, удовлетворяющее условию:
Fs – 1 < N ≤ Fs;
3) Определяется минимальный шаг поиска: h min= (X max – X min)/ Fs;
4) Рассчитывается значение критерия R в точке, определяемой соотношением X 1 = X min + h min Fs – 2;
5) Рассчитывается значение критерия R в точке, определяемой соотношением X 2 = X 1 + h min Fs – 3;
6) Если R (X 2) < R (X 1), то X 3 = X 2 + h min Fs – 4.Иначе Х 3 = X 1 – h min Fs – 4 и в этой точке рассчитывается новое значение R.
Процедура продолжается до тех пор, пока не будут исчерпаны все числа Фибоначчи в убывающей последовательности.