Метод локализации экстремума

Метод локализации представляет собой модификацию метода сканирования. При его использовании существенно снижается количество выполняемых вычислений. Весь интервал поиска, как и в методе сканирования, разбивается на несколько частей, но более крупных размеров (чаще всего на 4 отрезка). Вычисление критерия R(х) осуществляется во всех точках разбиения и на краях интервала. Выбирается значение аргумента, соответствующее наименьшему значению R(х). Новый интервал поиска будет состоять из двух отрезков, на общей границе которых находится найденный минимум. Процедура повторяется.

Абсолютная ошибка в нахождении экстремума при 4 отрезках разбиения равна

Метод локализации экстремума - student2.ru ,

где 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

Метод локализации экстремума - student2.ru

Рис. 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

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