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

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

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. Пример вывода на экран при оптимизации методом чисел Фибоначчи