Metoda złotego podziału

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Metoda złotego podziałunumeryczna metoda optymalizacji jednowymiarowej funkcji celu.

Algorytm ten może być używany przy minimalizacji kierunkowej razem z innymi metodami optymalizacji funkcji wielowymiarowych, takich jak metody gradientowe (np. metoda gradientu prostego, metoda Newtona) lub bezgradientowe (np. metoda Gaussa-Seidela, metoda Powella).

Innymi metodami optymalizacji jednowymiarowej są metoda dychotomii, metoda punktu środkowego, metoda Newtona.

Zadanie optymalizacji jednowymiarowej[edytuj]

Niech dana będzie funkcja celu :

oraz przedział w którym jest unimodalna (jest ciągła i posiada co najwyżej jedno ekstremum lokalne). Zadaniem optymalizacji jednowymiarowej funkcji jest znalezienie jej minimum w przedziale .

Warto podkreślić fakt, iż algorytmy minimalizacji jednowymiarowej działają poprawnie jedynie dla przedziałów w których funkcja jest unimodalna. Jeżeli zadana funkcja nie posiada tej własności, należy znaleźć jej przedziały unimodalności i zastosować opisywaną metodę do każdego z nich.

Algorytm[edytuj]

Idea algorytmu[edytuj]

Metoda złotego podziału. Badane są wartości funkcji w punktach i . Zgodnie z rysunkiem z czego wynika, iż minimum musi znajdować się w przedziale

Funkcja ciągła w przedziale posiada dokładnie jedno minimum x*. Minimum to można znaleźć poprzez kolejne podziały zadanego przedziału. W tym celu należy obliczyć wartości funkcji w dwóch punktach i takich, że , a następnie zbadać ich wielkości:

  • Jeżeli , to szukane minimum znajduje się w przedziale .
  • Jeżeli , to szukane minimum znajduje się w przedziale .

W ten sposób można dowolnie zawężać przedział w którym znajduje się minimum, aż do momentu gdy spełniony zostanie warunek:

dla ustalonej dokładności obliczeń .

Wielkość otrzymanego w wyniku powyższego postępowania przedziału po krokach wynosi: gdzie jest stałym współczynnikiem o który zmniejszana jest wielkość przedziałów w kolejnych krokach algorytmu.

Złoty podział[edytuj]

W metodzie złotego podziału wartość współczynnika jest dobrana w taki sposób, aby przy kolejnych iteracjach wykorzystywać obliczoną w poprzednim kroku wartość funkcji jednej z dwóch próbek ( lub ). Aby osiągnąć powyższą własność, wartość współczynnika musi być równa wartości złotego podziału:

skąd wzięła się nazwa metody.

Strategię obliczania minimum funkcji można zapisać:

  1. Jeśli:
  2. Jeśli to STOP, w przeciwnym wypadku powtórz punkt 2.

Pseudokod[edytuj]

Algorytm można również zapisać przy pomocy poniższego kodu w języku C:

float GoldenRatioMethod( float a, float b )
{
	// współczynnik złotego podziału
	float k = ( sqrt( 5 ) - 1 ) / 2;

	// lewa i prawa próbka
	float xL = b - k * ( b - a );
	float xR = a + k * ( b - a );

	// pętla póki nie zostanie spełniony warunek stopu
	while ( ( b - a ) > EPSILON )
	{
		// porównaj wartości funkcji celu lewej i prawej próbki
		if ( f( xL ) < f( xR ) )
		{
			// wybierz przedział [a, xR]
			b = xR;
			xR = xL;
			xL = b - k * ( b - a );
		}
		else
		{
			// wybierz przedział [xL, b]
			a = xL;
			xL = xR;
			xR = a + k * ( b - a );
		}
	}

	// zwróć wartość środkową przedziału
	return ( a + b ) / 2;
}

Zbieżność metody[edytuj]

Kolejne obliczane przedziały w metodzie złotego podziału są wielkości:

z czego wynika iż zbieżność metody jest liniowa (rząd zbieżności wynosi , zaś współczynnik zbieżności ). Ilość iteracji potrzebna do zawężenia przedziału początkowego do zadanej dokładności wynosi:

Zobacz też[edytuj]

Bibliografia[edytuj]

  1. Fortuna Z., Macukow B., Wąsowski J.: Metody Numeryczne, Wydawnictwa Naukowo-Techniczne, 2006.
  2. Stachurski A., Wierzbicki A.: Podstawy optymalizacji, Oficyna Wydawnicza PW, 1999.

Linki zewnętrzne[edytuj]