Dokumentacja klasy DichotomousDivision

#include <DichotomousDivision.h>

Diagram dziedziczenia dla DichotomousDivision

Opis szczegółowy

Metoda podziału dychotomicznego.

Metoda optymalizacji w kierunku, w której w każdym kroku zmniejszamy przedział nieoznaczoności o połowę.

Algorytm metody:

Oznaczenia:
$ a $ - lewy kraniec przedziału poszukiwań w danej iteracji
$ b $ - prawy kraniec przedziału poszukiwań w danej iteracji
$ x_l $ - punkt w 1/4 przedziału nieoznaczoności w danej iteracji
$ x_m $ - punkt w 1/2 przedziału nieoznaczoności w danej iteracji
$ x_r $ - punkt w 3/4 przedziału nieoznaczoności w danej iteracji
$ F_l $ - wartość funkcji celu w punkcie $ x_l $ $ F_m $ - wartość funkcji celu w punkcie $ x_m $ $ F_r $ - wartość funkcji celu w punkcie $ x_r $ $ L $ - długość odcinka nieoznaczoności

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

W metodzie podziału dychotomicznego dokładność rozumiana jest jako szerokość ostatniego przedziału nieokreśloności. Wymagamy by była ona mniejsza od $\varepsilon$ .

Krok 1:
Podstawić $ x_m = (a^0+b^0)/2 $ i obliczyć wartość funkcji w tym punkcie. Obliczyć $ L = (b^0-a^0) $ .

Krok 2:
Podstawić $ x_l = a + L/4 $ i $ x_r = b - L/4 $ i obliczyć wartość funkcji w tych punktach.

Krok 3:
Jeśli $ F_l < F_m $ , to:

$\left\{ \begin{array}{lll} b = x_m \\ x_m = x_l \\ F_m = F_l \end{array} \right.$

oraz przejść do kroku 6. Jeśli warunek nie jest spełniony, przejść do kroku 4.

Krok 4:
Jeśli $ F_r < F_m $ , to:

$\left\{ \begin{array}{lll} a = x_m \\ x_m = x_r \\ F_m = F_r \end{array} \right.$

i przejść do kroku 6. Jeśli warunek nie jest spełniony, przejść do kroku 5.

Krok 5:

$\left\{ \begin{array}{ll} a = x_l \\ b = x_r \\ \end{array} \right.$

Krok 6:

$L = (b-a)$

jeśli warunek $|L| \leq 2\varepsilon$ jest spełniony, zakończyć działanie algorytmu. W przeciwnym wypadku przejść do kroku 2.

Algorytm zaimplementowano na podstawie:
Ostanin. A: Metody i algorytmy optymalizacji, Wydawnictwo Politechniki Białostockiej, Białystok, 2003

Zobacz również:: Linesearch

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.