The Algorithm for The Bisection Method for Approximating Roots

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.