Functional Programming and Intelligent Algorithms

Overview

• Reading: Simon Thompson, Chapter 4 and 10.2

Problem 1: 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

$0=x^5+x^4·2+x^2·4+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·2+x^2·4+x-\mathrm{10}$

A couple of observations are easy to make.

1. $\mathrm{f(-10)}<0$
2. $\mathrm{f(10)}>0$
3. $\mathrm{f(x)}$ is continuous

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)}$.

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 $\mathrm{f(x)}$ 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 bisectfunction 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 u l | 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 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)}$).

5. Start ghci and load the module that you have written.
6. Test your bisection function by finding the root of $\mathrm{f(x)}$ in the interval $\mathrm{(-10,10)}$. I.e. evaluate the following bisect (-10) 10
7. It will be useful to check that the result is reasonable. You probably have some software (spreadsheet, MatLab, python, gnuplot) where you can plot $\mathrm{f(x)}$ on the interval $\mathrm{(-10,10)}$ and check that the zero you find is (approximately) correct. Or you could evaluate the function on the x-point returned by bisect and check if you get approximately zero.

Refinement with higher-order functions

We are going to implement a bisect function, so that it can be used to find zeros of arbitrary continuous functions.

1. 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.

   1. What is a higher-order function?
   2. Change the type signature of bisect into your module file.

2. Update the implementation of bisect to become a higher-order function.

   1. Add the function argument 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.

3. Test the revised bisection function by finding the root of $\mathrm{f(x)}$ in the interval $\mathrm{(-10,10)}$. I.e. evaluate the following bisect f (-10) 10

Problem 2: More Pictures

Do Exercises 4.25-4.30 in Simon Thompson's book.