# Simple Interpolation

1 Jul 2013

As of March 2020, School of Haskell has been switched to read-only mode.

# A simpler problem.

Given a list of points, we want to find a polynomial function `f` such that:

For every point `(x_i,y_i)` in your list, then `f x_i == y_i` is always true.

Just for fun, let us write the exact same problem using Haskell:

``````-- show This is given to you
listOfPoints = [(x_1,y_1), .. (x_N,y_N)]
-- /show

-- show The following property must be satisfied
map snd listOfPoints == map (f . fst) listOfPoints
-- /show
``````

## An example for a set of three points.

Here is a solution to the previous problem in the special case where the input list contains 3 points.

``````-- show The input
listOfPoints = [(x1,y1),(x2,y2),(x3,y3)]
-- /show

-- show The solution
f x = y1 * (x - x2) * (x - x3) / ((x1 - x2) * (x1 - x3)) +
y2 * (x - x1) * (x - x3) / ((x2 - x1) * (x2 - x3)) +
y3 * (x - x1) * (x - x2) / ((x3 - x1) * (x3 - x2))
-- /show``````

### Exercise

1. Evaluate `f x1`, and show that indeed `f x1 = y1`.
2. Either figure out why this shows `f x2 = y2`, or do it all over again.
3. Same thing for `f x3`.
4. Bonus: Write down a similar function for the case of 4 points.

## The solution for any number of points.

Now, we do the general thing.

By looking at the specific example (3 points), and any other specific examples you might have worked out (4 points), we will try to build a general solution. If you just want the solution, see the hidden content below:

### Generalizing a specific solution

Let us rewrite the solution:

``````
-- show The solution
f x = y1 * (x - x2) * (x - x3) / ((x1 - x2) * (x1 - x3)) +
y2 * (x - x1) * (x - x3) / ((x2 - x1) * (x2 - x3)) +
y3 * (x - x1) * (x - x2) / ((x3 - x1) * (x3 - x2))
-- /show
``````

We see that it is a sum of various terms. Let us rewrite it as such.

``````
-- show The solution
f x = sum \$ [y1 * (x - x2) * (x - x3) / ((x1 - x2) * (x1 - x3))
, y2 * (x - x1) * (x - x3) / ((x2 - x1) * (x2 - x3))
, y3 * (x - x1) * (x - x2) / ((x3 - x1) * (x3 - x2))]
-- /show
``````

Each term is the product of `y_i` with the rest.

``````-- show Inputs:
ys
x1, x2, x3
-- /show

-- show The solution
f x = sum \$ zipWith (*) ys [(x - x2) * (x - x3) / ((x1 - x2) * (x1 - x3))
, (x - x1) * (x - x3) / ((x2 - x1) * (x2 - x3))
, (x - x1) * (x - x2) / ((x3 - x1) * (x3 - x2))]
-- /show
``````

We can rewrite again:

``````-- show Inputs:
ys
x1, x2, x3
-- /show

-- show The solution
f x = sum \$ zipWith (*) ys [product [(x - x2) / (x1 - x2), (x - x3) / (x1 - x3)]
, product [(x - x1) / (x2 - x1), (x - x3) / (x2 - x3)]
, product [(x - x1) / (x3 - x1), (x - x2) / (x3 - x2)]]
-- /show
``````

Finally, we get the final form:

``````-- show Inputs:
xs
ys
-- /show

-- show The solution
f x = let
lamb xi  = product \$ map (\xj -> (x-xj)/(xi-xj)) (delete xi xs)
in sum \$ zipWith (*) ys (map lamb xs)
-- /show  ``````

This is called the Lagrange method.

# Better than Interpolation?

So far, we have discussed a global (the whole input contributes to the same function) polynomial interpolation.

Later, we will talk about local interpolation, and even better interpolation.

However, you should realize that interpolation is rather bad if it comes to real data with built-in error. To tackle real data, we need Data Fitting techniques, and even later, we will talk about machine learning.