# Lagrange Polynomial

| math

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.