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?
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.
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
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
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
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With