Метод обратного половинного шага
Для вычисления минимума задается интервал поиска и шаг поиска. На одном краю интервала поиска (в начале) вычисляется функция. После совершения шага по аргументу, опять вычисляется функция.
Если новое значение функции меньше предыдущего, то делается следующий шаг. Если достигнут конец интервала поиска, а функция не превышала первоначальное значение, то считаем, что там минимума нет.
Если очередное значение функции больше предыдущего, то знак шага меняется на противоположный (идем в обратную сторону по аргументу), а его величина уменьшается в несколько раз (оптимально – в два раза). Метод позволяет найти первый локальный экстремум. Следует отметить, что если задать большой шаг, то первый локальный экстремум можно не обнаружить. Это – недостаток данного метода.
Далее приведен текст программы, позволяющий реализовать описанный выше алгоритм.
Function[]=ObratnPolovShag1D_170809();
function y=f(x)
y=(x+2).*(x-4);
end
disp('МЕТОД ПОИСКА МИНИМУМА ФУНКЦИИ ОБРАТНЫМ ПОЛОВИННЫМ ШАГОМ');
disp('применен для указанной функции: y=(x+2)*(x-4)');
disp('ВВОД ИСХОДНЫХ ДАННЫХ края диапазона поиска, точность по аргументу ИЛИ по функции ');
function[x,y,mas1x,mas1y,xleft,xright,nn]=ObrShag1()
disp('метод обратного половинного шага')
disp('для одномерного поиска экстремума указанной ниже функции')
disp('y=(x+2)*(x-4)')
% ввод диапазона значений аргумента функции
disp('исходные данные')
xleft=input('введите левую границу интервала поиска ');
xright=input('введите правую границу интервала поиска ');
choice=input('ВОПРОС завершение работы по минимальному изменению функции? Да=1 нет=0');
if choice==0
eps=input('введите допустимую погрешность по аргументу:');
else
yeps=input('введите минимальное изменение функции:');
end
%вычисляем размер шага
dx1=(xright-xleft)/100;
if choice==1
dx2=dx1;
else
dx2=eps*10;
end
if dx1<dx2
dx=dx1;
else
dx=dx2;
end
nn=1;
%создание массива точек
n=1;
masx(1)=xleft;
masy(1)=f(masx(1));
TheEnd=0;
while TheEnd==0
n=n+1;
masx(n)=masx(n-1)+dx;
masy(n)=f(masx(n));
string=strcat(‘аргумент:’,num2str(masx(n)),’ функция:’,num2str(masy(n)));
disp(string);
%возвращаемый массив точек
mas1x(nn)=masx(n);
mas1y(nn)=masy(n);
nn=nn+1;
% если пройден весь интервал поиска, то конец работы функции
if masx(n)>xright
disp(‘нет минимума’);
break;
end
% проверка условий окончания работы функции
if choice==1
if abs(masy(n)-masy(n-1))<yeps
TheEnd=1;
disp(‘yeps’);
end
else
if abs(masx(n)-masx(n-1))<eps
TheEnd=1;
disp('xeps');
end
end
% если пройден минимум, то
if masy(n)>masy(n-1)
%обратно с половинным шагом
dx=-dx/2
masx(1)=masx(n);
masy(1)=masy(n);
n=1;
end
end % конец while
%возвращаемые значения
x=masx(n);
y=masy(n);
nn=nn-1;
end
%обращение к функции поиска обратным половинным шагом
[x,y,mas1x,mas1y,xleft,xright,nn]=ObrShag1();
%выбор оформления вывода на экран
choiceTab=input('ВОПРОС выводить пошагово как таблицу? Да=1 нет=0 ');
choiceGraf=input('ВОПРОС выводить график? Да=1 нет=0 ');
%вывод таблицы
if choiceTab==1
disp('вывод результатов');
for i=1:nn
string=print(‘номер= %4i\tаргумент= %7.3f\tфункция= %7.3f’,i,mas1x(i),mas1y(i));
disp(string);
end
end
% подготовка к выводу текста
% num2str преобразует число в строку символов
disp('НАЙДЕН МИНИМУМ')
sx=strcat('оптимальное значение аргумента=',num2str(x),' с точностью (по аргументу):',num2str(abs(mas1x(nn)-mas1x(nn-1))));
sy=strcat('минимум функции=',num2str(y),' с точностью (по функции):’,num2str(abs(mas1y(nn)-mas1y(nn-1))));
sn=strcat(‘выполнено:’,num2str(nn),’ итераций’);
disp(sx); % вывод на экран
disp(sy);
disp(sn);
% подготовка к построению графика
h=0.1;
x1=xleft:h:xright;
y1=f(x1);
plot(x1,y1,’k-‘);
grid on;
title('y=(x+2)(x-4)');
xlabel('X');
ylabel('Y');
text(x,y,’\leftarrow Minimum’);
zeroMas=x1*0;
hold on;
if choiceGraf==1
plot(mas1x,mas1y,’r.’);
legend(‘plot with minimal step’,’plot with your step’,0);
else
legend(‘plot with minimal step’,0);
end
hold on;
plot(x1,zeroMas,’k-‘,zeroMas,y1,’k-‘); % построены оси
end
После выполнения этой программы пользователь видит на экране соответствующий текст, вводит нужные значения и получает график:
МЕТОД ПОИСКА МИНИМУМА ФУНКЦИИ ОБРАТНЫМ ПОЛОВИННЫМ ШАГОМ
Применен для указанной функции: y=(x+2)*(x-4)
ВВОД ИСХОДНЫХ ДАННЫХ края диапазона поиска, точность по аргументу ИЛИ по функции
метод обратного половинного шага
для одномерного поиска экстремума указанной ниже функции
y=(x+2)*(x-4)
исходные данные
введите левую границу интервала поиска -10
введите правую границу интервала поиска 10
ВОПРОС завершение работы по минимальному изменению функции? Да=1 нет=01
введите минимальное изменение функции:0.1
аргумент:-9.8 функция:107.64
аргумент:-9.6 функция:103.36
аргумент:-9.4 функция:99.16
аргумент:-9.2 функция:95.04
аргумент:-9 функция:91
аргумент:-8.8 функция:87.04
аргумент:-8.6 функция:83.16
аргумент:-8.4 функция:79.36
аргумент:-8.2 функция:75.64
аргумент:-8 функция:72
Часть вывода вырезана
аргумент:-1.4 функция:-3.24
аргумент:-1.2 функция:-4.16
аргумент:-1 функция:-5
аргумент:-0.8 функция:-5.76
аргумент:-0.6 функция:-6.44
аргумент:-0.4 функция:-7.04
аргумент:-0.2 функция:-7.56
аргумент:-2.0539e-015 функция:-8
аргумент:0.2 функция:-8.36
аргумент:0.4 функция:-8.64
аргумент:0.6 функция:-8.84
аргумент:0.8 функция:-8.96
аргумент:1 функция:-9
yeps % Это означает, что функция прервала свою работу при достожении минимального изменения по у
ВОПРОС выводить пошагово как таблицу? Да=1 нет=0 1
ВОПРОС выводить график? Да=1 нет=0 1
вывод результатов
номер= 1 аргумент= -9.800 функция=107.640
номер= 2 аргумент= -9.600 функция=103.360
номер= 3 аргумент= -9.400 функция= 99.160
Часть вывода вырезана
номер= 48 аргумент= -0.400 функция= -7.040
номер= 49 аргумент= -0.200 функция= -7.560
номер= 50 аргумент= -0.000 функция= -8.000
номер= 51 аргумент= 0.200 функция= -8.360
номер= 52 аргумент= 0.400 функция= -8.640
номер= 53 аргумент= 0.600 функция= -8.840
номер= 54 аргумент= 0.800 функция= -8.960
номер= 55 аргумент= 1.000 функция= -9.000
НАЙДЕН МИНИМУМ
оптимальное значение аргумента=1 с точностью (по аргументу):0.2
минимум функции=-9 с точностью (по функции):0.04
выполнено:55 итераций
Рис. 2.4. Пример вывода на экран при применении метода обратного половинного шага
Вывод результатов исполнения той же программы при изменении условий проведения поиска: