Polynomial interpolation

Click to add points

You can break it by choosing two points on the same virtical 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.