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

modifica

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

modifica

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

modifica

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 |ba| è 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

modifica

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.

 
Grafico di  
  1. Nella prima iterazione, si utilizza l'interpolazione lineare tra   e  , che produce  . Poiché giace tra   e  , il valore è accettabile. Oltretutto,  , così si imposta   e  .
  2. 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  .
  3. 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  .
  4. 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  .
  5. 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 ( ).
  6. 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  .
  7. 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).
  8. Nell'ottavo passo del metodo, no si può usare l'interpolazione quadratica perché  . Dall'interpolazione lineare si ricava  , che è accettabile.
  9. Nelle successive iterazioni, ci si avvina molto rapidamente alla radice  :   e   (E si ha alla 9ª iterazione   e   in quella successiva).

Implementazioni

modifica
  • 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
  1. ^ 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
  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

modifica

Collegamenti esterni

modifica
  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica