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

allora è più vicino alla radice di quanto lo sia . Questo in realtà non è sempre vero, infatti se considero una funzione che interseca l'asse x in e poi decresce lentamente dopo tale punto, si ha che, pur scegliendo lontano dalla radice, segue che ma è più vicina alla radice di quanto lo sia .

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]

  1. 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.
  2. Test d'arresto sull'ampiezza della bracket: Finché le istruzioni vengono eseguite.
  3. Nuovo passo: ci si avvicina alla radice attraverso l'assegnamento
    dove 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.
  4. 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
  5. 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.
  6. Controllo
  7. Applicazione del passo scelto:
  8. Preparazione della terna di punti per un eventuale passo successivo:
    Nota: se , allora segue necessariamente che , perché erano una bracket)
  9. 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:

Nel momento in cui scavalca la radice, la bracket si riduce velocemente e il metodo si blocca.

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
 PrecedenteSuccessivo