Metodo di Brent

Struttura del metodo

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 $(b,c)$$(b,c)$ con $f(b)*f(c)<0$$f(b)*f(c)<0$. Restituisce come output lo zero della funzione nella variabile chiamata $b$$b$. Nell'algoritmo, $b$$b$ rappresenta l'approssimazione della radice cercata. Il metodo si basa sull'idea che se

$$|f(b)|<|f(c)|$$

$$|f(b)|<|f(c)|$$

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

Nell'algoritmo, $a,b$$a,b$ rappresentano le due iterate con cui il metodo delle secanti calcola l'iterata successiva, cioè $b=x_{k}$$b=x_{k}$, $a=x_{k-1}$$a=x_{k-1}$, mentre $b$$b$ e $c$$c$ sono gli estremi della bracket.

Algoritmo

1. Definizione di a,b,c: In base all'idea precedente, se $|f(b)|>|f(c)|$$|f(b)|>|f(c)|$ allora scambio fra loro $b$$b$ e $c$$c$. Pongo poi $a=c$$a=c$ per far partire il metodo delle secanti.
2. Test d'arresto sull'ampiezza della bracket: Finché $|b-c|>\varepsilon$$|b-c|>\varepsilon$ le istruzioni vengono eseguite.
3. Nuovo passo: ci si avvicina alla radice attraverso l'assegnamento
   $$b=b+d_{d}$$

   $$b=b+d_{d}$$
   dove $d_{d}$$d_{d}$ 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 $b$$b$ in entrambi i metodi:
   $$d_{m}=(c-b)/2\quad {\hbox{passo di bisezione}}$$

   $$d_{m}=(c-b)/2\quad {\hbox{passo di bisezione}}$$
   Prima di calcolare $d_{s}$$d_{s}$ (passo del metodo delle secanti), si valuta $d_{f}=f(b)-f(a)$$d_{f}=f(b)-f(a)$. Se $d_{f}=0$$d_{f}=0$, si pone $d_{d}=d_{m}$$d_{d}=d_{m}$, perché $d_{s}$$d_{s}$ non è applicabile. Altrimenti
   $$d_{s}=a-{\frac {b-a}{f(b)-f(a)}}*f(b)$$

   $$d_{s}=a-{\frac {b-a}{f(b)-f(a)}}*f(b)$$
5. Scelta del passo: se entrambi i passi sono applicabili, si eseguono le seguenti istruzioni:
   $${\rm {{if}(\mathrm {sgn} d_{m}==\mathrm {sgn} d_{s}\wedge |d_{s}|<=|d_{m}|)}}$$

   $${\rm {{if}(\mathrm {sgn} d_{m}==\mathrm {sgn} d_{s}\wedge |d_{s}|<=|d_{m}|)}}$$
   $$d_{d}=d_{s}$$

   $$d_{d}=d_{s}$$
   $${\rm {else}}$$

   $${\rm {else}}$$
   $$d_{d}=d_{m}$$

   $$d_{d}=d_{m}$$
   $${\rm {end}}$$

   $${\rm {end}}$$
   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$\ast \ast \ast$$\ast \ast \ast$
7. Applicazione del passo scelto: $d=b+d_{d}$$d=b+d_{d}$
8. Preparazione della terna di punti per un eventuale passo successivo:
   $$a_{1}=a$$

   $$a_{1}=a$$
   $$b_{1}=d$$

   $$b_{1}=d$$
   $${\rm {{if}(\mathrm {sgn} f(d)\neq \mathrm {sgn} f(c))}}$$

   $${\rm {{if}(\mathrm {sgn} f(d)\neq \mathrm {sgn} f(c))}}$$
   $$c_{1}=c$$

   $$c_{1}=c$$
   $${\rm {else}}$$

   $${\rm {else}}$$
   $$c_{1}=b$$

   $$c_{1}=b$$
   $${\rm {end}}$$

   $${\rm {end}}$$
   Nota: se $\mathrm {sgn} f(d)\neq \mathrm {sgn} f(c)$$\mathrm {sgn} f(d)\neq \mathrm {sgn} f(c)$, allora segue necessariamente che $\mathrm {sgn} f(d)\neq \mathrm {sgn} f(b)$$\mathrm {sgn} f(d)\neq \mathrm {sgn} f(b)$, perché $b,c$$b,c$ erano una bracket)
9. Assegnamento:
   $$b=b_{1}$$

   $$b=b_{1}$$
   $$c=c_{1}$$

   $$c=c_{1}$$
   $${\rm {{if}(|f(b)|>|f(c)|)}}$$

   $${\rm {{if}(|f(b)|>|f(c)|)}}$$
   $$temp=b;$$

   $$temp=b;$$
   $$b=c;$$

   $$b=c;$$
   $$c=temp;$$

   $$c=temp;$$
   $${\rm {end}}$$

   $${\rm {end}}$$
   $$a_{1}=c$$

   $$a_{1}=c$$

$\ast \ast \ast$$\ast \ast \ast$: 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 $|d_{d}|<\varepsilon$$|d_{d}|<\varepsilon$ (quindi se il metodo delle secanti sta convergendo), si pone:

$$d=\varepsilon /2*\mathrm {sgn} d_{d}$$

$$d=\varepsilon /2*\mathrm {sgn} d_{d}$$

Nel momento in cui $d$$d$ 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