Метод поиска минимума функции обратным половинным шагом

Применен для указанной функции: y=(x+2)*(x-4)

ВВОД ИСХОДНЫХ ДАННЫХ края диапазона поиска, точность по аргументу ИЛИ по функции

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

для одномерного поиска экстремума указанной ниже функции

y=(x+2)*(x-4)

исходные данные

введите левую границу интервала поиска -10

введите правую границу интервала поиска 10

ВОПРОС завершение работы по минимальному изменению функции? Да=1 нет=00

введите допустимую погрешность по аргументу:0.1

аргумент:-9.8 функция:107.64

аргумент:-9.6 функция:103.36

аргумент:-9.4 функция:99.16

аргумент:-9.2 функция:95.04

аргумент:-9 функция:91

аргумент:-8.8 функция:87.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

аргумент:1.2 функция:-8.96

В отличии от приведенного выше примера, работа при достижении минимального изменения функции завершена не была, поэтому произошла смена знака шага по аргументу и его уменьшение вдвое.

dx = -0.1000

аргумент:1.1 функция:-8.99

аргумент:1 функция:-9

xeps

ВОПРОС выводить пошагово как таблицу? Да=1 нет=0 1

ВОПРОС выводить график? Да=1 нет=0 1

вывод результатов

номер= 1 аргумент= -9.800 функция=107.640

номер= 2 аргумент= -9.600 функция=103.360

номер= 3 аргумент= -9.400 функция= 99.160

номер= 4 аргумент= -9.200 функция= 95.040

номер= 5 аргумент= -9.000 функция= 91.000

номер= 6 аргумент= -8.800 функция= 87.040

Часть вывода вырезана

номер= 54 аргумент= 0.800 функция= -8.960

номер= 55 аргумент= 1.000 функция= -9.000

номер= 56 аргумент= 1.200 функция= -8.960

номер= 57 аргумент= 1.100 функция= -8.990

номер= 58 аргумент= 1.000 функция= -9.000

НАЙДЕН МИНИМУМ

оптимальное значение аргумента=1 с точностью (по аргументу):0.1

минимум функции=-9 с точностью (по функции):0.01

выполнено:58 итераций

Метод золотого сечения

В основе этого метода лежит правило геометрического отношения или золотого сечения:

метод поиска минимума функции обратным половинным шагом - student2.ru или метод поиска минимума функции обратным половинным шагом - student2.ru ,

где метод поиска минимума функции обратным половинным шагом - student2.ru – длина всего отрезка; метод поиска минимума функции обратным половинным шагом - student2.ru – длина его большей части; метод поиска минимума функции обратным половинным шагом - student2.ru – длина его меньшей части.

метод поиска минимума функции обратным половинным шагом - student2.ru

Рис. 2.5. Графическая иллюстрация правила золотого сечения

В соответствии с этим правилом определяются точки исследуемого интервала, в которых необходимо производить вычисление функции метод поиска минимума функции обратным половинным шагом - student2.ru .

Из рис. 2.5 следует, что:

метод поиска минимума функции обратным половинным шагом - student2.ru . (1)

Тогда, подставляя в (1) соотношение (2) получим:

метод поиска минимума функции обратным половинным шагом - student2.ru . (2)

Обозначив отношение метод поиска минимума функции обратным половинным шагом - student2.ru и подставив его в (2), получим:

метод поиска минимума функции обратным половинным шагом - student2.ru , (3)

откуда следует:

метод поиска минимума функции обратным половинным шагом - student2.ru . (4)

Решение этого уравнения дает:

метод поиска минимума функции обратным половинным шагом - student2.ru . (5)

Поскольку метод поиска минимума функции обратным половинным шагом - student2.ru , то его значение принимается равным:

метод поиска минимума функции обратным половинным шагом - student2.ru . (6)

R
х3
х1
х2
х4
хmin
хmax

Рис. 2.6. Графическая иллюстрация метода золотого сечения

На исследуемом интервале (рис. 2.6) определяются две точки X1 = Xmin + k²a и X2 = Xmin + ka, где а – длина интервала [Xmin, Xmax]. Находим значения функции в точках Xmin, X1, X2, Xmax. Если наименьшее значение R будет соответствовать точке X1, то новым интервалом поиска будет [Xmin, X2], и на этом интервале находится новая точка X3 = Xmin + k²a, где ka – длина интервала [Xmin, X2] Если наименьшее значение R будет в соответствовать точке X2, то новым интервалом поиска будет [X1, Xmax], и на этом интервале находится новая точка X4 = X1 + ka, где ka – длина интервала [X1, Xmax]. Затем процедура повторяется. Абсолютная ошибка в определении экстремума после s вычислений будет вычисляться по формуле:

метод поиска минимума функции обратным половинным шагом - student2.ru . (7)

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

function[]=ZolotSechenie1D_170809();

function y=f(x)

y=(x+2).*(x-4);

end

disp('МЕТОД ПОИСКА МИНИМУМА ФУНКЦИИ МЕТОДОМ ЗОЛОТОГО СЕЧЕНИЯ');

disp('Применен для указанной функции: y=(x+2)*(x-4)');

disp('ВВОД ИСХОДНЫХ ДАННЫХ точность по аргументу, края диапазона поиска');

function [x,y,xleft1,xright1,nn]=ZolS1()

eps=input('точность=');

xleft=input('левый край поиска=');

xright=input('правый край поиска=');

xleft1=xleft; %возвращаемые значения

xright1=xright; %возвращаемые значения

k=(sqrt(5)-1)/2; %число К, показывающее отношения длин отрезков

x1=xleft+k*k*abs(xleft-xright);

x2=xleft+k*abs(xleft-xright);

z=0;

j=0;

nn=1;

disp('ВЫВОД ПРОМЕЖУТОЧНЫХ РЕЗУЛЬТАТОВ ПОШАГОВО ');

while abs(xleft-xright)>eps

R1=f(x1);

R2=f(x2);

if R1<R2 % если минимум в точке Х1

z=x1; % для возвращения значения минимума

j=R1; % для возвращения значения минимума

%для следующей итерации подготавливаем интервал с четырьмя точками по правилу золотого сечения вместо xleft,x1,x2

xright=x2;

x2=x1;

x1=xleft+k*k*abs(xleft-xright);

%возвращаемые значения

mas1x(nn)=x1;

mas1y(nn)=R1;

else %если минимум в точке Х2

z=x2;

j=R2;

%для следующей итерации подготавливаем интервал с четырьмя точками по правилу золотого сечения вместо x1,x2,xright

xleft=x1;

x1=x2;

x2=xleft+k*abs(xleft-xright);

%возвращаемые значения

mas1x(nn)=x2;

mas1y(nn)=R2;

end %конец if

%вывод на экран минимума функции и соответствующего аргумента соответствующего аргумента для выполнения итерации

string=strcat('шаг номер:',int2str(nn),' аргумент:',num2str(mas1x(nn)),' функция от него:',num2str(mas1y(nn)));

disp(string);

nn=nn+1;

end %конец while

%возвращаемые значения найденного минимума и возвращения значения

x=z;

y=j;

nn=nn-1;

end

%обращение к функции методом золотого сечения

[x,y,xleft1,xright1,nn]=ZolS1();

%выбор оформления вывода на экран

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

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=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 Gold 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)

ВВОД ИСХОДНЫХ ДАННЫХ точность по аргументу, края диапазона поиска

точность=0.1

левый край поиска=-10

правый край поиска=10

ВЫВОД ПРОМЕЖУТОЧНЫХ РЕЗУЛЬТАТОВ ПОШАГОВО

шаг номер:1 аргумент:5.2786 функция от него:-7.1486

шаг номер:2 аргумент:0.55728 функция от него:-7.1486

шаг номер:3 аргумент:-0.55728 функция от него:-8.804

шаг номер:4 аргумент:1.2461 функция от него:-8.804

Часть вывода вырезана

шаг номер:9 аргумент:0.92089 функция от него:-8.9997

шаг номер:10 аргумент:1.0214 функция от него:-8.9997

шаг номер:11 аргумент:0.95928 функция от него:-8.9997

шаг номер:12 аргумент:0.99767 функция от него:-8.9997

ВОПРОС выводить пошагово как таблицу? Да=1 нет=0 1

ВОПРОС выводить график? Да=1 нет=0 1

вывод результатов

номер= 1 аргумент= 5.279 функция= -7.149

номер= 2 аргумент= 0.557 функция= -7.149

номер= 3 аргумент= -0.557 функция= -8.804

номер= 4 аргумент= 1.246 функция= -8.804

номер= 5 аргумент= 1.672 функция= -8.939

номер= 6 аргумент= 0.983 функция= -8.939

номер= 7 аргумент= 0.820 функция= -9.000

номер= 8 аргумент= 1.084 функция= -9.000

номер= 9 аргумент= 0.921 функция= -9.000

номер= 10 аргумент= 1.021 функция= -9.000

номер= 11 аргумент= 0.959 функция= -9.000

номер= 12 аргумент= 0.998 функция= -9.000

НАЙДЕН МИНИМУМ

оптимальное значение аргумента=0.98301 с точностью:0.038388

минимум функции=-8.9997 с точностью:0

выполнено:12 итераций

метод поиска минимума функции обратным половинным шагом - student2.ru

Рис. 2.7. Пример применения метода золотого сечения

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