Metodo di Brent
Nell'[[analisi numerica]], il '''metodo di Brent''' è un algoritmo che permette il [[Calcolo di uno zero di una funzione|calcolo numerico della radice]] di una funzione combinando il [[metodo della bisezione]], il [[metodo delle secanti]] e l'[[interpolazione quadratica inversa]]. L'algoritmo ha la robustezza della bisezione ma può essere veloce come altri metodi meno sicuri. Il metodo prova ad usare il potenzialmente veloce metodo delle secanti o dell'interpolazione quadratica inversa se possibile, ma può ripiegare sulla più robusta bisezione se necessario. Il metodo di Brent, come suggerisce il nome, è dovuto a [[Richard Brent]]<ref>[[Richard Brent|Brent, R. P.]] (1973),  "Chapter 4: An Algorithm with Guaranteed Convergence for Finding a Zero of a Function", Algorithms for Minimization without Derivatives, Englewood Cliffs, NJ: Prentice-Hall, ISBN 0-13-022335-2</ref> e costruito su un precedente algoritmo di Theodorus Dekker.<ref>Dekker, T. J. (1969), "Finding a zero by means of successive linear interpolation", in Dejon, B.; Henrici, P., Constructive Aspects of the Fundamental Theorem of Algebra, London: Wiley-Interscience, ISBN 978-0-471-20300-1</ref> Di conseguenza, l'algoritmo è conosciuto anche come '''metodo di Brent–Dekker'''.

== Metodo di Dekker ==
L'idea di combinare il metodo della bisezione con quello delle secanti risale a Dekker (1969).

Si suppoga che si voglia risolvere l'equazione <math>f(x)=0</math>. Come per il metodo della bisezione, serve inizializzare il metodo di Dekker con due punti, <math>a_0</math> e <math>b_0</math>, tali che <math>f(a_0)</math> e <math>f(b_0)</math> abbiano segno opposto. Se <math>f(x)</math> è continua in <math>[a_0, b_0]</math>, il [[teorema di Bolzano]] garantisce l'esistenza di una radice fra <math>a_0</math> e <math>b_0</math>.
In ogni iterazione sono coinvolti tre punti:
* <math>b_k</math> è la iterata corrente, cioè l'approssimazione temporanea dello zero di <math>f</math>.
* <math>a_k</math> è il "contro-punto", cioè un punto tale che <math>f(a_k)</math> e <math>f(b_k)</math> abbiano segno opposto, cosicché l'intervallo<math>[a_0, b_0]</math> contenga la soluzione. Oltretutto, <math>|f(b_k)|</math> dovrebbe essere minore o uguale di <math>|f(a_k)|</math>, in modo che <math>b_k</math> sia una migliore approssimazione della soluzione rispetto a <math>a_k</math>.
* <math>b_{k-1}</math> è la precedente iterata (per la prima iterazione, si pone <math>b_{k-1}=a_0</math>).

Ad ogni iterazione vengono calcolati due valori provvisori. Il primo è dato dall'interpolazione lineare, anche conosciuto come il metodo delle secanti:
::<math> s = \begin{cases}  b_k - \frac{b_k-b_{k-1}}{f(b_k)-f(b_{k-1})} f(b_k), & \mbox{se }  f(b_k)\neq f(b_{k-1})  \\ m & \mbox{altrimenti } \end{cases} </math>

e il secondo è dato dal metodo della bisezione
::<math> m = \frac{a_k+b_k}{2}. </math>
Se il risultato delle secanti, <math>s</math>, giace strettamente tra <math>b_k</math> e <math>m</math>, allora diventa la prossima iterata (<math>b_{k+1}=s</math>), altrimenti viene preso il [[punto medio]] (<math>b_{k+1}=m</math>).

Dopo, si sceglie il valore del nuovo contro-punto tale che <math>f(a_{k+1})</math> e <math>f(b_{k+1})</math> abbiano segno diverso. Se quest'ultimi hanno segni opposti, allora il contro-punto rimane lo stesso: <math>a_{k+1}=a_k</math>. Altrimenti, <math>f(b_{k+1})</math> e <math>f(b_k)</math> hanno segno diverso e perciò il nuovo contro-punto diventa <math>a_{k+1}=b_k</math>.

Infine, se <math>|f(a_{k+1})| < |f(b_{k+1})|</math>, allora <math>a_{k+1}</math> è probabilmente una migliore approssimazione della soluzione rispetto a <math>b_{k+1}</math>, e quindi vengono scambiati i valori di <math>a_{k+1}</math> e <math>b_{k+1}</math>.

Questo conclude la descrizione di una singola iterazione del metodo di Dekker.

Il metodo di Dekker funziona bene se <math>f</math> si "comporta" ragionevolmente bene. Tuttavia, ci sono delle circostanze in cui ogni iterazione utilizza il metodo delle secanti, ma <math>b_k</math> converge molto lentamente (in particolare, <math>|b_k-b_{k-1}|</math> può essere arbitrariamente piccolo). In questo caso, il metodo di Dekker richiede molte più iterazione dell'algoritmo di bisezione.

== Metodo di Brent ==
Brent (1973) propose una piccola modifica per evitare questo problema, infatti inserì un test aggiuntivo che deve essere soddisfatto prima che il risultato del metodo delle secanti sia accettato per l'iterazione successiva. Devono essere soddisfatte contemporaneamente due disuguaglianze:
Data una specifica tolleranza numerica <math>\delta</math>, se il passo precedente ha utilizzato il metodo della bisezione, deve valere entrambe la disuguaglianza
::<math> |\delta| < |b_k - b_{k-1}|,\quad |\delta| < |s-b_k| < \begin{matrix} \frac12 \end{matrix} |b_k - b_{k-1}| </math>
per eseguire l'interpolazione, altrimenti viene usata nuovamente la bisezione.

Se il passo precedente ha usato l'interpolazione, invece si usano
::<math> |\delta| < |b_{k-1} - b_{k-2}| \quad|s-b_k| < \begin{matrix} \frac12 \end{matrix} |b_{k-1} - b_{k-2}|</math>
per decidere se eseguire l'interpolazione (quando le disuguaglianze sono entrambe soddisfatte) o la bisezione (in caso contrario).

Questa modifica assicura che alla <math>k</math>-esima iterazione, il metodo della bisezione sarà utilizzato in al massimo <math>2\log_2(|b_{k-1}-b_{k-2}|/\delta)</math> successive iterazioni, poiché le precedenti condizioni obbligano le <math>|b_k-b_{k-1}|</math> a dimezzarsi ogni due iterazioni. Così dopo al massimo <math>2\log_2(|b_{k-1}-b_{k-2}|/\delta)</math> iterazioni, <math>|b_k-b_{k-1}|</math> sarà più piccolo di <math>\delta</math> e quindi viene eseguita una bisezione. Brent dimostrò che questo metodo richiede al massimo <math>N^2</math> iterazioni, dove <math>N</math> indica il numero di volte in cui metodo di bisezione è stato utilizzato. Se la funzione <math>f</math> non è , allora il metodo di Brent viene usato con sia la interpolazione lineare che quella quadratica inversa, e in tal caso l'algoritmo avrà una velocità di convergenza superlineare. 

Oltretutto, il metodo di Brent usa l'interpolazione quadratica inversa invece di quella [[Metodo dell'interpolazione lineare|lineare]] (come usato nel metodo delle secanti). Se <math>f(b_k)</math>, <math>f(a_k)</math> e <math>f(b_{k-1})</math> sono distinti, l'efficienza aumenta leggermente. Di conseguenza, la condizione per accettare <math>s</math> (il valore proposto sia dall'interpolazione lineare o quadratica) deve essere cambiata: <math>s</math> deve trovarsi tra <math>( 3a_k+ b_k) / 4</math> e <math>b_k</math>.

== Algoritmo ==
Di seguito si fornisce lo [[pseudocodice]] di questo metodo:

 '''input''' ''a'', ''b'', e (un puntatore a) una funzione ''f''
 calcola ''f''(''a'')
 calcola ''f''(''b'')
 '''if''' ''f''(''a'')''f''(''b'') &ge; 0 '''then''' esci dalla funzione perché la radice potrebbe non essere di (''a'',''b'').
 '''if''' |''f''(''a'')| < |''f''(''b'')| '''then''' scambia (''a'',''b'') '''end if'''
 ''c'' := ''a''
 '''set''' mflag
 '''repeat until''' ''f''(''b o s'') = 0 '''or''' |''b'' &minus; ''a''| è abbastanza piccolo ''(convergenza)''
   '''if''' ''f''(''a'') ≠ ''f''(''c'') '''and''' ''f''(''b'') ≠ ''f''(''c'') '''then'''

     <math> s := \frac{af(b)f(c)}{(f(a)-f(b))(f(a)-f(c))} + \frac{bf(a)f(c)}{(f(b)-f(a))(f(b)-f(c))} + \frac{cf(a)f(b)}{(f(c)-f(a))(f(c)-f(b))} </math>  ''(interpolazione quadratica inversa)''

   '''else'''

     <math> s := b - f(b) \frac{b-a}{f(b)-f(a)} </math> ''([[metodo delle secanti]])''

   '''end if'''
   '''if''' ''(condizione 1)'' ''s'' non è tra <math> \frac{3a+b}{4} </math> e ''b'' '''or'''
      ''(condizione 2)'' (mflag è impostata '''and''' <math>|s-b|\geq |b-c|/2</math>) '''or'''
      ''(condizione 3)'' (mflag è libera '''and''' <math>|s-b| \geq |c-d|/2</math>) '''or'''
      ''(condizione 4)'' (mflag è impostata '''and''' <math>|b-c| < |\delta|</math>) '''or'''
      ''(condizione 5)'' (mflag è libera '''and''' <math>|c-d| < |\delta|</math>)
   '''then'''

     <math> s := \frac{a+b}{2} </math> ''([[metodo della bisezione]])''

     '''set''' mflag
   '''else'''
     '''clear''' mflag
   '''end if'''
   calcola ''f''(''s'')
   ''d'' := ''c''  ''(d qui è stata assegnata per la prima volta; non sarà usata sopra nella prima iterazione perché mflag è impostata)''
   ''c'' := ''b''
   '''if''' ''f''(''a'')''f''(''s'') < 0 '''then''' ''b'' := ''s'' '''else''' ''a'' := ''s'' '''end if'''
   '''if''' |''f''(''a'')| < |''f''(''b'')| '''then''' scambia (''a'',''b'') '''end if'''
 '''end repeat'''
 '''output''' ''b'' ''o s (restituisce la radice)''

== Esempio ==
Si supponga che si stia cercando uno zero della funzione <math>f(x) = (x + 3)(x - 1)^2</math>.

Si prende <math>[a_0, b_0] = [-4, 4/3]</math> come intervallo iniziale.

Si ha <math>f(a_0) = -25</math> e <math>f(b_0) = 0.48148</math> (tutti i numeri in questa sezione sono arrotondati), perciò le condizioni <math>f(a_0)f(b_0)<0</math> e <math>|f(b_0)| \leq |f(a_0)|</math> sono soddisfatte.

[[Image:Brent method example.svg|thumb|Grafico di <math>f(x)=(x+3)(x-1)^2</math>]]
# Nella prima iterazione, si utilizza l'interpolazione lineare tra <math>(b_{-1},f(b_{-1})) = (a_0,f(a_0)) = (-4, -25)</math> e <math>(b_0,f(b_0)) = (1.33333, 0.48148)</math>, che produce <math>s = 1.23256</math>. Poiché giace tra <math>( 3a_0+ b_0) / 4</math> e <math>b_0</math>, il valore è accettabile. Oltretutto, <math>f(1.23256) = 0.22891</math>, così si imposta <math>a_1=a_0</math> e <math>b_1=s=1.23256</math>.
# Nella seconda iterazione, si utilizza l'interpolazione quadratica inversa tra <math>(a_1,f(a_1)) = (-4, -25)</math>, <math>(b_0,f(b_0)) = (1.33333, 0.48148)</math> e <math>(b_1,f(b_1)) = (1.23256, 0.22891)</math>. Questo porta a 1.14205, che è compreso tra <math>(3a_1 + b_1) / 4</math> e <math>b_1</math>. Inoltre, la disuguaglianza <math>|1.14205 - b_1| \leq |b_0-b_1| / 2</math> è soddisfatta, e quindi questo valore è accettabile. Oltretutto, <math>f(1.14205) = 0.083582</math>, perciò si imposta <math>a_2 = a_1</math> e <math>b_2 = 1.14205</math>.
# Al terzo passo, si utilizza l'interpolazione quadratica inversa tra <math>(a_2,f(a_2)) = (-4, -25)</math>, <math>(b_1,f(b_1)) = (1.23256, 0.22891)</math> e <math>(b_2,f(b_2)) = (1.14205, 0.083582)</math>. Si ottiene così 1.09032, che giace tra <math>( 3a_2+ b_2) / 4</math> e <math>b_2</math>. Ma qui si deve tenere conto della condizione aggiuntiva di Brent: la disuguaglianza <math>|1.09032 - b_2| \leq |b_1-b_0| / 2</math> non è soddisfatta, perciò il valore viene scartato. Invece si considera il punto medio <math> m = -1.42897</math> dell'intervallo <math>[a_2, b_2]</math>, e si ha <math>f(m) = 9.26891</math>, dunque si mette <math>a_3=a_2</math> e <math>b_3=-1.42897</math>.
# Nella quarta iterazione, si utilizza l'interpolazione quadratica inversa tra <math>(a_3,f(a_3)) = (-4, -25)</math>, <math>(b_2,f(b_2)) = (1.14205, 0.083582)</math> e <math>(b_3,f(b_3)) = (-1.42897, 9.26891)</math>, restituendo <math>1.15448</math>. Quest'ultimo non giace tra <math>( 3a_3+ b_3) / 4</math> e <math>b_3</math>, quindi è sostituito dal punto medio <math>m = -2.71449</math>. Di conseguenza si ha <math>f(m) = 3.93934</math>, quindi si imposta <math>a_4 = a_3</math> e <math>b_4 = -2.71449</math>.
# Nella quinta interazione, usando l'interpolazione quadratica inversa, si ottiene <math>-3.45500</math>, che giace nell'intervallo richiesto. Tuttavia, la precedente iterazione ha usato la bisezione, perciò deve essere soddisfatta la disuguaglianza <math>|3.45500 - b_4| \leq |b_4-b_3| / 2 </math>. Quest'ultima è falsa, quindi si usa il punto medio <math> m = -3.35724</math>. Si ricava <math>f(m) = -6.78239</math>, allora <math>m</math> diventa il nuovo contro-punto (<math>a_5 = -3.35724</math>) e l'iterata rimane la stessa (<math>b_5=b_4</math>). 
# Nella sesta iterazione, non si può usare l'interpolazione quadratica perché <math>b_5=b_4</math>. Quindi, si usa l'interpolazione lineare tra <math> (a_5, f(a_5)) = (-3.35724, -6.78239)</math> e <math>(b_5, f(b_5)) = (-2.71449, 3.93934)</math>. Il risultato è <math>s = -2.95064</math>, che soddisfa tutte le condizioni. Ma poiché l'iterata non è cambiata nel passo precedente, si rifiuta il risultato e si ritorna alla bisezione. Si aggiorna così <math>s = -3.03587</math>, e si ha <math>f(s) = -0.58418</math>.
# Nella settima iterazione, si può nuovamente usare l'interpolazione quadratica inversa. Il risultato è <math>s = -3.00219</math>, che soddisfa tutte le condizioni. Ora, <math>f(s) = -0.03515</math>, quindi si imposta <math>a_7=b_6</math> e <math>b_7 = -3.00219</math> (<math>a_7</math> e <math>b_6</math> sono scambiati in modo che la condizione <math>|f(b_7)| \leq |f(a_7)|</math> sia soddisfatta).
# Nell'ottavo passo del metodo, no si può usare l'interpolazione quadratica perché <math>a_7=b_6</math>. Dall'interpolazione lineare si ricava <math>s = -2.99994</math>, che è accettabile. 
# Nelle successive iterazioni, ci si avvina molto rapidamente alla radice <math>x = -3</math>: <math>b_9 = -3 + 6\cdot 10^{-8}</math> e <math>b_10 = -3 - 3\cdot 10^{-15}</math> (E si ha alla 9ª iterazione <math>f(s) = -1.4\cdot 10^{-7}</math> e <math>f(s) = 6.96\cdot 10^{-12}</math> in quella successiva).

== Implementazioni ==
* Brent (1973) pubblicò una implementazione in ''Algol 60''. 
* ''Netlib'' contiene una traduzione in [[Fortran]] di questa implementazione con leggere modifiche. 
* Il metodo <kbd>solve</kbd> di PARI/GP implementa il metodo di Brent. 
* Altre implementazione dell'algoritmo (in C++, C, e Fortran) si trovano nella serie di libri ''Numerical Recipes''. 
* La libreria matematica di ''Apache Commons'' implementa l'algoritmo in [[Java (linguaggio di programmazione)|Java]].
* Il modulo di ottimizzazione ''SciPy'' implementa l'algoritmo in [[Python]].
* La libreria standard di ''Modelica'' implementa il metodo in [[Modelica]].
* La funzione <kbd>optimize</kbd> implementa l'algoritmo in [[R (software)]].
* Le librerie [[Boost (C++)|boost]] implementano l'algoritmo in [[C++]] nel toolkit di matematica ("Locating function minima").
* Il pacchetto <kbd>Optim.jl</kbd> implementa l'algoritmo in [[Julia (linguaggio di programmazione)|Julia]]

== Note ==
<references/>

== Bibliografia ==
*Atkinson, Kendall E. (1989). "Sezione 2.8.". An Introduction to Numerical Analysis (2ª ed.). John Wiley and Sons. ISBN 0-471-50023-2.
*Press, W. H.; Teukolsky, S. A.; Vetterling, W. T.; Flannery, B. P. (2007). [http://apps.nrbook.com/empanel/index.html#pg=454 "Section 9.3. Van Wijngaarden–Dekker–Brent Method"] {{Webarchive|url=https://web.archive.org/web/20110811154417/http://apps.nrbook.com/empanel/index.html#pg=454 |date=11 agosto 2011 }}. Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.

== Collegamenti esterni ==
* [http://www.netlib.org/go/zeroin.f zeroin.f] in Netlib.
* [http://people.sc.fsu.edu/~jburkardt/cpp_src/brent/brent.html modulo Brent in C++ (anche C, Fortran, Matlab)] {{Webarchive|url=https://web.archive.org/web/20180405205252/http://people.sc.fsu.edu/~jburkardt/cpp_src/brent/brent.html |date=5 aprile 2018 }} di John Burkardt 
* [https://www.gnu.org/software/gsl/ GSL] implementazione.
* [https://www.boost.org/doc/libs/1_55_0/libs/math/doc/html/math_toolkit/internals1/minima.html Boost C++] implementazione.
* [https://it.wikitolearn.org/Corso:Calcolo_Numerico_I1/Radici_di_equazioni_non_lineari/Metodo_di_Brent Metodo di brent] {{Webarchive|url=https://web.archive.org/web/20180421162839/https://it.wikitolearn.org/Corso:Calcolo_Numerico_I1/Radici_di_equazioni_non_lineari/Metodo_di_Brent |date=21 aprile 2018 }}

{{Portale|matematica}}

[[Categoria:Algoritmi per il calcolo degli zeri|Brent]]