 # 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).