Exercises on the Bisection Method

1. 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 performs a fixed number of iterations, iterations.

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

The definition of this Python function will be of the form

def bisection1(f, a, b, iterations):
    . . .
    return root

and the usage will be something like

root = bisection1(f, a, b, iterations)
print(f'The approximate root is {root}')

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)

The bisection method algorithm in “pseudocode”#

Here is a description of the improved version 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 this more refined algorithm, solving to a specified maximum allowable absolute error, and this time also giving a bound on the error in the computed result, so with usage

(root, errorBound) = bisection2(f, a, b, errorTolerance)

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 output the the final error bound as well as the approximate 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!

Contents