Jest to metoda bardziej wyrafinowana od metody złotego podziału i różni się od niej zmienną wartością \(\displaystyle{ r }\) w każdym przedziale.
Ponadto liczba iteracji \(\displaystyle{ n }\) w tej metodzie zależy od przyjętego apriori błędu \(\displaystyle{ \varepsilon.}\)
Mając daną funkcję unimodalną \(\displaystyle{ f }\) w przedziale \(\displaystyle{ [a_{0}, b_{0}],}\) punkty \(\displaystyle{ c_{k}, d_{k} }\) w \(\displaystyle{ k-}\) tej iteracji obliczamy z układu równań:
\(\displaystyle{ c_{k} = a_{k} + a_{k} + \left(\frac{ F_{n-k-2})}{F_{n-k}}\right)(b_{k}-a_{k}), }\)
\(\displaystyle{ d_{k} = a_{k} +\left( \frac{F_{n-k-1})}{F_{n-k}}\right)(b_{k}-a_{k}). }\)
1. Jeśli \(\displaystyle{ f(c_{k}) \leq f(d_{k}), }\)to nowym przedziałem jest przedział \(\displaystyle{ [a_{k+1}, b_{k+1}] = [a_{k}, d_{k}],}\)
2. Jeśli \(\displaystyle{ f(c_{k}) > f(d_{k}),}\) to nowym przedziałem jest przedział \(\displaystyle{ [a_{k+1}, b_{k+1}] = [c_{k}, b_{k}].}\)
Jeśli współrzędna minimum funkcji \(\displaystyle{ f }\) ma być znaleziona z dokładnością \(\displaystyle{ \varepsilon,}\) tzn.żadamy, aby \(\displaystyle{ \frac{1}{F_{n}} (b_{0}-a_{0}) < \varepsilon, }\) wtedy liczba iteracji \(\displaystyle{ n }\) jest najmiejszą liczbą całkowitą spełniającą nierówność:
\(\displaystyle{ F_{n}> \frac{b_{0}-a_{0}}{\varepsilon}. }\)
\(\displaystyle{ k - }\) tą liczbę Fibonacci znajdujemy ze wzoru Bineta:
\(\displaystyle{ F_{k} = \frac{1}{\sqrt{5}}\left[ \left(\frac{1+\sqrt{5}}{2}\right)^{k} -\left(\frac{1-\sqrt{5}}{2}\right)^{k} \right].}\)
Program w MATLAB
Kod: Zaznacz cały
function fibonacci(f,a,b,tol)
% Funkcja f - unimodalna w przedziale [a,b]
% Metoda Fibonacci znajdowania minimum funkcji w [a,b]
fibonacci(1)=1;
fibonacci(2)=2;
n=2;
while (fibonacci(n) <= (b-a)/tol )
n=n+1;
fibonacci(n)=fibonacci(n-1)+fibonacci(n-2);
end
c = b - (fibonacci(n-1)/fibonacci(n))*(b-a);
d = a + (fibonacci(n-1)/fibonacci(n))*(b-a);
fc = feval(f, c);
fd = feval(f, d);
fprintf('\n')
disp(' Metoda Fibonacci ')
fprintf('\n')
disp('__________________________________________________________________')
disp(' n a c d b f(c) f(d) ')
disp('__________________________________________________________________')
fprintf('\n')
for k = n:-1:3
fprintf('%2.f %10.7f %10.7f %10.7f %10.7f %10.7f %10.7f\n',k,a,c,d,b,fc,fd)
if (fc <= fd)
b = d;
d = c;
fd = fc;
c = a + (fibonacci(k-2)/fibonacci(k))*(b-a);
fc = feval(f, c);
else
a = c;
c = d;
fc = fd;
d = a + (fibonacci(k-1)/fibonacci(k))*(b-a);
fd = feval(f, d);
end
end
xmin=(a+b)/2;
fmin=feval(f,xmin);
fprintf('\n minimum = %14.10f',fmin)
fprintf(' at x = %14.10f',xmin)
Kod: Zaznacz cały
function f=f1(x)
f=cos(x)-sin(x);
Metoda Fibonacci
____________________________________________________________________
n a c d b f(c) f(d)
____________________________________________________________________
17 1.0000000 1.7639319 2.2360681 3.0000000 -1.1733443 -1.4040220
16 1.7639319 2.2360681 2.5278641 3.0000000 -1.4040220 -1.3934259
15 1.7639319 2.0557282 2.2360681 2.5278641 -1.3508548 -1.4040220
14 2.0557282 2.2360681 2.3475244 2.5278641 -1.4040220 -1.4141604
13 2.2360681 2.3475244 2.4164076 2.5278641 -1.4141604 -1.4116506
12 2.2360681 2.3049511 2.3475244 2.4164076 -1.4123572 -1.4141604
11 2.3049511 2.3475244 2.3738341 2.4164076 -1.4141604 -1.4139935
10 2.3049511 2.3312606 2.3475244 2.3738341 -1.4137740 -1.4141604
9 2.3312606 2.3475244 2.3575700 2.3738341 -1.4141604 -1.4142122
8 2.3475244 2.3575700 2.3637886 2.3738341 -1.4142122 -1.4141728
7 2.3475244 2.3537431 2.3575700 2.3637886 -1.4142093 -1.4142122
6 2.3537431 2.3575700 2.3599617 2.3637886 -1.4142122 -1.4142035
5 2.3537431 2.3561349 2.3575700 2.3599617 -1.4142136 -1.4142122
4 2.3537431 2.3551782 2.3561349 2.3575700 -1.4142128 -1.4142136
3 2.3551782 2.3561349 2.3566133 2.3575700 -1.4142136 -1.4142134
minimum = -1.4142134993 at x = 2.3558957369>>