How to do the Bisection method in Python
Solution 1
Basic Technique
Here's some code showing the basic technique:
>>> def samesign(a, b):
return a * b > 0
>>> def bisect(func, low, high):
'Find root of continuous function where f(low) and f(high) have opposite signs'
assert not samesign(func(low), func(high))
for i in range(54):
midpoint = (low + high) / 2.0
if samesign(func(low), func(midpoint)):
low = midpoint
else:
high = midpoint
return midpoint
>>> def f(x):
return -26 + 85*x - 91*x**2 +44*x**3 -8*x**4 + x**5
>>> x = bisect(f, 0, 1)
>>> print(x, f(x))
0.557025516287 3.74700270811e-16
Tolerance
To exit early when a given tolerance is achieved, add a test at the end of the loop:
def bisect(func, low, high, tolerance=None):
assert not samesign(func(low), func(high))
for i in range(54):
midpoint = (low + high) / 2.0
if samesign(func(low), func(midpoint)):
low = midpoint
else:
high = midpoint
if tolerance is not None and abs(high - low) < tolerance:
break
return midpoint
Solution 2
You could see the solution in an earlier Stack Overflow question here that uses scipy.optimize.bisect. Or, if your purpose is learning, the pseudocode in the Wikipedia entry on the bisection method is a good guide to doing your own implementation in Python, as suggested by a commenter on the the earlier question.
Solution 3
My implementation is more generic and yet simpler than the other solutions: (and public domain)
def solve(func, x = 0.0, step = 1e3, prec = 1e-10):
"""Find a root of func(x) using the bisection method.
The function may be rising or falling, or a boolean expression, as long as
the end points have differing signs or boolean values.
Examples:
solve(lambda x: x**3 > 1000) to calculate the cubic root of 1000.
solve(math.sin, x=6, step=1) to solve sin(x)=0 with x=[6,7).
"""
test = lambda x: func(x) > 0 # Convert into bool function
begin, end = test(x), test(x + step)
assert begin is not end # func(x) and func(x+step) must be on opposite sides
while abs(step) > prec:
step *= 0.5
if test(x + step) is not end: x += step
return x
Solution 4
# Defining Function
def f(x):
return x**3-5*x-9
# Implementing Bisection Method
def bisection(x0,x1,e):
step = 1
print('\n\n*** BISECTION METHOD IMPLEMENTATION ***')
condition = True
while condition:
x2 = (x0 + x1)/2
print('Iteration-%d, x2 = %0.6f and f(x2) = %0.6f' % (step, x2, f(x2)))
if f(x0) * f(x2) < 0:
x1 = x2
else:
x0 = x2
step = step + 1
condition = abs(f(x2)) > e
print('\nRequired Root is : %0.8f' % x2)
# Input Section
x0 = input('First Guess: ')
x1 = input('Second Guess: ')
e = input('Tolerable Error: ')
# Converting input to float
x0 = float(x0)
x1 = float(x1)
e = float(e)
#Note: You can combine above two section like this
# x0 = float(input('First Guess: '))
# x1 = float(input('Second Guess: '))
# e = float(input('Tolerable Error: '))
# Checking Correctness of initial guess values and bisecting
if f(x0) * f(x1) > 0.0:
print('Given guess values do not bracket the root.')
print('Try Again with different guess values.')
else:
bisection(x0,x1,e)
Additionally codesansar.com/numerical-methods/ has large collection of algorithms, pseudocodes, and programs using different programming languages for Numerical Analysis.
Scrubatpython
Updated on July 23, 2022Comments
-
Scrubatpython almost 2 years
I want to make a Python program that will run a bisection method to determine the root of:
f(x) = -26 + 85x - 91x2 +44x3 -8x4 + x5
The Bisection method is a numerical method for estimating the roots of a polynomial f(x).
Are there any available pseudocode, algorithms or libraries I could use to tell me the answer?
-
ultimatetechie about 10 yearsHow would I add a tolerance, instead of iterating the loop n times?