Cristian Consonni bio photo

Cristian Consonni

Ph.D. in Computer Science, free software activist, physicist and storyteller

Email Twitter Facebook LinkedIn Github Stackoverflow keybase

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 bit1 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\), se2

\[|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\]
  1. Questa è una semplificazione, per sapere più dettagli su come un numero con la virgola viene rappresentato consultate la pagina “Numero in virgola mobile” su Wikipedia e questa immagine

  2. Bisogna usare il valore assoluto perché si sta calcolando la distanza di \(f(c)\) da zero, altrimenti questo check passerebbe se f(c) < 0).