Metodo di Brent
Nell'analisi numerica, il metodo di Brent è un algoritmo che permette il 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[1] e costruito su un precedente algoritmo di Theodorus Dekker.[2] 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 . Come per il metodo della bisezione, serve inizializzare il metodo di Dekker con due punti, e , tali che e abbiano segno opposto. Se è continua in , il teorema di Bolzano garantisce l'esistenza di una radice fra e . In ogni iterazione sono coinvolti tre punti:
- è la iterata corrente, cioè l'approssimazione temporanea dello zero di .
- è il "contro-punto", cioè un punto tale che e abbiano segno opposto, cosicché l'intervallo contenga la soluzione. Oltretutto, dovrebbe essere minore o uguale di , in modo che sia una migliore approssimazione della soluzione rispetto a .
- è la precedente iterata (per la prima iterazione, si pone ).
Ad ogni iterazione vengono calcolati due valori provvisori. Il primo è dato dall'interpolazione lineare, anche conosciuto come il metodo delle secanti:
e il secondo è dato dal metodo della bisezione
Se il risultato delle secanti, , giace strettamente tra e , allora diventa la prossima iterata (), altrimenti viene preso il punto medio ().
Dopo, si sceglie il valore del nuovo contro-punto tale che e abbiano segno diverso. Se quest'ultimi hanno segni opposti, allora il contro-punto rimane lo stesso: . Altrimenti, e hanno segno diverso e perciò il nuovo contro-punto diventa .
Infine, se , allora è probabilmente una migliore approssimazione della soluzione rispetto a , e quindi vengono scambiati i valori di e .
Questo conclude la descrizione di una singola iterazione del metodo di Dekker.
Il metodo di Dekker funziona bene se si "comporta" ragionevolmente bene. Tuttavia, ci sono delle circostanze in cui ogni iterazione utilizza il metodo delle secanti, ma converge molto lentamente (in particolare, 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 , se il passo precedente ha utilizzato il metodo della bisezione, deve valere entrambe la disuguaglianza
per eseguire l'interpolazione, altrimenti viene usata nuovamente la bisezione.
Se il passo precedente ha usato l'interpolazione, invece si usano
per decidere se eseguire l'interpolazione (quando le disuguaglianze sono entrambe soddisfatte) o la bisezione (in caso contrario).
Questa modifica assicura che alla -esima iterazione, il metodo della bisezione sarà utilizzato in al massimo successive iterazioni, poiché le precedenti condizioni obbligano le a dimezzarsi ogni due iterazioni. Così dopo al massimo iterazioni, sarà più piccolo di e quindi viene eseguita una bisezione. Brent dimostrò che questo metodo richiede al massimo iterazioni, dove indica il numero di volte in cui metodo di bisezione è stato utilizzato. Se la funzione 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 lineare (come usato nel metodo delle secanti). Se , e sono distinti, l'efficienza aumenta leggermente. Di conseguenza, la condizione per accettare (il valore proposto sia dall'interpolazione lineare o quadratica) deve essere cambiata: deve trovarsi tra e .
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) ≥ 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 − a| è abbastanza piccolo (convergenza) if f(a) ≠ f(c) and f(b) ≠ f(c) then
(interpolazione quadratica inversa)
else
(metodo delle secanti)
end if if (condizione 1) s non è tra e b or (condizione 2) (mflag è impostata and ) or (condizione 3) (mflag è libera and ) or (condizione 4) (mflag è impostata and ) or (condizione 5) (mflag è libera and ) then
(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 .
Si prende come intervallo iniziale.
Si ha e (tutti i numeri in questa sezione sono arrotondati), perciò le condizioni e sono soddisfatte.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/2d/Brent_method_example.svg/220px-Brent_method_example.svg.png)
- Nella prima iterazione, si utilizza l'interpolazione lineare tra e , che produce . Poiché giace tra e , il valore è accettabile. Oltretutto, , così si imposta e .
- Nella seconda iterazione, si utilizza l'interpolazione quadratica inversa tra , e . Questo porta a 1.14205, che è compreso tra e . Inoltre, la disuguaglianza è soddisfatta, e quindi questo valore è accettabile. Oltretutto, , perciò si imposta e .
- Al terzo passo, si utilizza l'interpolazione quadratica inversa tra , e . Si ottiene così 1.09032, che giace tra e . Ma qui si deve tenere conto della condizione aggiuntiva di Brent: la disuguaglianza non è soddisfatta, perciò il valore viene scartato. Invece si considera il punto medio dell'intervallo , e si ha , dunque si mette e .
- Nella quarta iterazione, si utilizza l'interpolazione quadratica inversa tra , e , restituendo . Quest'ultimo non giace tra e , quindi è sostituito dal punto medio . Di conseguenza si ha , quindi si imposta e .
- Nella quinta interazione, usando l'interpolazione quadratica inversa, si ottiene , che giace nell'intervallo richiesto. Tuttavia, la precedente iterazione ha usato la bisezione, perciò deve essere soddisfatta la disuguaglianza . Quest'ultima è falsa, quindi si usa il punto medio . Si ricava , allora diventa il nuovo contro-punto () e l'iterata rimane la stessa ().
- Nella sesta iterazione, non si può usare l'interpolazione quadratica perché . Quindi, si usa l'interpolazione lineare tra e . Il risultato è , 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ì , e si ha .
- Nella settima iterazione, si può nuovamente usare l'interpolazione quadratica inversa. Il risultato è , che soddisfa tutte le condizioni. Ora, , quindi si imposta e ( e sono scambiati in modo che la condizione sia soddisfatta).
- Nell'ottavo passo del metodo, no si può usare l'interpolazione quadratica perché . Dall'interpolazione lineare si ricava , che è accettabile.
- Nelle successive iterazioni, ci si avvina molto rapidamente alla radice : e (E si ha alla 9ª iterazione e 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 solve 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.
- Il modulo di ottimizzazione SciPy implementa l'algoritmo in Python.
- La libreria standard di Modelica implementa il metodo in Modelica.
- La funzione optimize implementa l'algoritmo in R (software).
- Le librerie boost implementano l'algoritmo in C++ nel toolkit di matematica ("Locating function minima").
- Il pacchetto Optim.jl implementa l'algoritmo in Julia
Note
- ^ 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
- ^ 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
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). "Section 9.3. Van Wijngaarden–Dekker–Brent Method" Archiviato l'11 agosto 2011 in Internet Archive.. Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.
Collegamenti esterni
- zeroin.f in Netlib.
- modulo Brent in C++ (anche C, Fortran, Matlab) Archiviato il 5 aprile 2018 in Internet Archive. di John Burkardt
- GSL implementazione.
- Boost C++ implementazione.
- Metodo di brent Archiviato il 21 aprile 2018 in Internet Archive.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Crystal128-kmplot.svg/25px-Crystal128-kmplot.svg.png)