Interpolation

Interpolation is estimating unknown values between known values.
Generally, given data points, interpolation finds a smooth function that passes through all the data points.

Example: For the points (1,3) and (2,7), we can fit the function $y=4x-1$.
Now, we can provide values for x= 1.5, x = 1.32, x = 1.999 etc.

Practical Uses

• We can go from a low-res photo to a high-res photo by interpolating; we are estimating the colour values of the newly generated pixels!

Types of Interpolation

• Linear Interpolation (lerp) - connects two points with a straight line
• Polynomial Interpolation - a single polynomial connects all points
  • Includes Lagrange, Newton interpolation techniques
• Spline Interpolation - piecewise polynomials (avoids oscillations)

Naive Polynomial Interpolation

For $n$ data points, we can generate a polynomial of degree $n-1$. This is an upper-bound for the degree that a polynomial must be to go through all the data points!

Example: Given data points (1,2), (3, 4), and (5,8). Give a polynomial interpolation

$y=a_0{x}^2+a_1{x}^1+a_2$.

Subbing in the points:
$g$

Vandermonde Matrix

Generalised Theorem

Theorem: Given $n+1$ data points $(x_0,y_0),(x_1,y_1),\dots ,(x_{n+1},y_{n+1})$

Horner Scheme

$a_0+a_{1}x+a_2{x}^2+\cdots +a_n{x}^n=a_0+x(a_1+x(a_2+\dots ))$

Derived from just factoring out the $x$ each time

Limitations of Naive Polynomial Interpolation

1. Finding the inverse of the Vandermonde matrix is expensive
2. No support for incremental update; have to recalculate the polynomial from scratch
3. Must find the whole function first (determine coefficients) before finding estimates for intermediate points

Lagrange Interpolation solves problems 1 and 3.
Newton Interpolation solves problems 2 and 3.

Lagrange Polynomial

Divided Difference

1st order divided difference is the gradient/rate-of-change of the line between the two parts.
2nd order divided difference is the rate of change of the 1st order divided differences.

$[y_0,y_1,\dots ,y_{n-1},y_n]=\frac{}{}$

Example: Evaluate $[y_0,y_1,y_2]$ for $(x_0,y_0),(x_1,y_1),(x_2,y_2)$

First, calculate the 1st order divided differences.

$[y_0,y_1]=\frac{y_1-y_0}{x_1-x_0}$

Divided Difference Properties

Property 1:
Property 2: