Tutorial 3: Recursion and Problem Solving

4 Tutorial 3: Recursion and Problem Solving

In this section we will continue the study of the two functions $f\left(x\right)$ and $g\left(x\right)$ from the previous tutorial.

Reading: Simon Thompson, Chapter 4 and 10.2

4.1 Worked Example: Optimisation

A minimisation problem has the form

for some function $f\left(x\right)$. The problem is to find the smallest possible value for $f\left(x\right)$. Often, we also want to find the corresponding value of $x$.

One simple minimisation algorithm is obtained by imagining a ball rolling on the curve. It will always run down-hill, and eventually it will stop in a local minimum. We will implement this algorithm to find the $x$ value minimising the function $f\left(x\right)$ from the previous tutorial.

1.

Open the module from the previous tutorial, with the definition of the f function.

2.

We need to decide how far the ball should roll per iteration. For the time being we make it a constant, so add the following line to you module delta = 0.01

3.

Then we decide on the bounds for the search. We search for a minimum in the interval $\left(-20,20\right)$, and add the following lines to the module. low = −20 
high = 20

4.

We shall implement the function fmin which takes a starting point $x_0$ as input, and returns a (local) minimum. First we add the type declaration to our module, with one input and one output: fmin :: Double −> Double

5.

Now we can start adding definitions for fmin. Using guards, we can define one case at the time. First of all, if the ball has reached the lower or upper bound, this bound value is returned: fmin x0 | x0 − delta < low       = low 
        | x0 + delta > high      = high This constitues a base case for recursion.

6.

If we find smaller function value to the left of x0, i.e. at x0-delta, we move left and call the function recursively with the new starting point. Similarly, we move right if this gives a smaller function value. fmin x0 | f (x0 − delta) < f x0  = fmin (x0 − delta) 
        | f (x0 + delta) < f x0  = fmin (x0 + delta)

7.

If neither moving left nor right reduces the function value, we must be in a local minimum which is then returned: fmin x0 | otherwise              = x0

8.

Save your module, start GHCi, and load (or reload) the module.

9.

Test the fmin function, as follows fmin 0

10.

Discuss: does it matter what value you give as starting point?

4.2 Practice Problem: Bisection Method

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

Note that the right hand side is the function $g\left(x\right)$, so we can write $0=g\left(x\right)$ instead. Let’s not discuss whether a solution can be found analytically. We want to find some solution numerically.

A couple of observations are easy to make.

1.

$g\left(-10\right)<0$

2.

$g\left(10\right)>0$

3.

$g\left(x\right)$ is continuous

It follows from these three observations that $g\left(x\right)$ has at least one root in the interval $-10<x<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 $g\left(x\right)$ be a continuous function and $\left(l,u\right)$ an interval so that $g\left(l\right)$ and $g\left(u\right)$ have different sign; then $g\left(x\right)$ has a zero in the interval $\left(l,u\right)$. The Bisection Method finds the midpoint $m$ in the interval $\left(l,u\right)$. If $g\left(l\right)$ and $g\left(m\right)$ have different sign, then there must be a zero in the interval $\left(l,m\right)$ and we use bisection recursively on this interval. Otherwise, we call it recursively on the interval $\left(m,u\right)$.

4.2.1 Tasks

1.

Open your editor and create a new Haskell module for this problem. Choose an appropriate name for the module.

2.

Implement the function $g\left(x\right)$ described above in Haskell. The type description should be f :: Double −> Double

3.

We are going to implement a 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.

• Write the type signature of bisect into your module file.

4.

The 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).

Base case

If the difference 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 l u | u−l < eps = ...

choose an appropriate value for eps and add a defintion after the equal sign.

Recursive case

If the search interval is larger, we split it in two, and find which half must contain a root. Then we recursively continue the search in the relevant half. The recursive call, with two different cases using guards, can look something like this. bisect l u | fl*fm < 0 = bisect l m 
           | otherwise = bisect m u 
                     where ...

You need to complete the where clause to define the midpoint m and the function values fm ($g\left(m\right)$) and fl ($g\left(l\right)$).

5.

Start ghci and load the module that you have written.

6.

Test your bisection function by finding the root of $g\left(x\right)$ in the interval $\left(-10,10\right)$. I.e. evaluate the following bisect (−10) 10 Does the answer look reasonable when you compare to the plot of $g\left(x\right)$ in the previous tutorial?