I'm reading about polynomial interpolation in my numerical math book at the moment. The Lagrange interpolating polynomial is the unique polynomial of lowest degree that interpolates a given set of \(n\) points \((x_0, y_1),\) \((x_1, x_1), \ldots ,\) \((x_n, y_n). \) The \(x\) values of these points are called nodes and we require them to be distinct (why would you have the same data point twice, anyway).
Now we need to find a polynomial that evaluates to \(y_j\) for node \(x_j,\) where \(0 \leq j \leq n.\)
One idea is to use the \(y\) values for the polynomial and only select
\(y_j\) when calculating the value for \(x_j.\)
This selection of the right \(y\) values is what the Lagrange coefficients \(l_j(x)\) do for us.
$$
l_j(x) = \prod_{\substack{i=0 \\ i \neq j}}^{n} \frac{x-x_i}{x_j - x_i}
$$
If \(x\) is some \(x_k\) from our set of nodes, the Lagrange coefficient evaluates to either zero or one.
If \(j \neq k \), we must have \(x_k = x_i\) for \(i=k\) in the numerator, thus one factor is zero and the whole product is zero.
If \(j = k\), the numerator is always \(x_j - x_i\), thus each factor and the whole product is one.
Using the Lagrange coefficients, we can construct a polynomial \(p\) such that \(p(x_j) = y_j\) for \(0 \leq j \leq n.\) $$ L(x) = \sum_{j=0}^n l_j(x) y_j $$ Each coefficient \(l_j(x)\) is a product of \(n\) factors, that is, each is a polynomial of degree \(n\). If we add a data point, the polynomials will be of degree \(n+1\) and we'll need to recompute all of them, which is a bit of a disadvantage this method has.
I coded a quick interactive demo.
Click somewhere in the box below to add points and see the Lagrange polynomial interpolation in action.
Each click adds a point and redraws the diagram.
Use the button to reset if it gets too crazy.
How does this work? I sample a number of \(x\) values, calculate \(L(x)\) as introduced above, and connect these points by straight lines. If the sampled values are close enough to each other, you won't notice that this is actually a piecewise linear approximation of a curve.