# Interpolation

Given a set of points, we want to model the general trend of the points by finding a smooth curve that fits the dataset. This is actually what we do in machine learning.

Problem Formulation

Given $p(x_{1})=y_{1},p(x_{2})=y_{2},β¦,p(x_{n})=y_{n}$. estimate $y=p(x)$ for any point $x$ such that $x_{1}β€xβ€x_{n}$.

### CS370

2 ways to go about interpolation:

When there are very few points (<6), we do Polynomial Interpolation

- Vandermonde Matrix (monomial basis)
- Lagrange Form (Interpolation) (lagrange basis)

However, then, when there are lots of points, your 1 function might be of degree too high and it wonβt be as smooth anymore. Therefore, a better strategy is to use Piecewise Interpolation

- Piecewise linear
- Cubic Spline

There also is another category of interpolation called Hermite Interpolation, where we want to set the derivatives at control points.

### Polynomial Interpolation

If we have 5 points, we can find a polynomial of degree 4 passing through these points.

We use the equation below: $y=y_{0}+xΞy_{0}+x(xβ1)2!Ξ_{2}y_{0}β+x(xβ1)(xβ2)3!Ξ_{3}y_{0}β+β―$ $+x(xβ1)(xβ2)β―(xβn+1)n!Ξ_{n}y_{0}β$

Now, it looks very complicated at first, but we can calculate the finite differences very easily. Use the triangular table:

### Interpolation in Python

Thereβs logic for interpolating racing lines.

I need to reference both the TUFTM, and some implementation that the guys at F1TENTH did.

But thereβs this Scipy function for interpolation: