In this guide, we will learn the implementation of the Bisection method for finding the real root of a non-linear polynomial equation using Python.
Before we start, let’s understand the concept of the Bisection Method. The bisection method is simply a root-finding algorithm that can be used for any continuous function, say f(x) on an interval [a,b] where the value of the function ranges from a to b.
The basic concept of the bisection method is to bisect or divide the interval into 2 parts. And a solution must be in either of the subintervals. Then, the algorithm picks the subinterval where the sign of the given function changes and the process is iterated or repeated.
it is important to observe that the bisection method does not always produce a flawless solution to a non-linear equation (where f(x) is equal to 0), it can give an estimate of the absolute error in the approximation.
Now that we understand the basics of the bisection method, let’s take an example to make this easier for us. Suppose, we are asked to find the root of the polynomial equation given below:
to start the implementation in python, we should first define a function f(x) that stores the given equation and returns the function value. In this case, the value of the function defines as f(x) is stored in y.
def f(x): y = 3* x**3 + x**2 - 2*x + 4 return y
since the bisection method most importantly requires an interval in which the function value will be found, our next step is to define the intervals. Here, we have taken 2 variables a and b which will be used as the range or interval.
a = -100 b = 200
then, let’s define a function named ‘bisection’ having a range from a to b. In the code below, we have an if condition as follows:
if f(a)*f(b)>0: print("Sorry! There is no root found.") return c =a
if f(a) * f(b) > 0, the message above will be displayed because both f(a) and f(b) have the same sign. And it returns the value of a after assigning it to the variable c. please note that the variable c is referred to the midpoint value of the interval [a,b]
as we have already established that c is the midpoint value of the interval [a,b], we know that:
c = (a+b)/2
then we run an iterable while loop in python until the algorithm finds the root of the polynomial in any one of the subintervals.
while ((b-a)>=0.01): c = (a+b)/2 if f(c)==0: break #the midpt is the root st f(c) = 0 if f(c)*f(a)<0: b = c #shrink interval from right else: a=c print("The root of the equation is: ", c) bisection(a,b)
let’s interpret the loop now.
We have assigned a midpoint-like value to c at the beginning of the loop. Thus, creating subintervals. Then we have introduced an if-else structure for a set of conditions. Please note that the condition for the loop is:
while ((b-a)>=0.01): c = (a+b)/2
this condition ensures that the interval is very small. Thereby eliminating or minimizing chances of errors while finding the root.
For the following condition, the midpoint c is the root such that f(c) = 0, and if this condition is true then, the loop breaks and displays the root of the polynomial equation.
if f(c)==0: break
if it is not true, it moves to the next condition, that is:
if f(c)*f(a)<0: b = c #shrink interval from right
if f(c) * f(a) < 0 is true for the moment, then the interval is narrowed or shrunk from right, simply put, the interval is narrowed from c to b.
In f(a) * f(c) < 0, it means that either f(a) is negative or f(c) is negative. In the first case, let’s suppose that f(a) is greater than zero or positive. Then, the line has to range over the horizontal axis to reach the midpoint function f(c) that is negative. In the other case, f(c) would be greater than zero, and f(a) would be negative. Here, we can opt to have the new b as c.
if both the conditions are not true, the program returns the value of c. it is assumed that:
after the loop runs iteratively and it finds a value of the root in either one of the subintervals, the root is displayed by calling the function.
print("The root of the equation is: ", c) bisection(a,b)
And we’re done with the interpretation! Let’s look at the final implementation code and run the program.
# suppose, we are asked to find the root of the equation given below: #y = 3x^3 + x^2 - 2x + 4 def f(x): y = 3* x**3 + x**2 - 2*x + 4 return y a = -100 b = 200 def bisection(a,b): if f(a)*f(b)>0: print("Sorry! There is no root found.") return c =a while ((b-a)>=0.01): c = (a+b)/2 if f(c)==0: break #the midpt is the root st f(c) = 0 if f(c)*f(a)<0: b = c #shrink interval from right else: a=c print("The root of the equation is: ", c) bisection(a,b)
And here’s the root of the polynomial considered in this example:
The root of the equation is: -1.435546875
Submitted by KHYATI MADDALI (khyatimaddali)
Download packets of source code on Coders Packet