How to Use the Bisection Method for Numerical Computing

Author(s): Chinmay Bhalerao

Originally published on Towards AI.

Understanding the root-finding bisection method and its working

WE CAN CONNECT ON :U+007C LINKEDIN U+007C TWITTER U+007C MEDIUM U+007C SUBSTACK U+007C

A subfield of computer science and mathematics known as numerical computing focuses on employing computer-implemented numerical methods and algorithms to solve mathematical problems. It entails running simulations and calculations to arrive at approximations of answers to mathematical puzzles that could be challenging or impossible to solve analytically.

We have many equations in mathematics. To use those equations in real life, we have to solve those equations. We say “ EQUATION IS SOLVED” when we find its roots.f(x) = 0 where f(x) is a continuous function, and we want to find the value(s) of ‘x’ that makes the function equal to zero. When we put roots into the equation, the equation becomes zero. Let's see a simple example,

f(x) = x * x — 1

x * x — 1 = 0

f(1) = (1) * (1) –1 = 0

f(-1) = (-1) * (-1) –1=0

So 1 and –1 are roots of the above equations.

How did we understand that?

We put 1 in place of x in the equation. That's how we can solve these equations. But sadly, in real life, equations aren't that much simple to solve.

To solve real-life equations, we have many methods known as “ROOT FINDING METHODS”. These methods are very useful for numerical computing, optimization, Interpolation, curve fitting, Numerical analysis, and in many more fields.

If we started talking about evolution, then it would take a whole blog, but let's start directly with the implementation of techniques.

Bisection method

The bisection method in mathematics is a simple approach for locating numerical roots to an equation with a single unknown. The bisection method is the simplest numerical method for resolving the transcendental problem. We shall go into great detail on the bisection approach with solved issues in this article.

To determine the roots of a polynomial problem, utilize the bisection method. It splits and separates the interval in which the equation’s root is located. The continuous functions intermediate theorem serves as the method’s guiding premise. It operates by reducing the distance between the positive and negative intervals until it approaches the right response. By averaging the positive and negative intervals, this technique reduces the distance between the variables.

Although it is a straightforward process, it moves slowly. The bisection method is sometimes referred to as the dichotomy method, binary search method, interval halving method, and root-finding method.

Bisection Method Algorithm

For any continuous function f(x), [Source]

Find two points, say a and b such that a < b and f(a)* f(b) < 0

Find the midpoint of a and b, say “c”

t is the root of the given function if f(c) = 0; else follow the next step

Divide the interval [a, b] — If f(c)*f(a) <0, there exist a root between c and a
– else if f(c) *f (b) < 0, there exist a root between c and b

Repeat above three steps until f(c) = 0.

The bisection method is an approximation method to find the roots of the given equation by repeatedly dividing the interval. This method will divide the interval until the resulting interval is found, which is extremely small.

CODE:

Disclaimer/Warning: This code is just to show how to create a basic bisection code in Python. I am not claiming any optimization in the code and further improvements are needed according to the specific problem statement.

Let's take a simple function.

F(x) = x * x — 3

def fun(x):
 return x * x - 3

Let's write a very basic code to create a simple pipeline for bisection method code.

a = 1 #Approx first root
b = 2 #Approx second root 

#Function declaration
def fun(x):
 return x*x - 3

a_original = fun(a)
b_original = fun(b)
i = 0
while i < 50 : #Do this for 50 times 
 c = (a + b)/2
 c_original = fun(c)

 if c_original < 0:
 a = c
 else:
 b = c
# plt.plot(a)
 print("The a is {}".format(a))
 print("The b is {}".format(b))
 i+=1

The above is very basic but a basic code which is representing the bisection method at a brute-force level.

Let's see its output

The a is 1.5
The b is 2
The a is 1.5
The b is 1.75
The a is 1.625
The b is 1.75
The a is 1.6875
The b is 1.75
The a is 1.71875
The b is 1.75
The a is 1.71875
The b is 1.734375
The a is 1.7265625
The b is 1.734375
The a is 1.73046875
The b is 1.734375
The a is 1.73046875
The b is 1.732421875
The a is 1.7314453125
The b is 1.732421875
The a is 1.73193359375
The b is 1.732421875
The a is 1.73193359375
The b is 1.732177734375
The a is 1.73193359375
The b is 1.7320556640625
The a is 1.73199462890625
The b is 1.7320556640625
The a is 1.732025146484375
The b is 1.7320556640625
The a is 1.7320404052734375
The b is 1.7320556640625
The a is 1.7320480346679688
The b is 1.7320556640625
The a is 1.7320480346679688
The b is 1.7320518493652344
The a is 1.7320499420166016
The b is 1.7320518493652344
The a is 1.7320499420166016
The b is 1.732050895690918
The a is 1.7320504188537598
The b is 1.732050895690918
The a is 1.7320506572723389
The b is 1.732050895690918
The a is 1.7320507764816284
The b is 1.732050895690918
The a is 1.7320507764816284
The b is 1.7320508360862732
The a is 1.7320508062839508
The b is 1.7320508360862732
The a is 1.7320508062839508
The b is 1.732050821185112
The a is 1.7320508062839508
The b is 1.7320508137345314
The a is 1.7320508062839508
The b is 1.732050810009241
The a is 1.7320508062839508
The b is 1.732050808146596
The a is 1.7320508072152734
The b is 1.732050808146596
The a is 1.7320508072152734
The b is 1.7320508076809347
The a is 1.732050807448104
The b is 1.7320508076809347
The a is 1.7320508075645193
The b is 1.7320508076809347
The a is 1.7320508075645193
The b is 1.732050807622727
The a is 1.7320508075645193
The b is 1.7320508075936232
The a is 1.7320508075645193
The b is 1.7320508075790713
The a is 1.7320508075645193
The b is 1.7320508075717953
The a is 1.7320508075681573
The b is 1.7320508075717953
The a is 1.7320508075681573
The b is 1.7320508075699763
The a is 1.7320508075681573
The b is 1.7320508075690668
The a is 1.732050807568612
The b is 1.7320508075690668
The a is 1.7320508075688394
The b is 1.7320508075690668
The a is 1.7320508075688394
The b is 1.7320508075689531
The a is 1.7320508075688394
The b is 1.7320508075688963
The a is 1.7320508075688679
The b is 1.7320508075688963
The a is 1.7320508075688679
The b is 1.732050807568882
The a is 1.732050807568875
The b is 1.732050807568882
The a is 1.732050807568875
The b is 1.7320508075688785
The a is 1.7320508075688767
The b is 1.7320508075688785
The a is 1.7320508075688767
The b is 1.7320508075688776

The above output is of playing with a and b for 50 iterations. The system will get in trouble in processing numbers greater than 16 digits due to limitations. But we can see that the values of roots are coming closer and closer.

The last a is 1.73205080

The last b is 1.73205080

Substituting these latest values in the equation will get you,

F(a) = -0.000176000…..

F(b) = 0.000176000…..

Very close to 0 !!!

Now we know this logic is working. let's optimize the code and visualize the output so that we can understand it better.

import matplotlib.pyplot as plt

def Bisection_method(a, b, iterations):
 def fun(x):
 return x * x - 3

 # Create a figure and axis for the plot
 plt.figure()
 plt.xlabel('x')
 plt.ylabel('y')
 plt.title('Visualization of Equation y = x^2 - 3')

 # Plot the equation y = x^2 - 3 for the range [a, b]
 x_values = [x / 100.0 for x in range(int(a * 100), int(b * 100) + 1)]
 y_values = [fun(x) for x in x_values]
 plt.plot(x_values, y_values, color='orange', label='y = x^2 - 3')

 # Plot initial points a and b on the graph
 plt.plot(a, fun(a), 'ro', label='f(a)')
 plt.plot(b, fun(b), 'go', label='f(b)')

 # Plot the x-axis line
 plt.axhline(linewidth=2, y=0, color='brown', linestyle='dashdot')
 plt.axhline(y=fun(a), color='blue', linestyle='dashdot')
 plt.axhline(y=fun(b), color='blue', linestyle='dashdot')

 plt.legend()
 plt.grid()

 # Update the plot and display it
 plt.pause(1)

 a_vals = [a]
 b_vals = [b]

 i = 0
 while i < iterations:
 c = (a + b) / 2
 c_original = fun(c)

 if c_original < 0:
 a = c
 else:
 b = c
 i += 1

 a_vals.append(a)
 b_vals.append(b)

 # Plot all the values of a and b in different colors
 plt.plot([fun(a_val) for a_val in a_vals], 'mo', label='f(a)',color='orange')
 plt.axhline(y=0, color='brown', linestyle='dashdot')

 plt.plot([fun(b_val) for b_val in b_vals], 'co', label='f(b)')
 plt.axhline(y=0, color='brown', linestyle='dashdot')

 plt.legend()
 plt.grid()

 # Update the plot and display it
# plt.pause(1)

 plt.show()

#Call the function with initial values for a, b, and the number of iterations
a_initial = 1
b_initial = 2
iterations = 50
Bisection_method(a_initial, b_initial, iterations)

I modified this code such that it will take inputs and it will display the graph of roots.

In the above fig, we can see our starting points and their F(x) values. the red highlighted line is what we want to achieve with these initial roots.

In the above figure, I have plotted the outputs of the last 10 points out of 50. You can see the values converging towards 0 and the final few points are almost 0. It is a sign that we got out roots. Iterations are the limit you can put to control the whole execution. the parameter could be the threshold value for the Function. So either you have to stop after completing a certain number of iterations or if you achieved a certain threshold value.

You can change the function and use this code to find roots for your own equation, or you can directly use the below link, which will land you on the bisection method online calculator.

Bisection Method Online Calculator

The bisection method online calculator is a simple and reliable tool for finding the real root of non-linear equations using…

www.codesansar.com

Advantages of the Bisection method:

Convergence: dependability guarantees that the approach will come up with a solution so long as a root-containing interval is given.

Simpleness: The method is simple theoretically and simple to use.

Robustness: Compared to certain other root-finding techniques, the bisection method is less sensitive to the original guess.

Interval Refinement: Each improvement makes sure that with each iteration, the solution is more precise.

No derivative requirement: This makes it appropriate for functions for which derivatives are either unavailable or difficult to compute.

Global Convergence: This approach will finally locate a root if one is present inside the interval.

Limitations of the Bisection method:

Slow Convergence: The method can be slow compared to other root-finding algorithms with faster convergence rates, especially for functions with steep slopes, even though it ensures convergence.

Requirement of Interval:The procedure might not be appropriate if such an interval is unknown or challenging to determine.

Only One Root Can Be Found: The bisection method is made to only uncover one root inside the supplied range [a, b]. The procedure will arrive at one of a function’s roots if it has more than one inside that range

Limited Applicability to Complex Equations: The bisection method is most suitable for equations with a single real root within the specified interval.

To overcome these limitations, we have many other methods which are on the advanced level for root finding with different mechanisms. We will cover those in the next series of blogs.

If you have found this article insightful

It is a proven fact that “Generosity makes you a happier person”; therefore, Give claps to the article if you liked it. If you found this article insightful, follow me on Linkedin and Medium. You can also subscribe to get notified when I publish articles. Let’s create a community! Thanks for your support!

You can click here to buy me coffee.

Understanding LangChain U+1F99C️U+1F517: PART 1

Theoretical understanding of chains, prompts, and other important modules in Langchain

pub.towardsai.net

A Practical Guide to Selecting CNN Architectures for Computer Vision Applications

From LeNet to EfficientNet: Choosing the Best CNN Architecture for Your Project

levelup.gitconnected.com

Comprehensive Guide: Top Computer Vision Resources All in One Blog

Save this blog for comprehensive resources for computer vision

medium.com

Boost Your Data Science, ML, and CV Projects: Essential Tools for Effective Project Management

Make your builds and projects faster with these tools

pub.towardsai.net

Signing off,

Chinmay

Join thousands of data leaders on the AI newsletter. Join over 80,000 subscribers and keep up to date with the latest developments in AI. From research to projects and ideas. If you are building an AI startup, an AI-related product, or a service, we invite you to consider becoming a sponsor.

Published via Towards AI