Dokumentacja klasy FibonacciDivision

#include <FibonacciDivision.h>

Diagram dziedziczenia dla FibonacciDivision

SectionLineSearch LineSearch Method Observable Lista wszystkich składowych.

Opis szczegółowy

Metoda Fibonacciego.

Metoda Fibonacciego, opublikowana w 1953 roku przez Kiefera, jest szczególnie przydatna w sytuacjach gdy liczba obliczeń, które możemy wykonać jest ograniczona (np. w systemach czasu rzeczywistego). Metoda daje najmniejszy przedział nieokreśloności przy zadanej z góry liczbie wyliczeń funkcji.

Algorytm metody:

Oznaczenia:
$ a^k $ - lewy kraniec przedziału poszukiwań w k-tej iteracji
$ b^k $ - prawy kraniec przedziału poszukiwań w k-tej iteracji
$ \lambda^k $ - pierwszy punkt wyliczany w k-tej iteracji
$ \mu^k $ - drugi punkt wyliczany w k-tej iteracji
$ F_k $ - k-ty element ciągu Fibonacciego

Dane potrzebne do obliczeń:
$ f(x) $ - minimalizowana funkcja jednej zmiennej
$ a^1 $ - lewy kraniec przedziału poszukiwań
$ b^1 $ - prawy kraniec przedziału poszukiwań
$ \varepsilon $ - wymagana dokładność rozwiązania

W metodzie Fibonacciego dokładność rozumiana jest jako szerokość ostatniego przdziału nieokreśloności. Wymagamy by była ona mniejsza od $ \varepsilon $. Charakterystyczną cechą metody Fibonacciego jest to, że liczbę kroków optymalizacji ustalamy przed rozpoczęciem obliczeń. $ K $ musi spełniać warunek: $ (b^1 - a^1) / F_K \leq \varepsilon $.
Krok 1:
Tworzymy dwa nowe punkty ($ \lambda^k $ i $ \mu^k $) leżące pomiędzy a i b zgodnie ze wzorami:

\[ \lambda^k = a^k + \frac{F_{K-k-1}}{F_{K-k+1}}(b^k - a^k) \]

\[ \mu^k = a^k + \frac{F_{K-k}}{F_{K-k+1}}(b^k - a^k) \]

W nowoutworzonych punktach wyliczamy wartość funkcji.

Krok 2:
Jeśli $ f(\lambda^k) > f(\mu^k)$, to podstawiamy:

\[ \left\{ \begin{array}{llll} a^{k+1} = \lambda^k \\ b_{k+1} = b^k \\ \lambda^{k+1} = \mu^k \\ \mu^{k+1} = a^{k+1} + \frac{F_{K-i}}{F_{K-k+1}}(b^{k+1} - a^{k+1}) \end{array} \right. \]

oraz obliczamy wartość funkcji w punkcie $ \mu^{k+1} $. Następnie przechodzimy do punktu 4.
Jednak gdy $ f(\lambda^k) \leq f(\mu^k) $ przechodzimy do kroku 3.

Krok 3:
Podstawiamy

\[ \left\{ \begin{array}{llll} a^{k+1} = a^k \\ b^{k+1} = \mu^k \\ \mu^{k+1} = \lambda^k \\ \lambda^{k+1} = a^{k+1} + \frac{F_{K-k-1}}{F_{K-k+1}}(b^{k+1} - a^{k+1}) \end{array} \right. \]

i wyliczamy wartość funkcji w punkcie $ \lambda^{k+1} $. Następnie przechdzimy do punktu 4.

Krok 4:
Podstawiamy $ k=k+1 $. Jeśli $ i < K-1 $, to przejść do kroku 2. W przeciwnym wypadku przejść do kroku 5.

Krok 5:

\[ \left\{ \begin{array}{ll} \lambda^K = \lambda^{K-1} \\ \mu^K = \lambda^K + \varepsilon \end{array} \right. \]

Jeśli $ f(\lambda^K) > f(\mu^K) $, to podstawiamy:

\[ \left\{ \begin{array}{ll} a^K = \lambda^K \\ b^K = b^{K-1} \end{array} \right. \]

Jeśli natomiast $ f(\lambda^K) \leq f(\mu^K) $, to podstawiamy:

\[ \left\{ \begin{array}{ll} a^K = a^{K-1} \\ b^K = \lambda^K \end{array} \right. \]

Wynikiem działania metody jest punkt w środku odcinka $ [a, b] $.

Niniejszy dokument został półautomatycznie wycięty z dokumentacji kodu źródłowego programu Eduoptim 2. Pełna dokumentacja dostępna jest wraz ze źródłami bądź osobno w dziale pliki.
Hierarchia klas w programie nie odpowiada klasyfikacji metod optymalizacji.