# Liner Interpolation

In mathematics, linear interpolation is understood as a method of curve fitting using linear polynomials. A polynomial is just an expression that consists of variables along with their co-efficients. An example of a polynomial would be:

```
1x+2y²
```

In the above equation, the variable x has 1 as its coefficient, the variable y has 2 as its coefficient. Let us assume that we have a set of linear data points pointing to the x and y-axis:

```
1x = {2,5,7,10,11,15,17,19,21,25}
2y = {3,6,8,10,14,16,19,21,23,26}
```

Given a value x, we can find the value y. For example., for x = 2, the corresponding y is 3, for x = 11, the corresponding y is 14. Now we are interested in finding the value of x and y within our set of data points.

What is the value of y for x = 13 or what is the value of x for y = 13. Since the data points for both the x and y co-ordinates are linear, we can use the linear interpolation technique to find out the values for the desired data points. Geometrically, the linear interpolant is just a straight line between two known data points. Let us assume that our two data points are represented as (x0,y0) and (x1,y1). We are interested in finding the values of x and y that lies between these data points. Since we are in the linear boundary, geometrically speaking the ratio of the difference between x and y co-ordinates between two data points are equal.

Let us try to ascertain this with some numbers. Let our data points (x0,y0) be (2,3) and (x1,y1) be (5,6). The ratio y1/x1 should be equal to the ration y0/x0 and in our case, 6/5 == 3/2. Extending this idea, we can now say that the ratio of the difference between two data points should be geometrically equal between the two co-ordinates. If we are interested in a data point (x,y) which lies in-between (x0,y0) and (x1,y1), our formula now becomes:

```
1y - y0 / x - x0 = y1 - y0 / x1 - x0 which when solving for y, we get the following equation:
2y = y0 + (y1 - y0) * (x - x0) / (x1 - x0)
```

We now have the formula for linear interpolation, let's now implement that in Scala. Let us represent our data points as a Scala List:

```
1 val x = List(2,5,7,10,11,15,17,19,21,25)
2 val y = List(3,6,8,10,14,16,19,21,23,26)
3 val zippedDataPoints = x zip y
```

We define a function that takes these two zipped List of data points and an additional parameter for x. The function uses the formula to find the value of y for a given x. Here is the function:

```
1def interpolate(givenX: Int, dataPoints: List[(Int, Int)]) = {
2 // edge cases
3 val (headX, headY) = dataPoints.head
4 val (lastX, lastY) = dataPoints.last
5 givenX match {
6 case a if givenX >= lastX => lastY
7 case b if givenX <= headX => headY
8 case c => {
9 val (lower,upper) = dataPoints.span { case (x,y) => x < givenX }
10 val (x0,y0) = lower.last
11 val (x1,y1) = upper.head
12 // finally our formula!
13 y0 + (y1 - y0) * (givenX - x0) / (x1 - x0)
14 }
15 }
16}
```

Let's now write some tests to test our interpolation (using ScalaTest):

```
1 interpolate(2, zippedDataPoints) == 3
2 interpolate(4, zippedDataPoints) == 5
3 interpolate(27, zippedDataPoints) == 26
```

So there it is! we have our linear interpolation implemented using Scala!