MATH 375 Assignment 1¶
By Brenton LeMesurier
Due Friday January 22
This assignment is partly for review and orientation to the main software tools that we will be using: Python, Numpy, and Jupyter notebooks, for which the online tool Colab and the software Anaconda are two means of access. (Anaconda also provides access to the the Integrated Development Environment Spyder, the package Matplotlib for graphics and package SciPy that provides additional computational tools; we will use these later.)
For convenience, assignment sections like this will repeat some material from the notes, such as exercises. Also any section can be donwloaded as a Jupyter notebook, whc could be used as a template for workign on an assignment. To do that, use the download button near the top-right, and select the option “.ipynb”.
We will work on these exercises in class, but I encourage you to work on them at home too.
Objectives¶
The goal is to create Python functions for solving equations using the bisection method, and then to present the work in a Jupyter notebook.
The main mathematical objective is to solve an equation \(f(x) = 0\) where the function \(f:\mathbb{R} \to \mathbb{R}\) is continuous on an interval \([a,b]\) and changes sign between its endpoints, so that a solution within that interval is guaranteed by the Intermediate Value Theorem.
Implementing the Improved Bisection Algorithm¶
The main programming 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
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}')
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 \([-1, 1]\).
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)
Exercises¶
Exercise 1¶
(a) Explain carefully why there is guaranteed to be a root of function \(f\) in the interval \((a, b)\) if \(f\) is continuous on this interval and \(f(a) f(b) < 0\).
(b) Give an example of a function \(g\) that illustrates why continuity is essential for the above result. (This function will be used below.)
Preferably, write this up in the Jupyter notebook for this assignment. However, if you are not yet comfortable presenting mathematical work in a notebook’s Markdown cells, you may do it in another format such as PDF from LaTeX or even a PDF scan of hand-written work.
Exercise 2¶
(a) Create a Python function which implements the first algorithm for bisection from the section
Root Finding by Interval Halving
which performs a fixed number \(N\) of iterations;
the usage should be:
root = bisection1(f, a, b, N)
(b) Test it with the above example solving \(x = \cos x\) by using the function \(f(x) = x - \cos x\), \([a, b] = [-1, 1]\).
(This involves defining another function f.)
(c) Then experiment with what happens when use your non-continuous function \(g\) frm Exercise 1.
Note: Part (c) is an example of what I call destructive testing: seeking hard cases that either reveal the weakness or limitations of an algorithm, or illustrate its robustness and reliability.
Present this in a Jupyter notebook.
You may develop and submit this entirely in such a notebook;
however, if you wish to explore the Spyder IDE, or prefer to develop code with such software and then copy into a notebook, you may do so.
In that case, do this in a Python file named bisection1.py,
and also submit that file.
Exercise 3¶
Create Python/Numpy code for the above improved algorithm with a function bisection2,
and to test it by solving
\(x - \cos x = 0\) again, this time accurate to within \(10^{-4}\).
Use the fact that there is a solution in the interval \((-1, 1)\).
Submitting your work¶
Once all the above code is working, including running the test cases and dispaying output, put it all together into a single Jupyter notebook. (Plus any PDF files for Exercise 1, if you did not do that part in the notebook.)
Feel free to copy stuff from the current notebook (or any other parts of the book for this course), such as describing the algorithm in pseudocode.
Then submit your files to Canvas.
This work is licensed under Creative Commons Attribution-ShareAlike 4.0 International