Metodo di bisezione

Si inizia con un intervallo $[a,b]$ che include uno zero, e uno solo, in modo che sia $f(a)f(b) < 0$. L'algoritmo di bisezione dimezza l'intervallo ad ogni iterazione, raffinando sempre più la stima di $x_0$:

1. $c = (a+b)/2$
2. se $f(a)f(c)<0$ si ridefinisce $b=c$; altrimenti se $f(b)f(c)<0$ si ridefinisce $a=c$.
3. si ottiene così un nuovo intervallo $[a,b]$ di ampiezza dimezzata, su cui si ripete il procedimento.

La convergenza è garantita (è impossibile "perdere" lo zero), e il logaritmo dell'errore diminuisce linearmente col numero di iterazioni. Possono sorgere difficoltà relativamente al criterio di arresto. Ad esempio:

• Errore assoluto: $\vert a-b\vert<\epsilon$. Questo può dare problemi se $x_0$ è molto grande: gli errori di arrotondamento in $\vert a-b\vert$ potrebbero essere più grandi di $\epsilon$.
• Errore relativo: $\vert a-b\vert<\epsilon a$. Questo può dare problemi in prossimità di $x=0$.
• Se la pendenza di $f(x)$ vicino allo zero è molto piccola, potrebbe esserci un intero intervallo in cui $f(x)$ è indistinguibile da zero nella rappresentazione della macchina.