Bisection Method

Bisection method is a numerical method to find the root of a polynomial. In bisection method we iteratively reach to the solution by narrowing down after guessing two values which enclose the actual solution.

Bisection method is the same thing as guess the number game you might have played in your school, where the player guesses the number and then receives a hint about whether the actual number is greater or lesser the guess. The player keeps track of the hints and tries to reach the actual number in minimum number of guesses. Here is as sample game (the solution is 4)

Gameplay1: Random Guesses

1. Guess: 8 (hint: the actual number is lower)
2. Guess: 2 (hint: the actual number is higher)
3. Guess: 7 (hint: the actual number is lower)
4. Guess: 5 (hint: the actual number is lower)
5. Guess: 4 (correct)

Gameplay2: Cutting into Halves

1. Guess: 5 (hint: the actual number is lower)
2. Guess: 2 (hint: the actual number is higher)
3. Guess: 4 (correct)

In the above two gameplays it’s clear that it is better to cut the bounded region in half than to take blind guesses. Bisection method uses the same technique to solve an equation and approaches to the solution by dividing the possible solution region to half and then deciding which side will contain the solution. Hint: The side where the function meets x-axis is the side to go. The values for which the function gives values with opposite signs encloses the point where the function meets x-axis.

Steps

1. Guess the initial upper and lower bounds first. (which must enclose the actual solution)
2. Check if the initial upper and lower bounds are correct. If the function gives values with opposite signs for both values, then the bounds are correct.
3. Iteratively:
   • Calculate the midpoint of the upper and lower bounds
   • Calculate the value of the function for all the three values: lowerBound, upperBound and the midpoint
   • Decide which side to go. (The side which contains the solution/where the function changes sign)
     Replace either lower or upper bound with the midpoint to cut the region into half. In other words, choose either lowerBound, midpoint or midpoint, upperBound as the new lowerBound and upperBound
   • Repeat until the value of midpoint reaches the desired decimal places or the difference between lower and upper bound is less than the tolerable error.
4. Midpoint is your desired solution.

Example

f(x) = x² - 3

Let a: lower bound , b:upper bound and m: midpoint for brevity.

Initial Bounds: a = 1 & b=2

Now the error is tolerable hence our desired solution is 1.7266

This example was a simple but in real life it takes a huge number of iterations to reach the desired root hence we use computer to help us.

by Arifullah Jan and last modified on Jun 30, 2019