The bisection algorithm

The zero theorem does not say where the zero is, only that it exists. The bisection algorithm finds it by successive approximations, halving the interval at each step.

In brief — Procedure

1. Start from $[a,b]$ with $f(a)\cdot f(b)<0$.
2. Compute the midpoint $m = \dfrac{a+b}{2}$ and the sign of $f(m)$.
3. If $f(a)\cdot f(m) < 0$: the zero is in $[a,m]$, set $b=m$. Otherwise it is in $[m,b]$, set $a=m$.
4. Repeat from step 2 until $|b-a|<\varepsilon$ (the desired precision).

At each step the interval halves: after $n$ steps the error is $\le\dfrac{b-a}{2^n}$.

Example — Bisection applied to $\ln(x+3)-3x+0{,}1=0$

Let $f(x) = \ln(x+3)-3x+0{,}1$. Let us look for a zero.

$f(0) = \ln 3 + 0{,}1 \approx 1{,}2 > 0$; $\quad f(1) = \ln 4 - 3 + 0{,}1 \approx -1{,}5 < 0$. Opposite signs: there is a zero in $[0,1]$.

Step	$a$	$b$	$m$	$f(m)$
1	$0$	$1$	$0{,}5$	$f(0{,}5)\approx -0{,}15 < 0$
2	$0$	$0{,}5$	$0{,}25$	$f(0{,}25)\approx 0{,}43 > 0$
3	$0{,}25$	$0{,}5$	$0{,}375$	$f(0{,}375)\approx 0{,}12 > 0$
4	$0{,}375$	$0{,}5$	$0{,}4375$	$f(0{,}4375)\approx -0{,}02 < 0$
5	$0{,}375$	$0{,}4375$	$0{,}406$	$f(0{,}406)\approx 0{,}05 > 0$

After 5 steps the zero is in $[0{,}406;\ 0{,}4375]$, with error $<0{,}032$. Approximate value: $x\approx 0{,}42$.

The strength of bisection is its robustness: it requires only being able to evaluate $f$ and recognise its sign, and it always converges (provided one starts from a change of sign). The price is its slowness: it gains about one decimal digit every $3{,}3$ iterations.

Links

Topics: Continuita
Concepts: Algoritmo di bisezione · Teorema degli zeri
Skills: Stimare · Usare formule