Bisection method

Level FundamentalDifficulty ★★★★★Method⌖ Open in the map

What is it?

Keep an interval where $f$ changes sign and halve it each step. Slow (one bit per step) but impossible to break: Bolzano's theorem guarantees a root inside. It is binary search on a continuous function.

Formulas

$m = \frac{a + b}{2}, \qquad [a,b] \leftarrow \begin{cases}[a, m] & f(a)f(m) < 0 \\ [m, b] & f(a)f(m) \ge 0\end{cases}$; $|x_k - x^\ast| \le \frac{b - a}{2^{k+1}}$
guaranteed error after $k$ steps

Where it shows up in computing

Scientific computing★★★★★frequentScientific computing and algorithms
Robust solvers (Brent's method) combine bisection's guarantee with faster steps.
Ray tracing★★★★★frequentComputer graphics
Intersecting rays with implicit surfaces or height fields often brackets the hit and bisects.
Algorithm analysis and complexity★★★★★indirectScientific computing and algorithms
Same idea as binary search (and git bisect): halving gives $O(\log n)$ steps.

Where is it used?

Computing topics reachable from here, through the chain of ideas that leads to them:

λ Scientific computing and algorithms

Scientific computing★★★★★
Algorithm analysis and complexity★★★★★

3D Computer graphics

Ray tracing★★★★★
Ray tracing→Signed distance fields and ray marching★★★★★
Ray tracing→The rendering equation★★★★★

Exercises

1Computation

How many bisection steps on $[1, 2]$ guarantee $\sqrt 2$ to within $10^{-6}$ ?

Solution

$2^{-(k+1)} < 10^{-6} \iff k + 1 > 6\log_2 10 \approx 19.9$ : $k = 19$ steps.

This page has the essentials. A fuller treatment (intuition, formal definition, worked example) is on the way.