Note sul metodo della bisezione per trovare gli zeri di una funzione continua.

Approfitto di una domanda che ho ricevuto rispetto al metodo della bisezione per elaborare meglio un dettaglio che ho omesso a lezione.

Lo pseudocodice fornito nelle slides riporta alla linea 5 il controllo:

\[\mathit{\mathbf{if}} \; ( f(c) = 0) \lor ((b - a)/2) < \varepsilon ) \; \mathit{\mathbf{then}} \dots\]

in particolare viene controllato se \(f(c) = 0\). Questo è teoricamente corretto, ma da un punto di vista computazionale è una richiesta molto stringente. Il problema è che, in generale, si possono compiere degli errori di arrotondamento (perché comunque qualsiasi valore è salvato in una cella di memoria composta da un numero finito di byte (bit) e quindi non è possibile rappresentare numeri arbitrari) mentre con quel controllo si sta richiedendo che il valore di \(f(c)\) sia esattamente zero.

Diciamo che se il valore di f(c) fosse rappresentato con 4 bit¹ questo equivarrebbe a controllare che in memoria sia rappresentata la sequenza di bit \(\texttt{0000}\).

Per semplificare questo vincolo si può introdurre un nuovo valore di tolleranza, chiamato \(\varepsilon_y\), e controllare, invece che \(f(c) == 0\), se²

\[|f(c)| < \varepsilon_y\]

il primo epsilon, che possiamo chiamare \(\varepsilon_x\), stabilisce qual è la tolleranza all’errore rispetto alle \(x\), \(\varepsilon_y\) ha lo stesso ruolo rispetto alle \(y\).

Si tratta comunque di un dettaglio perché:

• come detto sopra, è un errore di computazione dovuto al fatto che i computer reali hanno una quantità finita di memoria.
• In alcuni casi è possibile esprimere \(\varepsilon_y\) in funzione di \(\varepsilon_x\) cioè è possibile scegliere un valore di \(\varepsilon_y\) tale per cui si può essere sicuri che l’errore sulle \(x\) sia comunque più piccolo di \(\varepsilon_x\). In pratica, con la funzione \(f(x) = x^3 - x -2\) data per esercizio era possibile usare \(\varepsilon_y = \varepsilon_x\), quindi controllare se:

\[|f(c)| < \varepsilon_x\]

---