The Bisection Method for root finding

The most basic problem in Numerical Analysis (methods) is the root-finding problem.

For a given function f(x), the process of finding the root involves finding the value of x for which f(x) = 0. If the function equals zero, x is the root of the function.

A root of the equation f(x) = 0 is also called a zero of the function f(x).

The Bisection Method, also called the interval halving method, the binary search method, or the dichotomy method. is based on the Bolzano’s theorem for continuous functions.

Theorem (Bolzano): If a function f(x) is continuous on an interval [a, b] and f(a)·f(b) < 0, then a value c ∈ (a, b) exist for which f(c) = 0.

Example of a continuous function

Image: Example of a continuous function

A function is continuous when small changes of the argument gives also in small changes in the result. In other words, if x changes with small steps f(x) will also change with small steps, it doesn’t give big “jumps” of the result.

f(a)·f(b) < 0 means that f(a) and f(b) have different signs, which means that one of them is above the x-axis and the other one below the x-axis. In this case, if we plot the f(x) function, at some point, it will cross the x-axis. The x value for which the plot is crossing the x-axis is the root of the equation f(x) = 0.

The Bisection Method looks to find the value c for which the plot of the function f crosses the x-axis. The c value is in this case is an approximation of the root of the function f(x). How close the value of c gets to the real root depends on the value of the tolerance we set for the algorithm.

The Bisection Method explained

Image: The Bisection Method explained

For a given function f(x),the Bisection Method algorithm works as follows:

  1. two values a and b are chosen for which f(a) > 0 and f(b) < 0 (or the other way around)
  2. interval halving: a midpoint c is calculated as the arithmetic mean between a and b, c = (a + b) / 2
  3. the function f is evaluated for the value of c
  4. if f(c) = 0 means that we found the root of the function, which is c
  5. if f(c) ≠ 0 we check the sign of f(c):
    • if f(c) has the same sign as f(a) we replace a with c and we keep the same value for b
    • if f(c) has the same sign as f(b), we replace b with c and we keep the same value for a
  6. we go back to step 2. and recalculate c with the new value of a or b

The algorithm ends when the values of f(c) is less than a defined tolerance (e.g. 0.001). In this case we say that c is close enough to be the root of the function for which f(c) ~= 0.

In order to avoid too many iterations, we can set a maximum number of iterations (e.g. 1000) and even if we are above the defined tolerance, we keep the last value of c as the root of our function.

The Bisection Method Explained as a Logic Diagram

Image: The Bisection Method Explained as a Logic Diagram

The best way of understanding how the algorithm work is by looking at an example.

For the function f(x) below find the best approximation of the root given the tolerance of TOL = 0.01 and a maximum of NMAX = 1000 iterations.

\[f(x) = 10 – x^2 \]

In the table below we are going to calculate the values described in the logic diagram above:

iabcf(a)f(b)f(c)
0-251.56-157.75
11.553.257.75-15-0.5625
21.53.252.3757.75-0.56254.359375
32.3753.252.81254.359375-0.56252.0898438
42.81253.253.031252.0898438-0.56250.8115234
53.031253.253.1406250.8115234-0.56250.1364746
63.1406253.253.19531250.1364746-0.5625-0.2100220
73.1406253.19531253.16796880.1364746-0.2100220-0.0360260
83.1406253.16796883.15429690.1364746-0.03602600.0504112
93.15429693.16796883.16113280.0504112-0.03602600.0072393

At initialization (i = 0) we choose a = -2 and b = 5. After evaluating the function in both points we can see that f(a) is positive while f(b) is negative. This means that between these points, the plot of the function will cross the x-axis in a particular point, which is the root we need to find.

After 9 iterations the value of f(c) is less than our defined tolerance (0.0072393 < 0.01). This means that the value that approximates best the root of the function f is the last value of c = 3.1611328.

We can check our result by solving our quadratic equations in a classic way:

\[ \begin{equation*} \begin{split}
10 – x^2 &= 0\\
x^2 &= 10\\
x &= \sqrt{10} = \pm 3.16227766
\end{split} \end{equation*} \]

Below you can see an animation of the f(x) plot for every iteration. Notice how the [a, b] interval (red horizontal line) is halved at each iteration, until it’s converging into a point where the plot is crossing the x-axis (value of x in that point being the root of the function f).

The Bisection Method animation

Image: The Bisection Method animation
for f(x) = 10 – x2

The example calculated in the table is also executed in the C code below. The results are the same as those calculated in the table. Use this C code (copy and past to into a *.c file and execute) to examine the impact of tolerance (e.g 0.0001) on the number of iterations necessary to converge to a solution.

#include<stdio.h>
#include<math.h>

/* SIGN function definition as a macro */
#define sign(x) (x > 0) ? 1 : ((x < 0) ? -1 : 0)

/* functions prototype */
float f (float x);
int f_disp (int i, float a, float b, float c);

int main(void){
 float a = -2; /* left point */
 float b = 5; /* right point */
 float TOL = 1E-2; /* tolerance */
 float NMAX = 1000; /* maximum number of iterations */
 float c = 0; /* estimated root */
 int i = 0; /* index */
 
 c = (a + b)/2; /* calculate the midpoint */
 
 /* Display the table header and initial data */
 printf("i\ta\t\tb\t\tc\t\tf(a)\t\tf(b)\t\tf(c)\n");
 f_disp(i, a, b, c);
 
 /* Evaluate loop until the result is less than the tolerance
 * maximum number of iterations is not yet reached*/
 
 if (f(c) == 0){
  /* If the first midpoint gives f(c) = 0, c is the root */
  printf("Root is: %f \n", c);}
  else{
   while ((fabs(f(c)) > TOL) && (i<=NMAX)){
    if (sign(f(c)) == sign(f(a))){
     /* f(c) has same sign as f(a) */
     a = c;}
    else{
     /* f(c) has same sign as f(b) */
     b = c;} 
    c = (a+b)/2; /* midpoint update */
    f_disp(i+1, a, b, c); /* display current data */
    i++; /* index increment */}}
 
 /* Display results */
 printf("\nRoot is c=%.7f found after %d iterations\n", c, i);
 printf("The value of the function f(c) is: %.10f\n", f(c));
 return 0;}

/* function definition */
float f (float x){
 float y;
 y = 10 - x*x;
 return y;}

/* display function definition */
int f_disp (int i, float a, float b, float c){
 printf("%d\t%.7f\t%.7f\t%.7f\t", i, a, b, c);
 printf("%.7f\t%.7f\t%.7f\n", f(a), f(b), f(c));
 return 0;}

The same algorithm is implemented in a Scilab script. Play with the a, b, TOL and NMAX parameters to understand their impact on the method.

// Function definition
deff('y=f(x)','y=10-x^2;');

// Parameter definition
a = -2; // left point
b = 5; // right point
TOL = 1e-2; // tolerance
NMAX = 1000; // maximum number of iterations
c = (a+b)/2; // midpoint
i = 0; // index

// Loop until function result less than tolerance AND 
// maximum number of iternations is not yet reached

if (f(c) == 0)
 // If the first midpoint gives f(c) = 0, c is the root
 disp(['Root is: ' string(c)]);
else
 while ((abs(f(c)) > TOL) & (i <= NMAX))
  if (sign(f(c)) == sign(f(a)))
   // f(c) has same sign as f(a)
   a = c;
  else
   // f(c) has same sign as f(b)
   b = c;
  end
  c = (a+b)/2; // midpoint update
  i = i + 1; // index increment
 end
end
clc();
// Display results
format(10); // number of decimal places to display
disp(['Root is: ' string(c) ', found in ' string(i) ' steps.'])
disp(['The value of the function f(c) is: ' string(f(c))])

As you can see, the Bisection Method converges to a solution which depends on the tolerance and number of iteration the algorithm performs. There is a dependency between the tolerance and number of iterations. For a particular tolerance we can calculate how many iterations n we need to perform.

Every iteration the algorithm generates a series of intervals [an, bn] which is half of the previous one:

\[b_n – a_n = \frac{b-a}{2^n} =|c-x| \tag{1}\]

The tolerance ε is the absolute value of the difference between the actual root of the function x and the approximation c.

\[\varepsilon=|c-x| \tag{2}\]

For the algorithm to converge within an absolute error tolerance (ε), we need to have:

\[|c-x| \le \varepsilon \tag{3}\]

By replacing inequality (3) with equation (1), we get:

\[\frac{b-a}{2^n}\le \varepsilon \tag{4}\]

Solving inequality (4), we obtain:

\[2^n \ge \frac{b-a}{\varepsilon} \tag{5}\]

We apply the logarithm function to both sides of the inequality (5):

\[log(2^n) \ge log\left (\frac{b-a}{\varepsilon} \right )  \tag{6}\]

Solving (6), we get:

\[ \begin{equation*} \begin{split}
n \cdot log(2) &\ge log\left (\frac{b-a}{\varepsilon} \right )\\
n &\ge \frac{log\left (\frac{b-a}{\varepsilon} \right )}{log(2)}
\end{split} \end{equation*} \]

From the above result we can understand that, using the Bisection Method, in order to calculate an approximate root of a function within tolerance ε, the number n of iterations we need to perform is:

\[ \begin{equation} \begin{split}
\bbox[#FFFF9D]{n \ge \frac{log\left (\frac{b-a}{\varepsilon}\right )}{log(2)}}
\end{split} \end{equation} \]

For the example presented in this tutorial our algorithm performed 9 iterations until it found the solution within the imposed tolerance. Let’s apply the above formula to see what is the minimum calculated number of iterations.

\[ \begin{equation*} \begin{split}
a &= -2\\
b &= 5\\
\varepsilon &= 0.01\\
n &\ge \frac{log\left (\frac{5+2}{0.01} \right )}{log(2)}\\
n &\ge 9.45
\end{split} \end{equation*} \]

The result shown that we need at least 9 iterations (the integer of 9.45) to converge the solution within the predefined tolerance, which is exactly how many iterations our algorithm performed.

The Bisection Method is a simple root finding method, easy to implement and very robust. The disadvantages of this method is that it’s relatively slow. Because of this, most of the time, the bisection method is used as a starting point to obtain a rough value of the solution which is used later as a starting point for more rapidly converging methods.

The Bisection Method is summarized in the poster below:

The Bisection Method Explained Poster

Image: The Bisection Method Explained Poster (click on it for higher resolution)

Test your knowledge in the Bisection Method by taking the quiz below:

QUIZ! (click to open)

For any questions or observations regarding this tutorial please use the comment form below.

Don’t forget to Like, Share and Subscribe!

4 Comments

  1. Hussain Khan
  2. John Lee
  3. lonz
  4. mahmoudali ali

Leave a Reply

Ad Blocker Detected

Dear user, Our website provides free and high quality content by displaying ads to our visitors. Please support us by disabling your Ad blocker for our site. Thank you!

Refresh