Metoda Fibonacci

Dział poświęcony konstrukcjom platońskim i nie tylko...
janusz47
Użytkownik
Użytkownik
Posty: 7910
Rejestracja: 18 mar 2009, o 16:24
Płeć: Mężczyzna
Podziękował: 30 razy
Pomógł: 1670 razy

Metoda Fibonacci

Post autor: janusz47 »

Metoda Fibonacci

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) 
Przykład

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>>
ODPOWIEDZ