The Algorithm for The Bisection Method for Approximating Roots

We will now look at the algorithm for the bisection method in approximating roots of functions.

Obtain a function $f$, the left endpoint $a$ and the right endpoint $b$ of the interval $[a, b]$ containing a root $\alpha$. Also obtain a maximum number of iterations and an error tolerance $\epsilon$.

For $i = 1, 2, ...$ up to the maximum number of iterations:

Step 1: First compute the value of $f$ under the right end point, that is, compute $f(b)$.

Step 2: Set $c = \frac{1}{2} (a + b)$. The value of $c$ is located in the middle of the interval $[a, b]$.

Step 3: Compute the value of $f$ under the midpoint, that is, compute $f(c)$.

Step 4: If $f(c) = 0$, then stop the iteration process. $c$ is the root $\alpha$

Step 5: Check the accuracy requirement:

(1)

\begin{align} \quad \frac{b - a}{2} < \epsilon \end{align}

If half of the length of the interval $[a, b]$ is less than epsilon, then the point $c$ is within $\epsilon$ on the root $\alpha$, and so stop the iteration process. $c$ is a sufficiently close approximation to the root $\alpha$.

Step 6: If $f(b) f(c) < 0$, then set $a = c$, and if $f(b) f(c) > 0$ then set $b = c$. This ensures that the smaller interval still contains the root $\alpha$.

If the accuracy requirement $\epsilon$ is not achieved after the maximum number of iterations allowed, then print out a failure message.