Metoda Brenta (optymalizacja)

Metoda Brenta - numeryczna metoda szukania minimum funkcji jednej zmiennej. Podobnie jak metoda złotego podziału nie używa pochodnych a jedynie samych wartości funkcji. Znaczne przyśpieszenie zostało uzyskane przez wyznaczenie przybliżenia punktu minimum za pomocą interpolacji trzech punktów parabolą. Sprawdzane jest czy parabola ma minimum (we wzorze a ma być >0) i następnym punktem jest współrzędna x ekstremum paraboli. Współrzędna x punktu ekstremum paraboli jest zadana wzorem Mając trzy punkty x1,x2 i x3 oraz wartości funkcji y1, y2 i y3 z interpolacji wielomianem Lagrange'a mamy:

W metodzie Brenta aby uprościć wzór na wybrano jeden punkt (np x1) i zamiast pozostałych dwóch stosuje się odległość do pierwszego punktu i najpierw wylicza się odległość ekstremum od pierwszego punktu:

Podstawiając:

Mamy:

Otrzymujemy:

Mając iloczyny oraz obliczymy d.

Poniższy kod został przedstawiony w artykule Brenta[1]. Używa dwóch zmiennych dla tolerancji obliczeń: jedna podawana jest przez użytkownika, druga nie może być za mała i jest równa pierwiastkowi z wartości błędu maszynowego.

Wikibooks:pl:Kody_źródłowe/Szukanie minimów metodą Brenta

Działanie

edytuj

Dla funkcji sinus na przedziale (0;10) i dokładności 1e-16 wyznacza minimum już po 10 krokach, podczas gdy metoda złotego podziału potrzebowała aż 79 kroków.

Zobacz też

edytuj

Przypisy

edytuj