Solving Equations by the Bisection Method

We wish to calculate the root of a given function located between two given points by the known bisection method which does that by repeatedly approaching the two points around the root until they are close enough. Specificly, given the function \(f\) and the points \(x_1, x_2\) such that there is a point \(x_0\) such that \(f(x_0) = 0\), the method repeatedly calculates the middle point \((x_1+x_2) / 2.0\) (let’s call it m), calculates its image f(m), and compares the sign (positive or negative) of f(m) and the signs of f(x_1) and f(x_2). The point whose image has the same sign of f(m) is moved to m. This is illustrated by the following figure:

../../../_images/bisection.png

For example, for the second iteration it is necessary to move the point \(x_2\) to the midpoint \(m\) and the point \(x_1\) remains the same.

This iterative process continues until the distance between \(x_1\) and \(x_2`is less than :math:`epsilon\) and the root is calculated as the average of \(x_1\) and \(x_2\).

The bisection method is garanteed to converge towards a root as long as the function \(f(x)\) is continuous between \(x_1\) and \(x_2\), and that the initial values \(f(x_1)\) and \(f(x_2)\) have opposite signs (this ensures the existence of a root between \(x_1\) and \(x_2\)).

Please implement the following Python function in the bisection module (bisection.py file) to compute a root of the specific function \(f(x) = x^3-3\,sin(x)+1\):

bisection.bisection_solve(x1, x2, eps)

given

  • x1, x2, float such that x2 >= x1 (they determine the search interval) and f(x1)*f(x2) < 0.0

  • eps, float with the tolerance

returns a float x0 obtained by applying the bisection method described above such that \(f(x0) == 0.0\) with tolerance eps.

For example:


>>> z = bisection_solve(1, 2, 1e-2)
>>> round(z, 4)
1.2227

>>> z = bisection_solve(0.5, 1.5, 1e-6)
>>> round(z, 4)
1.2204

>>> z = bisection_solve(0.0, 0.5, 1e-6)
>>> round(z, 4)
0.3558

>>> z = bisection_solve(0.0, 0.0, 1e-6)
>>> round(z, 4)
0.0

Doctests are available at the bisection.test file.