Exercises on the Bisection Method

A test case

As a first test case, we will solve \(x - \cos(x) = 0\), which can be shown to have a unique root that lies in the interval \([0, 1]\).

Then other equations can be tried.

Exercise 1

Create a Python function implementing the first, simplest algorithm from the section on Root finding by interval halving, which perfomrs a fixed number of iterations, max_iterations. (This was called “N” there, but in code I encourage using more descriptive names for variables.)

This be used as: root = bisection1(f, a, b, max_iterations)

Test it with the above example, and then try solving at least one other equation.

The main task is to create a Python function whose input specifies a function f, the interval end-points a and b, and an upper limit tol on the allowable absolute error in the result; and whose output is both an approximate root c and a bound errorBound on its absolute error.

That is, we require that there is an exact root \(r\) near \(c\), in that

\[|r - c| \leq \text{errorBound} \leq \text{TOL}.\]

The definition of this Python function will be of the form

def bisection(f, a, b, TOL):
    . . .
    return c, errorBound

and the usage will be something like

(root,  errorBound) = bisection(f, a, b, TOL)
print(f'The approximate root is {root} with absolute error at most {errorBound}')

I give a definition for the test function \(f\). Note that I get the cosine function from the module numpy rather than the standard Python module math, because numpy will be far more useful for us, and so I encourage you to avoid module math as much as possible!

from numpy import cos
def f(x):
    return x - cos(x)

This helps with the readability of large collections of code, avoiding the need to look further up the file to see where an object like cos comes from. (It is also essential if you happen to use two functions of the same name from different modules, though in the current example, one is unlikely to want both math.cos and numpy.cos.)

The bisection method algorithm in “pseudocode”

Here is a description of the bisection method algorithm in pseudocode, as used in our text book and these notes: a mix of notations from mathematics and computer code, whatever makes the ideas clearest.

Input:
\(\quad\) f (a continuous function from and to the real numbers),
\(\quad\) a and b (real numbers, \(a < b\) with \(f(a)\) and \(f(b)\) of opposite sign)
\(\quad\) errorTolerance (the maximum allowable absolute error)

Output will be:
\(\quad\) r (an approximation of a solution of \(f(r) = 0\))
\(\quad\) errorBound (an upper limit on the absolute error in that approximation).

\(\displaystyle c = \frac{a + b}{2}\)
errorBound = c - a
while errorBound > errorTolerance:
\(\quad\) if f(a) f(c) > 0:
\(\quad\)\(\quad\) \(a \leftarrow c\)
\(\quad\) else:
\(\quad\)\(\quad\) \(b \leftarrow c\)
\(\quad\) end if
\(\quad\) \(\displaystyle c = \frac{a + b}{2}\)
\(\quad\) errorBound = c - a
end while
r = c

Output: r, errorBound

Exercise 2

Create Python/Numpy code for the more refined algorthn mabvm, wolving to a specified maximum allownble absolte error, so with usage (root,  errorBound) = bisection(f, a, b, TOL)

Again test by solving \(x - \cos x = 0\), using the fact that there is a solution in the interval \((-1, 1)\), but this time solve accurate to within \(10^{-4}\), and otu the the final error bound as well as the apprxomate root.

Exercise 3

Consider the equation \(x^5 = x^2 + 10\).

a) Find an interval \([a,b]\) of length one in which there is guaranteed to be a root.

b) Compute the next two improved approximations given by the bisection method.

c) Determine how many iterations of the bisection method would then be needed to approximate the root with an absolute error of at most \(10^{-10}\).
Do this without actually computing those extra iterations or computing the root!

---

This work is licensed under Creative Commons Attribution-ShareAlike 4.0 International