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₀) = 1.
- 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₁) = 0. You can probably see that l₀(x₂) = 0 and l₀(x₃) = 0 as well by the same argument.
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₀) = 0,
- l₁(x₁) = 1,
- l₁(x₂) = 0,
- and l₁(x₃) = 0.
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!
