Metodo di Brent
Struttura del metodo[modifica | modifica wikitesto]
E' una combinazione del metodo di bisezione e delle secanti, in cui si sfruttano la sicurezza di convergenza del metodo di bisezione e la velocità di convergenza di quello delle secanti.
Il metodo richiede come input una bracket con . Restituisce come output lo zero della funzione nella variabile chiamata . Nell'algoritmo, rappresenta l'approssimazione della radice cercata. Il metodo si basa sull'idea che se
Nell'algoritmo, rappresentano le due iterate con cui il metodo delle secanti calcola l'iterata successiva, cioè , , mentre e sono gli estremi della bracket.
Algoritmo[modifica | modifica wikitesto]
- Definizione di a,b,c: In base all'idea precedente, se allora scambio fra loro e . Pongo poi per far partire il metodo delle secanti.
- Test d'arresto sull'ampiezza della bracket: Finché le istruzioni vengono eseguite.
- Nuovo passo: ci si avvicina alla radice attraverso l'assegnamentodove può essere posto uguale al passo del metodo delle secanti oppure uguale al passo del metodo di bisezione, e questa scelta viene valutata ad ogni iterazione.
- Valutazione dei due passi possibili: Per scegliere quali dei due metodi usare, si valuta di quanto ci si sposta da in entrambi i metodi:Prima di calcolare (passo del metodo delle secanti), si valuta . Se , si pone , perché non è applicabile. Altrimenti
- Scelta del passo: se entrambi i passi sono applicabili, si eseguono le seguenti istruzioni:Nota: Queste istruzioni si giustificano nel seguente modo: Il passo di bisezione rimane sempre nella bracket per definizione del metodo, invece, se il passo di secanti ha direzione opposta, si esce dalla bracket. Una volta assicurato che entrambi i metodi stanno dentro la bracket, si sceglie il passo di ampiezza più piccola, che mi fa allontanare di meno dall'approssimazione corrente della radice.
- Controllo
- Applicazione del passo scelto:
- Preparazione della terna di punti per un eventuale passo successivo:Nota: se , allora segue necessariamente che , perché erano una bracket)
- Assegnamento:
: Prima di usare il passo scelto, bisogna fare un controllo. Se si continua ad applicare il metodo delle secanti, l'ampiezza della bracket non si riduce, e il metodo continua a fare iterazioni anche vicino alla radice, perché la condizione del test di arresto sulla bracket non viene verificata. Allora si aggiunge il seguente test: se (quindi se il metodo delle secanti sta convergendo), si pone:
Metodo implementato:
function [b,it] = Mybrent(f,a,b,c) if(abs(feval(f,b))>=abs(feval(f,c))) temp = b; b = c; c = temp; end while(abs(b-c)>eps) dm = (c-b)/2; q = feval(f,a)-feval(f,b); if(q==0) ds = dm; else ds = a-(b-a)/(feval(f,b)-feval(f,a))*feval(f,b); end if(sign(ds)==sign(dm)&&abs(ds)<=abs(dm)) dd = ds; else dd = dm; end if(dd<eps) d = eps/2*sign(dd); end d = b+dd; b1 = d; if(sign(b1)==sign(b)) c1 = c; else c1 = b; end b = b1; c = c1; if(abs(feval(f,c))<=abs(feval(f,b))) temp = b; b = c; c = temp; end end