Метод локализации экстремума
Метод локализации представляет собой модификацию метода сканирования. При его использовании существенно снижается количество выполняемых вычислений. Весь интервал поиска, как и в методе сканирования, разбивается на несколько частей, но более крупных размеров (чаще всего на 4 отрезка). Вычисление критерия R(х) осуществляется во всех точках разбиения и на краях интервала. Выбирается значение аргумента, соответствующее наименьшему значению R(х). Новый интервал поиска будет состоять из двух отрезков, на общей границе которых находится найденный минимум. Процедура повторяется.
Абсолютная ошибка в нахождении экстремума при 4 отрезках разбиения равна
,
где s – количество точек, в которых вычисляется значение критерия.
Далее приведен текст программы, позволяющий реализовать описанный выше алгоритм.
function[]=LocalizExtrem1D_170809();
%метод одномерного поиска экстремума для указанной ниже функции
function y=f(x)
%функция вычисляется от одного аргумента и возвращает одно значение
%или от вектора аргумента и возвращает вектор, каждый элемент
%которого вычислен от соответствующего элемента вектора аргумента
y=(x+2).*(x-4); %поэтому перед знаком умножения * стоит точка .
%если не ставить ;точку с запятой в конце строки то произойдет
%вывод на экран
end
%метод одномерного поиска минимума: локализации экстремума
disp('МЕТОД ПОИСКА МИНИМУМА ФУНКЦИИ ЛОКАЛИЗАЦИЕЙ ЭКСТРЕМУМА');
disp('Применен для указанной функции: y=(x+2)*(x-4)');
disp('ВВОД ИСХОДНЫХ ДАННЫХ края диапазона поиска, точность по аргументу ИЛИ по функции ');
function[x,y,mas1x,mas1y,xleft1,xright1,nn]=LocExt1(); % функция локализации экстремума
disp('Одномерная оптимизация методом локализации экстремума');
disp('ЗАДАЧА найти минимум указанной ниже функции ') ;
disp('y=(x+2)*(x-4)');
disp('в интервале, определяемом пользователем')
% ввод диапазона значений аргумента функции
xleft=input('введите левую границу диапазона поиска=');
xright=input('введите правую границу диапазона поиска=');
choice=input('ВОПРОС завершение работы по минимальному изменению функции? Да=1 нет=0');
if choice==0
yeps=input('введите допустимую погрешность по аргументу:');
else
yeps=input('введите минимальное изменение функции:');
end
xleft1=xleft;
xright1=xright;
%создание массива точек
n=5; %5 точек, чтобы было 4 отрезка
nn=1;
TheEnd=0;
while TheEnd==0
dx=(xright-xleft)/4;
masx(1)=xleft;
masy(1)=f(xleft);
disp(' очередная итерация');
for i=2:n
%вычисление значений аргументов и функции от каждого из них
masx(i)=masx(i-1)+dx;
masy(i)=f(masx(i));
string=strcat(‘аргумент:’,num2str(masx(i)),’ функция:’,num2str(masy(i)));
disp(string);
% проверка условий окончания работы функции
if choice==1
if abs(masy(i)-masy(i-1))<yeps
TheEnd=1;
end
else
if abs(xright-xleft)<eps
TheEnd=1;
end
end
end
%поиск минимума
min=masy(1)
num=1;
for i=2:n
if masy(i)<min
min=masy(i);
num=i;
end
end
string=strcat(‘В ДАННОЙ ИТЕРАЦИИ оптимальный аргумент:’,num2str(masx(num)),’ минимальная функция:’,num2str(masy(num)));
disp(string);
%подготовка к новой итерации
if num==1
xright=masx(2);
elseif num==n
xleft=masx(n-1);
else
xleft=masx(num-1);
xright=masx(num+1);
end
%возвращаемый массив точек
for i=1:5
mas1x(nn)=masx(i);
mas1y(nn)=masy(i);
nn=nn+1;
end
end
%возвращаемые значения минимума функции и соответствующего аргумента
x=masx(num);
y=masy(num);
end
disp('Одномерная оптимизация методом локализации экстремума');
disp('ЗАДАЧА найти минимум указанной ниже функции ') ;
disp('y=(x+2)*(x-4)');
disp('в интервале, определяемом пользователем')
%обращение к функции локализации экстремума
[x,y,mas1x,mas1y,xleft1,xright1,nn]=LocExt1();
nn=nn-1;
%выбор оформления вывода на экран
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));
sy=strcat('минимум функции=',num2str(y),' с точностью:',num2str(abs(mas1y(nn)-mas1y(nn-1))));
sn=strcat('выполнено:',num2str(nn),' итераций');
disp(sx) % вывод на экран
disp(sy)
% подготовка к построению графика
h=0.1;
x1=xleft1:h:xright1;
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’,’points by Localisation method’,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.01
очередная итерация
аргумент:-5 функция:27
аргумент:0 функция:-8
аргумент:5 функция:7
аргумент:10 функция:72
В ДАННОЙ ИТЕРАЦИИ оптимальный аргумент:0 минимальная функция:-8
очередная итерация
аргумент:-2.5 функция:3.25
аргумент:0 функция:-8
аргумент:2.5 функция:-6.75
аргумент:5 функция:7
В ДАННОЙ ИТЕРАЦИИ оптимальный аргумент:0 минимальная функция:-8
очередная итерация
аргумент:-1.25 функция:-3.9375
аргумент:0 функция:-8
аргумент:1.25 функция:-8.9375
аргумент:2.5 функция:-6.75
В ДАННОЙ ИТЕРАЦИИ оптимальный аргумент:1.25 минимальная функция:-8.9375
очередная итерация
аргумент:0.625 функция:-8.8594
аргумент:1.25 функция:-8.9375
аргумент:1.875 функция:-8.2344
аргумент:2.5 функция:-6.75
В ДАННОЙ ИТЕРАЦИИ оптимальный аргумент:1.25 минимальная функция:-8.9375
очередная итерация
аргумент:0.9375 функция:-8.9961
аргумент:1.25 функция:-8.9375
аргумент:1.5625 функция:-8.6836
аргумент:1.875 функция:-8.2344
В ДАННОЙ ИТЕРАЦИИ оптимальный аргумент:0.9375 минимальная функция:-8.9961
очередная итерация
аргумент:0.78125 функция:-8.9521
аргумент:0.9375 функция:-8.9961
аргумент:1.0938 функция:-8.9912
аргумент:1.25 функция:-8.9375
В ДАННОЙ ИТЕРАЦИИ оптимальный аргумент:0.9375 минимальная функция:-8.9961
ВОПРОС выводить пошагово как таблицу? Да=1 нет=0 1
ВОПРОС выводить график? Да=1 нет=0 1
вывод результатов
номер= 1 аргумент=-10.000 функция=112.000
номер= 2 аргумент= -5.000 функция= 27.000
номер= 3 аргумент= 0.000 функция= -8.000
номер= 4 аргумент= 5.000 функция= 7.000
номер= 5 аргумент= 10.000 функция= 72.000
номер= 6 аргумент= -5.000 функция= 27.000
номер= 7 аргумент= -2.500 функция= 3.250
номер= 8 аргумент= 0.000 функция= -8.000
номер= 9 аргумент= 2.500 функция= -6.750
номер= 10 аргумент= 5.000 функция= 7.000
номер= 11 аргумент= -2.500 функция= 3.250
номер= 12 аргумент= -1.250 функция= -3.938
номер= 13 аргумент= 0.000 функция= -8.000
номер= 14 аргумент= 1.250 функция= -8.938
номер= 15 аргумент= 2.500 функция= -6.750
номер= 16 аргумент= 0.000 функция= -8.000
номер= 17 аргумент= 0.625 функция= -8.859
номер= 18 аргумент= 1.250 функция= -8.938
номер= 19 аргумент= 1.875 функция= -8.234
номер= 20 аргумент= 2.500 функция= -6.750
номер= 21 аргумент= 0.625 функция= -8.859
номер= 22 аргумент= 0.938 функция= -8.996
номер= 23 аргумент= 1.250 функция= -8.938
номер= 24 аргумент= 1.563 функция= -8.684
номер= 25 аргумент= 1.875 функция= -8.234
номер= 26 аргумент= 0.625 функция= -8.859
номер= 27 аргумент= 0.781 функция= -8.952
номер= 28 аргумент= 0.938 функция= -8.9961
номер= 29 аргумент= 1.094 функция= -8.991
номер= 30 аргумент= 1.250 функция= -8.938
НАЙДЕН МИНИМУМ
оптимальное значение аргумента=0.9375
минимум функции=-8.9961 с точностью:0.053711
Рис. 2.3. Пример вывода на экран при оптимизации методом локализации экстремума
Вывод результатов исполнения той же программы при изменении условий проведения поиска:
МЕТОД ПОИСКА МИНИМУМА ФУНКЦИИ ЛОКАЛИЗАЦИЕЙ ЭКСТРЕМУМА
Применен для указанной функции: y=(x+2)*(x-4)
ВВОД ИСХОДНЫХ ДАННЫХ края диапазона поиска, точность по аргументу ИЛИ по функции
Одномерная оптимизация методом локализации экстремума
ЗАДАЧА найти минимум указанной ниже функции
• y=(x+2)*(x-4)
в интервале, определяемом пользователем
введите левую границу диапазона поиска=-10
введите правую границу диапазона поиска=10
ВОПРОС завершение работы по минимальному изменению функции? Да=1 нет=00
введите допустимую погрешность по аргументу:0.1
очередная итерация
аргумент:-5 функция:27
аргумент:0 функция:-8
аргумент:5 функция:7
аргумент:10 функция:72
В ДАННОЙ ИТЕРАЦИИ оптимальный аргумент:0 минимальная функция:-8
очередная итерация
аргумент:-2.5 функция:3.25
аргумент:0 функция:-8
аргумент:2.5 функция:-6.75
аргумент:5 функция:7
В ДАННОЙ ИТЕРАЦИИ оптимальный аргумент:0 минимальная функция:-8
очередная итерация
аргумент:-1.25 функция:-3.9375
аргумент:0 функция:-8
аргумент:1.25 функция:-8.9375
аргумент:2.5 функция:-6.75
Часть вывода вырезана
В ДАННОЙ ИТЕРАЦИИ оптимальный аргумент:1.0156 минимальная функция:-8.9998
очередная итерация
аргумент:0.97656 функция:-8.9995
аргумент:1.0156 функция:-8.9998
аргумент:1.0547 функция:-8.997
аргумент:1.0938 функция:-8.9912
В ДАННОЙ ИТЕРАЦИИ оптимальный аргумент:1.0156 минимальная функция:-8.9998
очередная итерация
аргумент:0.99609 функция:-9
аргумент:1.0156 функция:-8.9998
аргумент:1.0352 функция:-8.9988
аргумент:1.0547 функция:-8.997
В ДАННОЙ ИТЕРАЦИИ оптимальный аргумент:0.99609 минимальная функция:-9
ВОПРОС выводить пошагово как таблицу? Да=1 нет=0 1
ВОПРОС выводить график? Да=1 нет=0 1
вывод результатов
номер= 1 аргумент=-10.000 функция=112.000
номер= 2 аргумент= -5.000 функция= 27.000
номер= 3 аргумент= 0.000 функция= -8.000
номер= 4 аргумент= 5.000 функция= 7.000
номер= 5 аргумент= 10.000 функция= 72.000
номер= 6 аргумент= -5.000 функция= 27.000
номер= 7 аргумент= -2.500 функция= 3.250
номер= 8 аргумент= 0.000 функция= -8.000
номер= 9 аргумент= 2.500 функция= -6.750
номер= 10 аргумент= 5.000 функция= 7.000
номер= 11 аргумент= -2.500 функция= 3.250
номер= 12 аргумент= -1.250 функция= -3.938
номер= 13 аргумент= 0.000 функция= -8.000
номер= 14 аргумент= 1.250 функция= -8.938
номер= 15 аргумент= 2.500 функция= -6.750
Часть вывода вырезана
номер= 39 аргумент= 1.055 функция= -8.997
номер= 40 аргумент= 1.094 функция= -8.991
номер= 41 аргумент= 0.977 функция= -8.999
номер= 42 аргумент= 0.996 функция= -9.000
номер= 43 аргумент= 1.016 функция= -9.000
номер= 44 аргумент= 1.035 функция= -8.999
номер= 45 аргумент= 1.055 функция= -8.997
НАЙДЕН МИНИМУМ
оптимальное значение аргумента=0.99609
минимум функции=-9 с точностью:0.0017548