Метод обратного половинного шага

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

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

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

Далее приведен текст программы, позволяющий реализовать описанный выше алгоритм.

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 итераций

Метод обратного половинного шага - student2.ru

Рис. 2.4. Пример вывода на экран при применении метода обратного половинного шага

Вывод результатов исполнения той же программы при изменении условий проведения поиска:

Наши рекомендации