bisection Algorithm
The bisection algorithm, also known as binary search or interval halving method, is a root-finding approach that narrows down the search interval by repeatedly dividing it in half. This algorithm is based on the intermediate value theorem and works on the premise that if a continuous function has values of opposite signs at two points within an interval, then it must have a root within that interval. The bisection method is especially effective for solving nonlinear equations with a single variable and is guaranteed to converge to a root if the function is continuous and the initial interval contains a root.
To implement the bisection algorithm, start by defining an initial interval [a, b] such that the function f(a) and f(b) have different signs. Then, compute the midpoint c = (a + b) / 2 and evaluate the function f(c). If f(c) is sufficiently close to zero or the specified tolerance, c is considered as the root. Otherwise, the algorithm checks the sign of f(c) and updates the interval [a, b] accordingly: if f(a) and f(c) have opposite signs, the new interval becomes [a, c], and if f(b) and f(c) have opposite signs, the interval becomes [c, b]. Repeat this process iteratively until the desired root is found or a maximum number of iterations is reached. The bisection algorithm is not the fastest root-finding method, but it is simple to implement and provides a robust and reliable means to find a root within a given interval.
import math
def bisection(
function, a, b
): # finds where the function becomes 0 in [a,b] using bolzano
start = a
end = b
if function(a) == 0: # one of the a or b is a root for the function
return a
elif function(b) == 0:
return b
elif (
function(a) * function(b) > 0
): # if none of these are root and they are both positive or negative,
# then his algorithm can't find the root
print("couldn't find root in [a,b]")
return
else:
mid = start + (end - start) / 2.0
while abs(start - mid) > 10 ** -7: # until we achieve precise equals to 10^-7
if function(mid) == 0:
return mid
elif function(mid) * function(start) < 0:
end = mid
else:
start = mid
mid = start + (end - start) / 2.0
return mid
def f(x):
return math.pow(x, 3) - 2 * x - 5
if __name__ == "__main__":
print(bisection(f, 1, 1000))
