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 $ax^{2}+bx+c$ 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 ${\frac {-b}{2a}}$ Mając trzy punkty x₁,x₂ i x₃ oraz wartości funkcji y₁, y₂ i y₃ z interpolacji wielomianem Lagrange'a mamy:

$y_{1}*{\frac {(x-x_{2})*(x-x_{3})}{(x_{1}-x_{2})*(x_{1}-x_{3})}}+y_{2}*{\frac {(x-x_{1})*(x-x_{3})}{(x_{2}-x_{1})*(x_{2}-x_{3})}}+y_{3}*{\frac {(x-x_{1})*(x-x_{2})}{(x_{3}-x_{1})*(x_{3}-x_{2})}}$

W metodzie Brenta aby uprościć wzór na ${\frac {-b}{2a}}$ wybrano jeden punkt (np x₁) i zamiast pozostałych dwóch stosuje się odległość do pierwszego punktu i najpierw wylicza się odległość ekstremum od pierwszego punktu: $d={\frac {-b}{2a}}-x_{1}$

Podstawiając:

$x_{2}:=x_{1}+dx_{2}$

$x_{3}:=x_{1}+dx_{3}$

$y_{2}:=y_{1}+dy_{2}$

$y_{3}:=y_{1}+dy_{3}$

Mamy:

$y_{1}*{\frac {(x-dx_{2}-x_{1})*(x-dx_{3}-x_{1})}{dx_{2}*dx_{3}}}+(y_{1}+dy_{2})*{\frac {(x-x_{1})*(x-dx_{3}-x_{1})}{dx_{2}*(dx_{2}-dx_{3})}}+(y_{1}+dy_{3})*{\frac {(x-x_{1})*(x-dx_{2}-x_{1})}{dx_{3}*(dx_{3}-dx_{2})}}$

Otrzymujemy:

$a=(dx_{2}\cdot dy_{3}-dx_{3}\cdot dy_{2})/(dx_{2}\cdot dx_{3}(dx_{3}-dx_{2}))$

$b=-(dx_{2}^{2}\cdot dy_{3}+2dx_{2}\cdot dy_{3}\cdot x_{1}-dx_{3}\cdot dy_{2}\cdot (dx_{3}+2x_{1}))/(dx_{2}\cdot dx_{3}\cdot (dx_{3}-dx_{2}))$

$d=(dx_{2}^{2}\cdot dy_{3}-dx_{3}^{2}\cdot dy_{2})/(2(dx_{2}\cdot dy_{3}-dx_{3}\cdot dy_{2}))$

Mając iloczyny $dx_{2}\cdot dy_{3}$ oraz $dx_{3}\cdot dy_{2}$ obliczymy d.

Kod

Poniższy kod został przedstawiony w artykule Brenta. 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

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ż

• metoda złotego podziału