Interpolation

In this topic, we will talk about quite an important use of polynomials – interpolation. This operation is commonly used in computational mathematics, and it is almost the main one. We will discuss what it is and what kinds of interpolation there are, and will examine one of the more popular ones in detail. This is where we will need the knowledge of polynomials.

What is interpolation?

Assume that we have a finite set of dots on the plane $\{(x_i,y_i)\}$, where none of $x_i$ repeat. We want to find such a function $f(x)$, that will contain all the dots. Since the function will be defined everywhere, then with its help we could find values of the dots that were not initially given, like the intermediate ones.
For example, let's say we have certain days of the month when we know the temperature, and we want to assume it for other days. This is where interpolation would come in handy.
Currently, there are many ways to perform interpolation. The choice of the algorithm depends on many factors: how accurate the chosen method is, what the cost of using it is, how smooth the interpolating function is, how much data it requires etc. But we will start with the simplest one: the linear interpolation.

Linear interpolation

Let's say we have two dots: $(1, 5)$ and $(4, 10)$. We would like to know what the value for $x=2$ could be. To find it, we will make a line from the first point to the second. And after that all we need is to find $y$ for said point, which will be our assumption, and the resulting line will be the interpolating function for our dots. Time to examine and find out what the value we've been looking is for $x=2$.

Let's write the linear equation for two dots and substitute $2$ into it.

$(5-10)x+(4-1)y+(1\cdot10-4\cdot5)=0$

$5x-3y+10=0$

$y=\frac{5x+10}{3}$

After substituting $2$ we get $\frac{5\cdot2+10}{3}=\frac{20}{3}=6 \frac{2}{3}$. We found that for $x=2$ $y$ will be $6 \frac{2}{3}$. And the interpolating function is $\frac{5x+10}{3}$.

Now imagine that we have not just two dots, but many of them, what are we going to do then? That's right, we will keep connecting two nearby dots with lines and will get a polyline, which to some degree approximates the function. Take a look at the image below to get an idea of what we are talking about.

Lagrange interpolating polynomial

Say, we have a set of $(n+1)$ dots on the plane, $x$ coordinates of which don't repeat. We would like to find a polynomial that would go through all of them and would have a degree of $n$. Such a polynomial is called the Lagrange polynomial and is noted $L(x)$. Such a polynomial, that by the way has no more than $n$ roots, is also the only one, but we won't give the proof here.

Let's try to understand how to make it. The formula for it has the following form: $L(x)=\sum_{i=0}^{n}y_il_i(x)$, where:

$l_i(x)=\prod_{j=0,j \neq i}^{n} \frac{x-x_j}{x_i-x_j}=\frac{x-x_0}{x_i-x_0} \dots \frac{x-x_{i-1}}{x_i-x_{i-1}} \cdot \frac{x-x_{i+1}}{x_i-x_{i+1}} \dots \frac{x-x_n}{x_i-x_n}$

Note, that $l_i(x)$ have certain properties:

• are polynomials of degree $n$

• $l_i(x_i) = 1$

• $l_i(x_j) = 0$ when $j ≠ i$

Indeed, $l_i(x)$ is such a multiplication that is missing one factor. If we substitute $x_i$ instead of $x$, then all factors will be $1$, therefore their product will also be $1$. Now if we substitute $x_j$, where $j ≠ i$, then there will be a factor equal to zero, and as a result, the product will also be zero.

Let's take a look at an example.
Say, we have $4$ dots: $\{(0,2), (2,0), (4,6), (-1,-9)\}$. It means that we can find a polynomial of degree $3$ that will interpolate all these dots.

First, find all $l_i(x)$ by using the formula:
$l_0(x)=\frac{x-2}{0-2} \cdot \frac{x-4}{0-4} \cdot \frac{x+1}{0+1} =\frac{1}{8}(x-2)(x-4)(x+1)$$l_1(x)=\frac{x-0}{2-0} \cdot \frac{x-4}{2-4} \cdot \frac{x+1}{2+1} =-\frac{1}{12}x(x-4)(x+1)$$l_2(x)=\frac{x-0}{4-0} \cdot \frac{x-2}{4-2} \cdot \frac{x+1}{4+1} =\frac{1}{40}x(x-2)(x+1)$$l_3(x)=\frac{x-0}{-1-0} \cdot \frac{x-2}{-1-2} \cdot \frac{x-4}{-1-4} =-\frac{1}{15}x(x-2)(x-4)$

After that, calculate $L(x)$ also with the formula: $L(x)=\frac{2}{8}(x-2)(x-4)(x+1)-\frac{0}{12}x(x-4)(x+1)+\frac{6}{40}x(x-2)(x+1)-\frac{-9}{15}x(x-2)(x-4)=x^3-5x^2+5x+2$
We got the polynomial of degree $3$: $L(x)=x^3-5x^2+5x+2$.

You can see the polynomial and the given dots on the graph, everything fits!

Other kinds of interpolation

We have taken a look at two types of interpolation: the linear interpolation and the interpolation with Lagrange polynomial. But there are also approaches. One of the popular ones is using the Newton's interpolating formula. It is very convenient to use when the $x$ coordinates of the dots are equally spaced.

Conclusion

In this chapter we have discussed interpolation, what types of interpolation exist. Furthermore, we have examined one of the common interpolation methods: using the Lagrange interpolating polynomial.