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{x}^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+d{x}_2$

$x_3:=x_1+d{x}_3$

$y_2:=y_1+d{y}_2$

$y_3:=y_1+d{y}_3$

Mamy:

$y_1*\frac{(x-d{x}_2-x_1)*(x-d{x}_3-x_1)}{d{x}_2*d{x}_3}+(y_1+d{y}_2)*\frac{(x-x_1)*(x-d{x}_3-x_1)}{d{x}_2*(d{x}_2-d{x}_3)}+(y_1+d{y}_3)*\frac{(x-x_1)*(x-d{x}_2-x_1)}{d{x}_3*(d{x}_3-d{x}_2)}$

Otrzymujemy:

$a=(d{x}_2\cdot d{y}_3-d{x}_3\cdot d{y}_2)/(d{x}_2\cdot d{x}_3(d{x}_3-d{x}_2))$

$b=-(d{x}_2^2\cdot d{y}_3+2d{x}_2\cdot d{y}_3\cdot x_1-d{x}_3\cdot d{y}_2\cdot (d{x}_3+2x_1))/(d{x}_2\cdot d{x}_3\cdot (d{x}_3-d{x}_2))$

$d=(d{x}_2^2\cdot d{y}_3-d{x}_3^2\cdot d{y}_2)/(2(d{x}_2\cdot d{y}_3-d{x}_3\cdot d{y}_2))$

Mając iloczyny $d{x}_2\cdot d{y}_3$ oraz $d{x}_3\cdot d{y}_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