Tekst źródłowy strony 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 <math>ax^2+bx+c</math> 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 <math>\frac{-b}{2a}</math>
Mając trzy punkty x<sub>1</sub>,x<sub>2</sub> i x<sub>3</sub> oraz wartości funkcji y<sub>1</sub>, y<sub>2</sub> i y<sub>3</sub> z [[Interpolacja_wielomianowa#Wielomian_Lagrange'a|interpolacji wielomianem Lagrange'a]] mamy:
:<math>
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)}
</math>
W metodzie Brenta aby uprościć wzór na <math>\frac{-b}{2a}</math> wybrano jeden punkt (np x<sub>1</sub>) i zamiast pozostałych dwóch stosuje się odległość do pierwszego punktu i najpierw wylicza się odległość ekstremum od pierwszego punktu: <math>d = \frac{-b}{2a} - x_1</math>

Podstawiając: 
:<math>x_2:=x_1+dx_2</math>
:<math>x_3:=x_1+dx_3</math>
:<math>y_2:=y_1+dy_2</math>
:<math>y_3:=y_1+dy_3</math>
Mamy: 
:<math>
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)}
</math>
Otrzymujemy: 
:<math>a = (dx_2 \cdot dy_3 - dx_3 \cdot dy_2)/(dx_2 \cdot dx_3 (dx_3 - dx_2))</math>
:<math>b =-(dx_2^2 \cdot dy_3 + 2 dx_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))</math>
:<math>d = (dx_2^2 \cdot dy_3 - dx_3^2 \cdot dy_2)/(2 (dx_2 \cdot dy_3 - dx_3 \cdot dy_2))</math>
Mając iloczyny <math>dx_2 \cdot dy_3</math> oraz <math>dx_3 \cdot dy_2</math> obliczymy d.

==Kod==
Poniższy kod został przedstawiony w artykule Brenta<ref>[http://www.jasoncantarella.com/downloads/brent_excerpt.pdf Algorithm for inimization without derivatives]</ref>. 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]]

== Przypisy ==
{{Przypisy}}

[[Kategoria:Metody numeryczne]]
[[Kategoria:Metody optymalizacji]]