In this tutorial we shall implement the Bisection Algorithm which is a simple numerical approach to equation solving. Consider the following equation as an example
$0={x}^{5}+{x}^{4}\xb72+{x}^{2}\xb74+x-\mathrm{10}$
Let's not discuss whether a solution can be found analytically. We want to find some solution numerically. To facilitate discussion, we define a symbol $\mathrm{f(x)}$ for the right hand side, i.e.
$\mathrm{f(x)}={x}^{5}+{x}^{4}\xb72+{x}^{2}\xb74+x-\mathrm{10}$
A couple of observations are easy to make.
It follows from these three observations that $\mathrm{f(x)}$ has at least one root in the interval $\mathrm{-10}<x<\mathrm{10}$. Without considering the possibility of multiple roots, we want to find one such root.
You can look up the Bisection Method in most undergraduate introductions to calculus. Let $\mathrm{f(x)}$ be a continuous function and $\mathrm{(l,u)}$ an interval so that $\mathrm{f(l)}$ and $\mathrm{f(u)}$ have different sign; then $\mathrm{f(x)}$ has a zero in the interval $\mathrm{f(x)}$. The Bisection Method finds the midpoint $m$ in the interval $\mathrm{(l,u)}$. If $\mathrm{f(l)}$ and $\mathrm{f(m)}$ have different sign, then there must be a zero in the interval $\mathrm{(l,m)}$, and we use bisection recursively on this interval. Otherwise, we call it recursively on the interval $\mathrm{(m,u)}$.
f :: Double -> Double
bisect
function,
which can be used to find a zero of f
with a call like
this:
bisect (-10) 10
The arguments are resp. the lower and upper bound of
the search interval and have type Double.
bisect
into your
module file. bisect
function has to be a recursive function,
so we need two cases.
Use l
and u
to denote the bound of the
search interval (l,u)
.
l-u
is very small,
we can just take the average of l
and u
as the approximate solution. Write a guarded expression
for the base case, e.g.
bisect u l | u-l < eps = ...
choose an appropriate value for eps
and add a defintion
after the equal sign.
bisect u l | fl*fm < 0 = bisect f l m
| otherwise = bisect f m u
where ...
You need to complete the where
clause to define
the midpoint m
and the function values
fm
($\mathrm{f(m)}$)
and fl
($\mathrm{f(l)}$).
bisect (-10) 10
bisect
and check if you get approximately
zero.
We are going to implement a bisect
function,
so that it can be used to find zeros of arbitrary continuous functions.
We want to change the bisect
function so that it can be
used like this
bisect f (-10) 10
The first argument is the function for which we want to find a zero,
with type Double -> Double
, making
bisect
a higher-order function.
The other two arguments are as before.
bisect
into your
module file.
Update the implementation of bisect
to become a higher-order
function.
f
as the first argument on
the right hand side of the definition? When the symbol f
is used as an argument, f
on the right hand side will refer to the argument and not to the
global definition. Thus no changes are required on the right hand
side.
bisect f (-10) 10
Do Exercises 4.25-4.30 in Simon Thompson's book.