Lagrange Interpolation Explained: How to Find a Polynomial Through Any Set of Points

Key Takeaways

• The unisolvence theorem guarantees exactly one polynomial of degree n-1 passes through n points
• Lagrange interpolation uses basis polynomials instead of solving equation systems
• This technique is fundamental to zero-knowledge proof systems in cryptography
• For 3 points, you get a unique parabola; for 2 points, a unique line

Here's a question that sounds simple but opens up a rabbit hole: if I give you three points on a graph, can you find a curve that passes through all of them? Turns out, you can. And there's exactly one polynomial of the lowest possible degree that does it. Joseph-Louis Lagrange figured out the slickest way to find it back in the 18th century, and his method is still the go-to approach today.

First, Let's Talk Polynomials

Before we jump into the interpolation stuff, let's make sure we're on the same page about polynomials. A polynomial is just an expression built from a variable x using addition, multiplication, and non-negative integer exponents. Nothing scary.

P(x) = 3x² + 2x + 1

The degree is whatever the highest power of x is. So that example above? Degree 2, which we call quadratic because x² is the boss. A few more examples to hammer this home:

• 5x³ − x is degree 3 (cubic)
• 7x + 4 is degree 1 (linear)
• 42 is degree 0 (constant, just sitting there)

The Problem: Points on a Graph

So here's the setup. You've got three data points expressed as inputs and outputs of some mystery function:

P(1) = 2
P(2) = 5
P(3) = 10

Now the question becomes: how many polynomials can pass through these three points? Through a single point, infinitely many curves fit. Constants, lines, parabolas, cubics, you name it. Add a second point and you eliminate some options, but plenty still work.

This is where the unisolvence theorem comes in clutch. It tells us that n points pin down exactly one polynomial of degree at most n − 1. So with our three points, we're guaranteed exactly one parabola (degree 2) that fits. No line or constant can do it. Just one specific parabola.

• 1 point gives you exactly one degree-0 polynomial (a constant)
• 2 points give you exactly one degree-1 polynomial (a line)
• 3 points give you exactly one degree-2 polynomial (a parabola)

The Brute Force Way (It Works, But Ugh)

Finding that polynomial is called interpolation. And the obvious way to do it is pretty tedious. You set up a system of equations by plugging each point into P(x) = ax² + bx + c:

P(1): a + b + c = 2
P(2): 4a + 2b + c = 5
P(3): 9a + 3b + c = 10

Then you grind through the algebra. Subtract the first equation from the second: 3a + b = 3. Subtract the second from the third: 5a + b = 5. Subtract those results: 2a = 2, so a = 1. Back-substitute and you get b = 0, c = 1.

The answer is P(x) = x² + 1. Great! But honestly, that was a lot of work for three points. Imagine doing this for ten points. Or a hundred. You'd lose your mind setting up all those equations.

Enter Lagrange: A Much Smarter Approach

Joseph-Louis Lagrange looked at this problem and basically said "there's gotta be a better way." And there was. His approach reaches the exact same answer through a completely different method that's way more elegant.

The key insight? Instead of solving for unknown coefficients, Lagrange builds something called basis polynomials. Think of these as building blocks that you can combine to hit any target values you want.

Here's the magic. For each of your points, you construct a polynomial that equals 1 at that point and 0 at every other point. So for our three points at x = 1, 2, and 3, you'd build:

• L₁(x): equals 1 when x=1, equals 0 when x=2 or x=3
• L₂(x): equals 1 when x=2, equals 0 when x=1 or x=3
• L₃(x): equals 1 when x=3, equals 0 when x=1 or x=2

Once you have these basis polynomials, you just multiply each one by the y-value you want at that point and add them up. L₁ gets multiplied by 2 (since P(1) = 2), L₂ gets multiplied by 5, and L₃ gets multiplied by 10.

Building Those Basis Polynomials

So how do you actually construct these basis polynomials? The trick is surprisingly simple. To make a polynomial that equals 0 at specific points, you use factors like (x - 2) which equals 0 when x = 2.

For L₁(x), which needs to be 0 at x=2 and x=3, you start with (x - 2)(x - 3). But wait, this gives you some random value at x=1, not 1. So you divide by whatever that value is to normalize it.

L₁(x) = (x - 2)(x - 3) / ((1 - 2)(1 - 3))
      = (x - 2)(x - 3) / ((-1)(-2))
      = (x - 2)(x - 3) / 2

Plug in x=1 and you get (1-2)(1-3)/2 = (-1)(-2)/2 = 1. Perfect. And if you plug in x=2 or x=3, you get 0 because of those factors in the numerator. The other basis polynomials work the same way.

Why This Actually Matters

Okay, so we've got a cleaner way to find polynomials. Cool. But why should you care beyond solving homework problems?

The kicker? Zero-knowledge proof systems encode computation as polynomials. When a prover wants to convince a verifier of something without revealing the underlying data, they turn their data into evaluations of a polynomial. And Lagrange interpolation is literally how that happens.

ZK proofs are everywhere now. Blockchain privacy, authentication systems, secure voting. All of them rely on this 18th-century math. When you hear about zkSNARKs or zkSTARKs, polynomial interpolation is doing heavy lifting under the hood.

The General Formula

If you want the formal version, here's what Lagrange interpolation looks like for n points. For each point (xᵢ, yᵢ), the basis polynomial Lᵢ(x) is:

Lᵢ(x) = ∏(j≠i) (x - xⱼ) / (xᵢ - xⱼ)

That big ∏ symbol means "multiply all these together for every j that isn't i." Then your final polynomial is just:

P(x) = Σᵢ yᵢ · Lᵢ(x)

Add up all the basis polynomials, each scaled by its corresponding y-value. That's it. No systems of equations. No matrix inversions. Just a direct formula.

Wrapping Up

Lagrange interpolation is one of those techniques that feels like a magic trick the first time you see it. You're given some scattered points, and boom, out pops the exact polynomial that connects them. The math is accessible enough for anyone with basic algebra, but powerful enough to underpin modern cryptographic systems.

Next time you hear about zero-knowledge proofs or polynomial commitments in crypto, remember that 18th-century math is still running the show. Lagrange figured out something timeless, and we're all still benefiting from it.

Frequently Asked Questions

What's the difference between interpolation and curve fitting?

Interpolation finds a polynomial that passes exactly through every point. Curve fitting (like regression) finds a polynomial that gets close to points but doesn't necessarily hit them all, which is useful when you have noisy data.

Can Lagrange interpolation handle duplicate x-values?

No. If you have two points with the same x-value but different y-values, no function can pass through both (since a function can only have one output per input). You'd need to remove duplicates or use a different approach.

Is Lagrange interpolation efficient for large datasets?

For very large numbers of points, other methods like Newton's divided differences or FFT-based approaches can be faster. Lagrange's method is elegant and great for understanding, but it recalculates a lot when you add new points.

Source: DEV Community