First math post: Interpolation

This post really is to test out LaTeX formatting, but I found interpolation somewhat slightly interesting.

So, the motivation for interpolation goes: How do you fit a n-degree polynomial to a set of n+1 data points?... Ok, it's not very motivating... I actually can't think of a reason to fit a n-degree polynomial to anything... except the Taylor fitting, and the Least-Square fit, but those are different. Anyways.

Proposition: Given a set of $n+1$ data points$(x_i, f(x_i))$, such that$x_i \neq x_j$ for $i \neq j$there exists a unique polynomial $p(x) = \sum_{i=0}^n a_ix^i$ of degree $n$ such that $p(x_i) = f(x_i)$ for $i = 0\ldots n$.

Proof: Exercise for the reader.

So how do you find that polynomial? There is the simple straightforward way of doing it by writing out a set of n+1 equations, and solving it by some variation of Gaussian Elimination. In matrix form...

$$\begin{pmatrix}1&x_0&x_0^2&\cdots&x_0^n\\1&x_1&x_1^2&\cdots&x_1^n\\1&x_2&x_2^2&\cdots&x_2^n\\\vdots&\vdots&\vdots&\ddots&\vdots\\1&x_n&x_n^2&\cdots&x_n^n\end{pmatrix}\begin{pmatrix}a_0\\a_1\\a_2\\\vdots\\a_n\end{pmatrix}=\begin{pmatrix}f(x_0)\\f(x_1)\\f(x_2)\\\vdots\\f(x_n)\end{pmatrix}$$

But solving such system with Gaussian Elimination is quite expensive. In fact, it takes order $\mathcal{O}(n^3)$ number of operations.

Fortunately, there is a clever way around solving such a big system to get our polynomial.

The trick is something called the Lagrange polynomial. Consider the i-th Lagrange basis polynomial:

$$l_i(x) = \prod_{k=0, k\neq i}^n \frac{(x-x_k)}{(x_i - x_k)}$$

Clearly, $l_i(x_j) = \delta_{ij}$. So now, all is left is to correctly sum the basis polynomials.

$$L(x) = \sum_{i=0}^n f(x_i)l_i(x) = p(x)$$

The sum of a n-th degree polynomial is also of degree n, and there is a unique polynomial of degree n that interpolates the data points. So since this Lagrange polynomial satisfies $L(x_i) = f(x_i)$ for $i = 0\ldots n$, it must be the only one.

At first, it seems that computing the Lagrange polynomial also requires $\mathcal{O}(n^3)$ operations, but there are simple tricks one may employ to reduce the number of needed operations to $\mathcal{O}(n^2)$. I leave it for the reader to see that this is the case, and see how much cheaper it is to find the interpolant this way instead of naive Gaussian Elimination.

[DM]