Поиск экстремума функции одной переменной.

При решении задач поиска максимума (минимума) выделяют локальный (с указанием границ) и глобальный максимум (минимум). Локальный минимум функции одной переменной ищет встроенная функция [x, y]=fminbnd(name, a, b, options). В ней:

· name имя М-функции,

· a, b границы поиска,

· options параметры управляющие ходом решения,

· x, y координаты точки минимума.

Для вычисления локального максимума, надо взять функцию name с другим знаком. Для примера, рассмотрим функцию y(x)=x⁴-0.5x³-28x²+140

Сначала найдем минимум на интервале, например, от -4 до -2.

[x,y]=fminbnd(@ext,-4,-2), где @ext обращение к М-функции вычисляющей интересующую нас функцию.

Потом найдем максимум на интервале от -6 до 6, для этого обратимся не к @ext, а к @ext_2, в которой функция y(x) взята с другим знаком, то есть y(x)=-(x⁴-0.5x³-28x²+140). То есть ее минимум будет максимумом исходной функции.

Получим и в том, и в другом случае координаты точки минимума (максимума) на заданном отрезке, что и требовалось.

 

Поиск экстремума функции нескольких переменной.

 

Минимум функции нескольких переменных z=f(x₁, x₂, …, x_n) осуществляет встроенная функция [X,Z]=fminsearch(name, x0, options) где:

· name имя М-функции вычисляющей z=f(x1, x2, …, xn),

· х0 вектор из n элементов, содержащих координаты точки начального приближения,

· options параметры управляющие ходом решения,

· Х вектор из n элементов, содержащий значения переменных, при которых функция z=f(x1, x2, …, xn) минимальна,

· Z это и есть минимальное значение функции.

Например, [X, Z]=fminsearch(@extr, [3 2]); где @extr обращение к М-функции extr, вычисляющей значение интересующей нас функции z=x₁²+x₂²-6x₂-2x₁+11, причем заданы начальные приближения [3 2] для х₁ и х₂ соответственно. В результате получим значения переменных в точке минимума и значение функции в минимуме.

 

Глава 2. Одномерная оптимизация с применением пакета MATLAB

Минимальный шаг по аргументу

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

Минимальное изменение функции

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

 

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

 

Поэтому необходимо заранее выбирать, как будет завершен процесс поиска экстремума.

 

Метод сканирования

Интервал, в котором проводится поиск экстремума, разбивается на равные участки определенной длины, равной шагу поиска. Далее последовательно определяется значение функции во всех точках такого деления, и среди них выбирается наименьшее или наибольшее, в зависимости от того, минимум или максимум ищется. Таким образом, экстремум может быть найден с точностью до шага поиска.

Основным достоинством данного метода является возможность найти глобальный экстремум, а недостатком – большой объем вычислений.

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

Function[]=Scanirovanie1D_030809();

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

function y=f(x)

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

%или от вектора аргумента и возвращает вектор, каждый элемент

%которого вычислен от соответствующего элемента вектора аргумента

y=(x+2).*(x-4); %поэтому перед знаком умножения * стоит точка.

%если не ставить точку с запятой; в конце строки то произойдет

%вывод на экран

end

%метод одномерного поиска экстремума: сканирование

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

% disp означает, что на экран будет выведено сообщение, выделенное апострофом

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

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

function[x,y,masx,masy,xleft,xright,n]=scan1();

% в квадратных скобках указан список возвращаемых переменных.

disp('метод cканирования ')

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

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

% на экран выводится сообщение и том, что нужно ввести исходные данные:

%диапазона значений аргумента функции

disp('исходные данные')

xleft=input('введите левую границу интервала поиска ');

xright=input('введите правую границу интервала поиска ');

h=input('введите допустимую погрешность по аргументу ');

%создание массива точек

n=ceil(abs((xright-xleft)/h)); % определяем число шагов

% функция ceil округляет число в сторону плюс бесконечности

masx(1)=xleft;

masy(1)=f(xleft);

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

for i=2:n

masx(i)=masx(i-1)+h;

masy(i)=f(masx(i));

end

%вывод на экран

for i=1:n

string=strcat(‘шаг номер:’,int2str(i),’ аргумент:’,num2str(masx(i)),’ функция от него:’,num2str(masy(i));

disp(string);

% string – имя переменной, strcat – функция, которая объединяет в одну строку символов все, что указано в круглых скобках, int2str(i) – функция, которая преобразует целое число в строку символов (где в круглых скобках указано число – аргумент функции)

end

% поиск минимума

min=masy(1); % стандартный алгоритм поиска минимума

num=1;

for i=2:n

if masy(i)<min

min=masy(i);

num=i;

end

end

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

x=masx(num);

y=masy(num);

end

%обращение к функции сканирования

[x,y,masx,masy,xleft,xright,n]=scan1();

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

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

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

%вывод таблицы

if choiceTab==1 % Два раза символ «равно» используется в операторе сравнения

disp('вывод результатов');

for i=1:n

%string=strcat(‘номер=’,int2str(i),’ аргумент=’,num2str(masx(i)),’ функция=’,num2str(masy(i)));

%disp(string);

string=sprint(‘номер= %4i\tаргумент= %7.3f\tфункция= %7.3f’,i,masx(i),masy(i));

% где %4i означает 4-х значное целое число с последующим знаком табуляции: \t

% где %7.3f означает десятичную дробь: 7 знаков до запятом, 3 – после с последующим знаком табуляции: \t

disp(string);

end

end

% подготовка к выводу текста

% num2str преобразует число в строку символов

disp('НАЙДЕН МИНИМУМ')

sx=strcat('оптимальное значение аргумента=',num2str(x),' с точностью:',num2str(abs(masx(n)-masx(n-1))));

% sx – имя переменной (строки символов). В данном случае оно не имеет никакого отношения к переменной x

sy=strcat('минимум функции=',num2str(y),' с точностью:',num2str(abs(masy(n)-masy(n-1)));

sn=strcat('выполнено:',num2str(n),' итераций');

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'); % подпись к оси x

ylabel('Y'); % подпись к оси y

text(x,y,’\leftarrow Minimum’);

zeroMas=x1*0;

hold on;

if choiceGraf==1

plot(masx,masy,’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)

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

метод cканирования

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

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

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

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

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

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

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

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

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

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

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

 

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

 

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

шаг номер:16 аргумент:-2.5 функция от него:3.25

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

шаг номер:18 аргумент:-1.5 функция от него:-2.75

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

шаг номер:20 аргумент:-0.5 функция от него:-6.75

шаг номер:21 аргумент:0 функция от него:-8

шаг номер:22 аргумент:0.5 функция от него:-8.75

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

шаг номер:24 аргумент:1.5 функция от него:-8.75

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

шаг номер:26 аргумент:2.5 функция от него:-6.75

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

 

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

шаг номер:36 аргумент:7.5 функция от него:33.25

шаг номер:37 аргумент:8 функция от него:40

шаг номер:38 аргумент:8.5 функция от него:47.25

шаг номер:39 аргумент:9 функция от него:55

шаг номер:40 аргумент:9.5 функция от него:63.25

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

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

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

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

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

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

Рис. 2.1. Пример вывода на экран при применении метода сканирования

 

Метод чисел Фибоначчи

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

F_n = F_{n – 1} + F_{n – 2}; F ₀ = 1.

Алгоритм поиска экстремума (в данном случае минимум) функции методом чисел Фибоначчи:

1) по заданной точности поиска Δ, где Δ = (X _max – X _min)/ F_s – абсолютная погрешность при поиске экстремума определяется по формуле, а F_s – число Фибоначчи под номером s, сначала рассчитывается вспомогательное число: N = (X _max – X _min)/Δ;

2) находится число Фибоначчи F_s, удовлетворяющее условию:

F_{s – 1} < N ≤ F_s;

3) определяется минимальный шаг поиска:

h _min= (X _max – X _min)/ F_s;

4) рассчитывается значение критерия R в точке, определяемой соотношением X ₁ = X _min + h _min F_{s – 2};

5) рассчитывается значение критерия R в точке, определяемой соотношением X ₂ = X ₁ + h _min F_{s – 3};

6) если R (X ₂) < R (X ₁), то X ₃ = X ₂ + h _min F_{s – 4.}

Иначе Х ₃ = X ₁ – h _min F_{s – 4} и в этой точке рассчитывается новое значение R.

Процедура продолжается до тех пор, пока не будут исчерпаны все числа Фибоначчи в убывающей последовательности.

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

Function[]=FibonachiChisla1D_170809();

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

function y=f(x);

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

%значение или от вектора аргумента и возвращает вектор, каждый элемент

%которого вычислен от соответствующего элемента вектора-аргумента y=(x+2).*(x-4);

%поэтому перед знаком умножения *стоит точка.

%если не ставить точку с запятой; в конце строки то произойдет

%вывод на экран

end

%метод одномерного поиска минимума: с использованием чисел Фибоначчи

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

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

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

function [x,y,masx,masy,xleft,xright,dy]=Fib1();

%Ввод исходных данных

disp(Одномерная оптимизация методом чисел Фибоначчи')

disp(ЗАДАЧА найти минимум указанной ниже функции')

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

disp ('в интервале, определяемом пользователем’)

eps=input('точность по аргументу=');

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

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

F(1)=1;

F(2)=2;

s=2;

N=abs(xright-xleft)/eps;

% определяются числа Фибоначчи

while N>F(s)

s=s+1;

F(s)=F(s-1)+F(s-2);

end %конец while

%вывод чисел Фибоначчи на экран

disp(' ЧИСЛА ФИБОНАЧЧИ');

for i=1:s

string=strcat(‘НОМЕР числа Фибоначчи:’,int2str(i),’ ЧИСЛО ФИБОНАЧЧИ:’,int2str(F(i)));

disp(string);

end

disp(‘ВЫВОД ЧИСЕЛ ФИБОНАЧЧИ ЗАВЕРШЕН’);

h=(xright-xleft)/F(s);

x1=xleft+h*F(s-2);

R1=f(x1); % вызов функции y=f(x)

x2=x1+h*F(s-3);

R2=f(x2); % вызов функции y=f(x)

k=s-3;

x3=0;

n=1;

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

while k>1 %основной цикл

k=k-1;

if R2<R1

x3=x2+h*F(k);

else

x3=x1-h*F(k);

end %конец if

%подготовка к следующей итерации

x1=x2;

R1=R2;

x2=x3;

R2=f(x3);

masx(n)=x3;

masy(n)=R2;

n=n+1;

%вывод на экран

string=strcat('число Фибоначчи номер:',int2str(k),' аргумент:',num2str(x3),' функция от него:',num2str(R2));

disp(string);

end %конец while

n=n-1;

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

x=x3;

y=R2;

dy=abs(y-masy(n-1));

end %конец функции

%обращение к функции поиска минимума (числа Фибоначчи)

[x,y,masx,masy,xleft,xright,dy]=Fib1();

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

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

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

%вывод таблицы

if choiceTab==1

disp('вывод результатов');

for i=1:length(masx)

string=print(‘номер= %4i\tаргумент= %7.3f\tфункция= %7.3f’,i,masx(i),masy(i));

disp(string);

end

end

% подготовка к выводу текста

% num2str преобразует число в строку символов

disp('НАЙДЕН МИНИМУМ')

sx=strcat('оптимальное значение аргумента=',num2str(x));

sy=strcat('минимум функции=',num2str(y),' с точностью:',num2str(dy));

sn=strcat('выполнено:',num2str(length(masx)),' итераций');

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'); % подпись к оси x

ylabel('Y'); % подпись к оси y

string=strcat(‘\leftarrow Minimum (‘,num2str(x),’,’,num2str(y),’)’);

text(x,y,string);

zeroMas=x1*0;

hold on;

if choiceGraf==1

plot(masx,masy,’r.’); % график построен

legend(‘plot with minimal step’,’points by Fibonachi 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)

в интервале, определяемом пользователем, точность по аргументу=0.01 левый край интервала поиска=-10, правый край интервала поиска=10

ЧИСЛА ФИБОНАЧЧИ

НОМЕР числа Фибоначчи:1 ЧИСЛО ФИБОНАЧЧИ:1

НОМЕР числа Фибоначчи:2 ЧИСЛО ФИБОНАЧЧИ:2

НОМЕР числа Фибоначчи:3 ЧИСЛО ФИБОНАЧЧИ:3

НОМЕР числа Фибоначчи:4 ЧИСЛО ФИБОНАЧЧИ:5

НОМЕР числа Фибоначчи:5 ЧИСЛО ФИБОНАЧЧИ:8

НОМЕР числа Фибоначчи:6 ЧИСЛО ФИБОНАЧЧИ:13

НОМЕР числа Фибоначчи:7 ЧИСЛО ФИБОНАЧЧИ:21

НОМЕР числа Фибоначчи:8 ЧИСЛО ФИБОНАЧЧИ:34

НОМЕР числа Фибоначчи:9 ЧИСЛО ФИБОНАЧЧИ:55

НОМЕР числа Фибоначчи:10 ЧИСЛО ФИБОНАЧЧИ:89

НОМЕР числа Фибоначчи:11 ЧИСЛО ФИБОНАЧЧИ:144

НОМЕР числа Фибоначчи:12 ЧИСЛО ФИБОНАЧЧИ:233

НОМЕР числа Фибоначчи:13 ЧИСЛО ФИБОНАЧЧИ:377

НОМЕР числа Фибоначчи:14 ЧИСЛО ФИБОНАЧЧИ:610

НОМЕР числа Фибоначчи:15 ЧИСЛО ФИБОНАЧЧИ:987

НОМЕР числа Фибоначчи:16 ЧИСЛО ФИБОНАЧЧИ:1597

НОМЕР числа Фибоначчи:17 ЧИСЛО ФИБОНАЧЧИ:2584

ВЫВОД ЧИСЕЛ ФИБОНАЧЧИ ЗАВЕРШЕН

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

число Фибоначчи номер:13 аргумент:5.2786 функция от него:9.3067

число Фибоначчи номер:12 аргумент:0.55728 функция от него:-8.804

число Фибоначчи номер:11 аргумент:1.6718 функция от него:-8.5486

 

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

число Фибоначчи номер:3 аргумент:0.99845 функция от него:-9

число Фибоначчи номер:2 аргумент:1.0139 функция от него:-8.9998

число Фибоначчи номер:1 аргумент:0.99071 функция от него:-8.9999

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

оптимальное значение аргумента=0.99071

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

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

Рис. 2.2. Пример вывода на экран при оптимизации методом чисел Фибоначчи