Data una generica funzione continua \( f(x) \) in un certo intervallo compatto \( [a, b]\), siamo interessati alla ricerca degli zeri "radici" (o meglio di uno zero in [a, b]) attraverso un metodo non algebrico. In generale per una funzione che non sia una di quelle elementari non esiste una "formula risolutiva" per la ricerca delle radici, per le equazioni algebriche esiste la formula fino al grado 4. Come possiamo risolvere sempre una equazione della forma \(f(\alpha) = 0 \)?.
Ci viene anzitutto in aiuto un teorema classico dell'analisi (Teorema degli zeri "di Bolzano") che ci assicura sempre che: se la funzione è continua in [a, b] ed assume segni opposti negli estremi (\( f(a)\cdot f(b) < 0\)), allora ci sarà sicuramente un punto \(\alpha\) da qualche parte nell'intervallo in cui \(f(\alpha) = 0\). Da un punto di vista intuitivo, il grafico della funzione deve per forza intersecarsi con l'asse delle ascisse se provaste a tracciare una curva continua da un punto negativo ad uno positivo!
Bisezione
Fatte queste premesse, possiamo costruire un algoritmo, per la ricerca degli zeri detto metodo di bisezione in grado di ricercare un intervallo in cui ricade lo zero con una certa precisione \(\epsilon\). Tutto quello che dobbiamo fare e suddividere in due (da qui "bisezione") l'intervallo di partenza e verificare "iterativamente" le condizioni del teorema di Bolzano e scartare la parte di intervallo in cui non valgono. Il mnetodo si arresta quando la dimenzione dell'intervallo corrente, diventa minore di \( \epsilon \).
Partiamo da una funzione \(f(x)\). Al passo zero, l'intervallo è tutto \([a, b]\). Chiaramente per ipotesi \(f(a)f(b) < 0 \): lo zero deve trovarsi nell'intervallo, altrimenti sarebbe inutile partire!.
- Si procede al passo uno dividendo in due l'intervallo in due sottointervalli: \( [a, {a+b \over 2}], [{a+b \over 2}, b] \).
Ora si verifica dove il prodotto negli estremi è negativo, se fosse ad esempio \( f(a)f\left( {a+b \over 2}\right) < 0 \) scarteremmo l'altro, altrimenti se fosse \( f(a)f\left( {a+b \over 2}\right) > 0 \) bisognerebbe verificare \( f\left( {a+b \over 2}\right)f(b) \) che sarà, si presume, negativo! Si controlla se è verificata la condizione di arresto: \( b-a < \epsilon\), se è verificata abbiamo finito, altrimenti si procede allo stesso modo. - Supponendo di avere scelto l'intervallo \( [a, {a+b \over 2}] \), si procede alla suddivisione in due parti, ottenendo i sottontervalli: \( \left[a, {a + {a+b\over 2}\over 2}\right] \) e \( \left[{a + {a+b\over 2}\over 2}, {a+b\over 2}\right] \), si considera l'intervallo in cui il prodotto della funzione negli estremi è negativo e così via...
- Al passo \(i\)-esimo lo zero sarà \( \alpha \approx x_i \pm {1\over 2}|b_i-a_i| \).
Esempio
Facciamo un esempio: prendiamo la funzione \( y = x^2-5\). Questa funzione sappiamo già avere due zeri, in particolare \( x_{12} = \pm \sqrt 5\) \(\Rightarrow x_1 \approx {2.236}, x_2 \approx {-2.236}\). Mettiamoci ad esempio nell'intervallo \( [1, 3]\), sicuri di beccare lo zero positivo, e fissiamo una precisione pari a \( \epsilon = 0.3 \).
-
\( \small f(1)f(3) = (1-5)(9-5) = (-4)(4) = -16 \). La precisione ancora è troppo grande: \(3-1 > 0.3\), iteriamo:
Lo zero deve trovarsi nell'intervallo \( [1, 3]\). Diviadiamo in due: consideriamo i due sottointervalli: \( [1, 2] \) e \( [2, 3]\). Avremo \(f(1)f(2) = (-4)(-1) > 0 \), mentre \(f(2)f(3) = (-4)(4) < 0 \). Scartiamo il primo intervallo e scegliamo il secondo. Verifichiamo la condizione di arresto: \( 2-1 > 0.3\) non è soddisfatta, iteriamo:
Lo zero deve trovarsi nell'intervallo \( [2, 3]\). Diviadiamo in due: consideriamo i due sottointervalli: \( [2, {2+3 \over 2}] \) e \( [{2+3 \over 2}, 3]\), ossia \( [2, 2.5] \) e \( [2.5, 3]\). Avremo: \( f(2)f(2.5) = (-1)(1.25) < 0\). Abbiamo gia trovato l'intervallo corretto, si potrebbe verificare che l'altro non soddisfa le condizioni di Bolzano, ma è una verifica ridondante. Verifichiamo la condizione di arresto: \( 2.5 - 2 > 0.3\), ancora risulta non valida, iteriamo:
Lo zero deve trovarsi nell'intervallo \( [2, 2.5]\). Diviadiamo in due: consideriamo i due sottointervalli: \( [2, {2.5+2 \over 2}] \) e \( [{2.5+2 \over 2}, 2.5]\) ossia: \( [2, 2.25] \) e \( [2.25, 2.5]\). Avremo che: \( f(2)f(2.25) = (-1)(0.0625) < 0\). Questo è l'intervallo contenente lo zero. Siccome \( 2.25 - 2 < 0.3\) ci fermiamo. Lo zero cercato è \( 2.25 \pm {0.25 \over 2}\). In accordo con lo zero "reale" che è circa \( 2.236 \)
Numero di iterazioni
Sappiamo che al primo passo la lunghezza dell'intrvallo è: \( b-a\).
- Alla prima iterazione sarà: \( {b-a \over 2}\)
- Alla seconda \( {{b-a \over 2} \over 2 } = {b-a \over 2^2} \)
- Alla terza iterazione sarà: \( {{b-a \over 2^2} \over 2} = {b-a \over 2^3}\)
- ...
- Se ci fermiamo alla \( n\)-esima iterazione, sarà valida la seguente relazione: \( {b-a \over 2^n} < \epsilon\)
Proviamo a manipolare questa formula, applicando il logaritmo in base 2 ad ambo i membri: $$ log_2\left({b-a \over 2^n}\right) < log_2(\epsilon) $$ $$ log_2(b-a) - log_2(2^n) < log_2(\epsilon) $$ $$ log_2(b-a) - log_2(\epsilon) < n $$ $$ log_2\left({b-a \over \epsilon}\right) < n $$ In particolare la quantità \( \left({b-a \over \epsilon}\right) = {\left( lunghezza([a, b]) \over precisione \right) } = N \) corrisponde al numero di sottointervalli, mentre il logaritmo "per eccesso" di tale quantità corrisponde al numero di iterazioni. Nell'esempio precedente: \( \left\lceil log_2\left( 3-1 \over 0.3\right) \right\rceil = \lceil 2.73 \rceil = 3 \).
