Data una funzione ƒ(x), si dice zero, o radice, di ƒ un elemento x0
del suo dominio tale che ƒ(x0) = 0.
Ci proponiamo di trovare gli zeri della funzione ƒ(x) = x2-2
utilizzando il metodo di bisezione. È l'algoritmo più semplice
ed è iterativo e, ad ogni ciclo,
dimezza l'intervallo in cui si
trova lo zero.
Dal teorema di Bolzano (o degli zeri) sappiamo che data una
funzione ƒ continua sull'intervallo chiuso [a,b] a valori in ℜ
tale che ƒ(a)*ƒ(b) < 0,
allora esiste un punto
x0 all'interno di [a,b] tale che ƒ(x0) = 0.
Definiamo intervallo di incertezza di ƒ un intervallo [a,b] che
soddisfa il Teorema
di Bolzano.
L'idea di base dell'algoritmo è che se esiste un intervalo di
incertezza [a,b] per
una funzione ƒ, allora ne esiste uno più piccolo (esattamente
la metà).
L'algoritmo deve avere in input
l'intervallo di incertezza di partenza [a,b] ed una precisione (o tolleranza)
ε con cui si vuole trovare lo zero di ƒ tale che |b -
a| < ε.
Si parte quindi dividendo in due l'intervallo trovando
il punto medio c = a + 0.5*(b-a) per cui avremo due intervalli [a,c] e [c,b].
Ora se ƒ(c) = 0 siamo fortunati e abbiamo trovato lo zero .
Altrimenti si deve valutare ƒ(a)*ƒ(c) e ƒ(c)*ƒ(b) e
ripetere la procedura sull'intervallo in cui ƒ cambia di segno.
La procedura va ripetuta finchè la larghezza dell'intervallo finale non è minore di ε.
Ci sono alcuni caveat. Se l'intervallo contiene più di una
radice il metodo della bisezione ne troverà solo
una.
Nell'implementazione delle condizioni
di ricerca dall'intervallo di incertezza occorre prestare attenzione alle
operazioni tra floating
point soprattutto in prossimità della radice.
Ad esempio le espressioni ƒ(a)*ƒ(c) e ƒ(c)*ƒ(b)
hanno una buona probabilità di essere approssimata a zero dal
momento che entrambi gli argomenti
convergono a una radice di
ƒ. Per evitare questa eventualità, è meglio valutare,
il prodotto dei segni sign(ƒ(a))*sign(ƒ(c))
e sign(ƒ(c))*sign(ƒ(b)).
Un altro controllo utile è contare il numero di iterazioni
dell'algoritmo e stampare un warning nel caso queste siano troppo grandi.
In tal modo ci si accorge se ci sono possibili problemi nel loop
(errori o richiesta di precisione troppo alta)
|
