Assignment: Bisection MethodΒΆ

Your task is to implement the bisection method for finding a solution $x$ of the equation $$ f(x)=0. $$ Here $f$ is a real-valued function of a single real variable $x$ and the solution of the above equation is called a root of $f$.

Many nonlinear algebraic equations, such as $x = 1 + \cos x$ do not admit a closed form solution. But a numerical method can find an approximate solution by finding the root of $f(x) = x - 1 - \cos x.$

Bisection is a numerical method to solve for a root of a function $f(x)$ of a single real variable $x$. Here is its description:

The Bisection method

  1. Start with an interval $[a,b]$ in which $f(x)$ changes sign.
  2. Then there must be (at least) one root in $[a,b]$.
  3. Halve the interval and set the midpoint $m = (a+b)/2$.

    • Does $f$ change sign in left half $[a,m]$?
    • If Yes: Repeat with the left interval $[a,m]$ (set $b=m$)
    • If No: Repeat with the right interval $[m,b]$ (set $a=m$)
  1. At the $n$th step, the initial interval $[a,b]$ has been halved $n$ times and we know that $f(x)$ must have a root inside a small subinterval of length $2^{-n}(b-a)$. Since the root is contained in this subinterval, $\text{error}\le 2^{-n}(b-a).$

  2. Hence we may stop the subdivisions when $n$ is such that $$ 2^{-n}(b-a) \le \epsilon. $$ for some user specified error tolerance $\epsilon$, and take the midpoint $m$ as the root.

Hints and suggestions

  1. Write down your steps as a precise algorithm (before you code) in terms of for/while, if, else, etc. Use this to map out how you will write your code.

  2. Write a first version of the code and make sure it is working on a test problem. Your code should be in the form of a function

    def bisection(f, a, b, eps, niters):
         # Code goes here.

    where f, a, b, and eps represent $f$, $a$, $b$ and $\epsilon$ in the above description, and niters is the maximal number of iterations, which in this case is the maximal number of subdivisions of the initial interval you will make (whether or not the eps tolerance is met).

  3. Test your bisection code on the function $f(x)$ whose roots you know, say $f(x) = \cos(x)$. Once you know your current code is working correctly, proceed to the next step. If you jump this step, beware that "premature optimization is the root of all evil," according to Donald Knuth.

  1. Refactor/improve/optimize: When halving the interval, can you reuse a previously used value of $f$ to make the code more efficient? (This would be important when the evaluation of $f$ is expensive.) Also have you made sure you have included comments? Does you function have a docstring?