Bisection method

Remarks

Clause 1 holds by induction, since the new interval keeps an endpoint where $f$ is negative and one where it is positive. The intermediate value theorem then gives a zero in it. Clause 2 is immediate, and the nested intervals theorem gives a common limit $r$ of $a_k$ and $b_k$; by continuity $f(r)^2 = \lim f(a_k) f(b_k) \le 0$, so $f(r) = 0$. Example: for $f(x) = x^2 - 2$ on $[1, 2]$, the midpoints are $1.5, 1.25, 1.375, 1.4375, \ldots$, and $20$ steps locate $\sqrt{2}$ within $2^{-21} < 5 \times 10^{-7}$. Continuity is needed: $f(x) = 1/x$ for $x \ne 0$ and $f(0) = 1$ changes sign on $[-1, 1]$, and bisection gives $[-1, 0], [-1/2, 0], \ldots$ and converges to $0$, which is not a zero. The error bound halves at each step, so the method converges linearly with ratio $1/2$ in the sense of the error bound, whatever $f$ is.

Going deeper

For a student

Bisection is the simplest root-finding algorithm and the most robust: it needs only continuity and a sign change, and its error bound is known in advance. It gains one binary digit per step, so it is slow compared with Newton's method or the secant method. Practical methods such as Brent's method combine a fast open method with bisection steps to keep the guarantee. It is also the constructive content of the intermediate value theorem.