An aside where Jeff and I explain Lagrange polynomial interpolation.

*This post written jointly with Jeff Wendling.*

Perhaps you remember how to figure out the equation for a line that goes through two points, but how do you figure out the 19th degree polynomial that goes through any 20 points? That seems really hard. Fortunately some dudes in the late 1700s who almost certainly didn’t have a band figured this out for us.

What we’re going to do is called Lagrange interpolation, named after the second person to figure it out. Interpolation just means we’re going to construct a curve through a set of points.

So, assume we have a set of 4 points. We’ll name them (*x*₀, *y*₀), (*x*₁, *y*₁), (*x*₂, *y*₂), and (*x*₃, *y*₃). We want to construct a degree 3 polynomial that goes through all 4 points. As is frequently the case in math, I’m going to pick something out of thin air and then we’ll look at the properties of that thing. Here’s the thing:

This new function *l*₀ is called a Lagrange basis polynomial. We’ll also need to come up with *l*₁, *l*₂, and *l*₃, but for now we’ll focus on *l*₀. It’s a function of *x* and uses information about our four points, namely, the specific values *x*₀, *x*₁, *x*₂, *x*₃. Notice that *l*₀ ignores *x*₀ in the numerator, but considers it heavily in the denominator.

So, what’s so special about it? Let’s see what happens when we evaluate *l*₀*(x*₀*)* and *l*₀*(x*₁*).*

- When we evaluate
*x*₀, every single numerator factor is equal to its equivalent denominator factor. This means all the terms in the fraction cancel out and the whole thing evaluates to 1. So*l*₀*(x*₀*)*=*.* - When we evaluate
*x*₁, the first numerator factor at the top,*(x-x₁)*, is equal to zero. This means the entire product is zero, so*l*₀*(x*₁*)*=*.*You can probably see that*l*₀*(x*₂*)*=*l*₀*(x*₃*)*=

You also might have noticed a pattern to how the Lagrange basis polynomial was built — there’s a term for every *x* coordinate that isn’t *x*₀ in the numerator, and the denominator looks just like the numerator, except that the variable *x* has been replaced by the specific *x* coordinate *x*₀. For example, here is the definition of the *l*₁ basis polynomial:

Similar to *l*₀, you can probably verify that

*l*₁*(x*₀*)*=*l*₁*(x*₁*)*=*1*,*l*₁*(x*₂*)*=- and
*l*₁*(x*₃*)*=

By extension, *l*₂ is 0 for all points besides *x*₂, where it is 1, and *l*₃ is 0 for all points besides *x*₃, where it is 1.

What can we do with these basis polynomials? We can combine them to make a polynomial that goes through all four points!

This is just the sum of our 4 basis polynomials, where each basis polynomial is multiplied by its corresponding *y* coordinate. Let’s try plugging in one of the *x* coordinates to see what happens, like maybe *x*₂. If we did our job right, we should get *y*₂ out!

This happened because of the neat property of the basis polynomials: they’re equal to zero for all points besides their corresponding point and equal to 1 when it is their corresponding point. Since the 1 gets multiplied by the appropriate *y* coordinate when that happens, we end up with *l*ᵢ*(x*ᵢ*) *=* y*ᵢ for all values *i*! I know, it feels like cheating.

So, okay, we have an equation that goes through all 4 points. But is it a degree 3 polynomial? It turns out, it is! The way this Lagrangian interpolation strategy works for 4 points is that after converting the equation to standard form, the largest exponent for *x* is 3. And since a degree 3 polynomial is uniquely determined by 4 points, we have just found the only degree 3 polynomial that could possibly exist that goes through those 4 points! Thanks, math!