Polynomial interpolation

Added 2020-12-19, Modified 2022-09-03

From scratch, using gaussian elimination

Click to add points, code is here.

You can break it by choosing two points on the same vertical line, or picking too many points.

How it works

Say you have points $(1,2), (3,2), (4,5)$ And say you want to find a quadratic which goes through these points.

This is the same as the system of equations

\begin{cases} a(1^2) + b(1) + c = 2 \\ a(3^2) + b(3) + c = 2 \\ a(4^2) + b(4) + c = 5 \end{cases}

Expressed in linear algebra this becomes

\begin{bmatrix}1 & 1 & 1 \\ 1 & 3 & 9 \\ 1 & 4 & 16\end{bmatrix} \begin{bmatrix}a \\ b \\ c\end{bmatrix} = \begin{bmatrix}2 \\ 2 \\ 5\end{bmatrix}

Then you can use elimination to solve $Ax = b$ , as I've done here.

Efficiency

Elimination is $O(n^3)$ , Realistically you should use $O(n^2)$ with Lagrange polynomials wiki, video. (also related to how $A$ is a Vandermonde matrix).

But I like the generality of elimination :D

There are also much more sophisticated techniques, like the Fast Fourier transform which (I think?) is $O(n \log n)$ . I don't understand it yet though.

General interpolation

Polynomial interpolation is cool, but useless in practice since high degree polynomials tend to extreme oscillations. There are other more attractive techniques like Fourier series. I recommended you read (or skim) Numerical Methods if you're interested (I've have lost sleep reading this book, it's that good).