Bisection Method

Bisection Method Formula

In Mathematics, the bisection method is used to find the root of a polynomial function. For further processing, it bisects the interval and then selects a sub-interval in which the root must lie and the solution is iteratively reached by narrowing down the values after guessing, which encloses the actual solution. In this method, the interval distance between the initial values is treated as a line segment. It then successively divides the interval in half and replaces one endpoint with the midpoint so that the root is bracketed. This method is based on The Intermediate Value Theorem and is very simple and robust and easy to implement. There are various names given to this method such as “ the interval halving method”, “the binary search method”, “the dichotomy method” and “Bolzano’s Method”.

Finding Root by Bisection Method

As stated above, the Bisection method program is a root-finding method which we often come across while dealing with Numerical Analysis. It is also known as the Bisection Method Numerical Analysis. It is based on Bolzano's theorem for continuous functions. So let us understand what Bolzano’s theorem says,


Theorem (Bolzano): If on an interval [a, b] and f(a)·f(b) < 0, a function f(x) is found to be continuous, then there exists a value c such that c ∈ (a, b) or which f(c) = 0. The graph given below shows a continuous function


The bisection method problems can be solved by using the Bisection Method formula to find the value c of the function f(x) that crosses the x-axis. In this case, the value c is an approximate value of the root of the function f(x). In this bisection method program, the value of the tolerance we set for the algorithm determines the value of c where it gets to the real root. One such bisection method is explained below.

Bisection Method Step by Step

To solve bisection method problems, given below is the step by step explanation of the working of the Bisection Method algorithm for a given function f(x):

Step 1. Choose two values, a and b such that f(a) > 0 and f(b) < 0 .

Step 2. Calculate a midpoint c as the arithmetic mean between a and b such that c = (a + b) / 2. This is called interval halving.

Step 3. Evaluate the function f for the value of c.

Step 4. The root of the function is found only if the value of f(c) = 0.

Step 5. If (c) ≠ 0, then we need to check the sign :

  1. we replace a with c, if f(c) has the same sign as f(a) and we keep the same value for b

  2. we replace b with c, if f(c) has the same sign as f(b), and we keep the same value for a

     To get the right value with the new value of a or b, we go back to step 2. and  recalculate c. 

Bisection Method Problems

The best way of understanding how the algorithm works is by looking at a bisection method example and solving it by using the bisection method formula.


Example 1:  Find the root of f(x) = 10 - x2


Solution: The calculation of the value is described below in the table:


i

a

b

c

f(a)

f(b)

f(c)

0

-2

5

1.5

6

-15

7.75

1

1.5

5

3.25

7.75

-15

-0.5625

2

1.5

3.25

2.375

7.75

-0.5625

4.359375

3

2.375

3.25

2.8125

4.359375

-0.5625

2.0898438

4

2.8125

3.25

3.03125

2.0898438

-0.5625

0.8115234

5

3.03125

3.25

3.140625

0.8115234

-0.5625

0.1364746

6

3.140625

3.25

3.1953125

0.1364746

-0.5625

-0.210022

7

3.140625

3.1953125

3.1679688

0.1364746

-0.210022

-0.036026

8

3.140625

3.1679688

3.1542969

0.1364746

-0.036026

0.0504112

9

3.1542969

3.1679688

3.1611328

0.0504112

-0.036026

0.0072393



At initialization (i = 0) we choose a = -2 and b = 5. After evaluation of the function in both points we find 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 at a particular point, which is the root we need to find.


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

By solving our quadratic equations in a classic way we can check our result:

10 - x2 =0

x2= 10

x = 10

x = ±3.16227766

Below you find 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 is the root of the function f(x)).

for f(x) = 10 – x2

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


FAQ (Frequently Asked Questions)

Question1: When Does a Function is said to be Continuous?

Answer: A function is said to be continuous when small changes in the argument bring about small changes in the result too. For example, small changes in x changes will give small changes in f(x) too. If the change in x is in small steps then the change in f(x) will also be in small steps and not big “jumps”. This shows that the argument and result are directly proportional to each other, such that if one increases then the other increases too. This makes a function continuous.

Question 2: What does f(a)·f(b) < 0 Means?

Answer: The statement f(a)·f(b) < 0 means that f(a)·f(b)  is less than zero such that f(a) and f(b) both have different signs where one of them is above the x-axis and the other one is below the x-axis. To explain this, we can take an example of a function that crosses the x-axis. Suppose if we plot a function f(x) at some point, it will cross the x-axis such that the value of x is the root of the equation f(x) = 0 for which the plot is crossing the x-axis.