Lagrange interpolation for IQ < 200

Remember those kids’ drawings where you need to connect the dots to form an image? After all these years, we finally present you with a way to cheat.

Interpolation is a method for estimating values between known points. These points can be, for example, temperature measurements, points in a chart or just dots in a drawing.

You can either connect the dots or interpolate

Instead of simply connecting the dots, interpolation gives us a formula that passes through them. In this article, we’ll explain how this works using a method popularized by the mathematician Joseph-Louis Lagrange.

Quick definitions

First, let’s get a few terms settled:

• A coefficient is the number in front of a variable. For example 13, — 5 and 7 are coefficients in function f(x) = 13x^4 — 5x + 7 (the last variable is implicit x^0).
• A polynomial is a function made of coefficients and powers of x. The coefficients usually come from numbers you know, like integers or fractions.
• A degree of a polynomial is the highest exponent. In our previous example, the polynomial’s degree is 4.

We will use polynomials throughout this article, since Lagrange interpolation produces polynomials.

What does Lagrange interpolation give us?

Performing the interpolation on a set of points produces a polynomial that passes through each of the provided points.

For example, suppose we have the points (1,3) and (3,5). We’ll show how to perform the interpolation in detail later, but for now, here are two polynomials that pass through these points: f(x) = x + 2 and f(x) = x^3 — 12x + 14.

Lagrange interpolation always returns the unique polynomial of lowest possible degree that passes all the points. For example, even though the blue curve also passes the points, Lagrange returns the red line because it has the minimal degree.

Typically, the minimal degree is one less than the number of points. In rare cases, however, the points may be perfectly aligned, allowing for a lower-degree polynomial. For instance, in our previous example, adding a third point at (2,4) would still allow the same red line to interpolate all points.

Interpolation with one point

Consider the point (3,5). What’s the polynomial of minimal degree that passes through this point?

For our point we know that x = 3 gives y = 5. Since we only have one point, there’s no information about how the polynomial should behave elsewhere. The lowest-degree choice is a constant polynomial that doesn’t change with x: f(x) = 5.

Things get a bit more interesting (and challenging) once we have more points.

Two points without Lagrange

Let’s use points (1,3) and (3,5) again.

We know we can connect two points by drawing a straight line. How can we get the polynomial that corresponds to this line?

A line is a degree 1 polynomial: f(x) = ax + b where a tells us how quickly the line rises as x (the slope) increases, and b is the resulting value of the polynomial when x = 0.

To find the slope a:

Since we don’t know b yet, we can solve it by requiring the line to pass through one of our points. Let’s plug (1,3) and the value of a into our function f(x) = ax + b:

By plugging in a and b, we get the final polynomial f(x) = x + 2.

The Lagrange method

The same reasoning works if we add more points, but the calculations quickly become messy. Lagrange interpolation gives us a cleaner way to handle it.

The basic idea is straightforward:

1. Focus on each point individually. For each point, create an intermediary polynomial that equals 1 at that point and 0 at all the others. We’ll call these polynomials L_i where i is the index of the point.
2. Weight by the y value. Multiply each of these intermediary polynomials by the corresponding y value of the point. We’ll call these polynomials P_i where i is again the index of the point.
3. Combine the polynomials. Add all these polynomials together to get the final polynomial, which passes through all points.

We’ll go through the details below

Lagrange for two points

Let’s go through the steps with a concrete example. We’ll use points (1,3) and (3,5) again.

Step 1: focus on each point individually

Let’s first create the intermediary polynomial for the point (1,3). We want a polynomial that:

1. Is 1 at the target point, x = 1.
2. Is 0 in every other point. We only have one other point: (3,5). So the polynomial needs to be 0 at x = 3.

Starting from the second requirement, we start with a term that equals 0 at the point x = 3. The simplest choice is x — 3. At x = 3, this term is 3 — 3 = 0, so it meets our requirement.

To fulfill the first requirement, we need to adjust x - 3 so that it equals 1 at x = 1. At x = 1 the term x - 3 is 1 – 3 = -2. To make -2 equal 1, we divide it by -2: -2 / -2 = 1. Therefore, our first intermediary polynomial becomes:

And the same polynomial visually:

This polynomial fulfills our requirements: it’s 1 when x=1 and 0 when x=3

We can use the same logic to calculate the second intermediary polynomial:

1. Find a term that equals 0 at point x = 1. The simplest choice is x - 1.
2. Adjust x — 1 so that it equals 1 at x = 3. Calculate 3 — 1 = 2 . Therefore, to make 2 equal 1, divide it by 2.

And visually:

This polynomial fulfills our requirements: it’s 1 when x=3 and 0 when x=1

Step 2: weight by the y value

If we combined the intermediary polynomials as they are, the y value at each point would be just 1. Our points have different y values. To fix this, we weight each intermediary polynomial by the actual y value of its point.

Remember that our points are (1,3) and (3,5).

To weight the first intermediary polynomial, we multiply it by the point’s y value:

And the second:

Step 3: Combine the polynomials

Now we have separate polynomials that each reach their corresponding point and are zero in other points. To get the final result, we simply sum these polynomials:

We get the same result as without Lagrange. Visually, the construction looks like this:

Red + Blue = Purple

Lagrange with three points

The same logic works for any number of points.

Let’s add a third point. Our points are: (1,3), (3,5) and (2,6).

Step 1: focus on each point individually

For point (1,3), we want an intermediary polynomial that:

1. Is 1 when x = 1.
2. Is 0 when x = 3 and x = 2.

Starting again from the second requirement, we can see that the simplest choice is (x — 3)(x - 2). With this term, the result is zero if x = 3 or x = 2 (with either of those values, one of the sides becomes zero, making the whole multiplication zero).

To fulfill the first requirement, let’s adjust (x — 3)(x - 2) so that it equals 1 at x=1. At x=1 the term (x - 3)(x - 2) is (1 – 3)(1 – 2) = 2.

Following the same logic, we can construct all of the intermediary polynomials:

Step 2: weight by the y-value

Weight the polynomials:

Step 3: Combine the polynomials

Finally, we sum the polynomials:

Here’s the same process visually:

Red + Blue + Orange = Green

But why?

Playing with dots and lines is fun, but how is this useful?

These dots don’t need to be just points on a chart, they can represent real data. Interpolation is what lets us turn scattered values into a whole picture, and that idea has many powerful uses:

• Data recovery: if you lose some of the data points, their data can be interpolated. For example, missing audio data can be interpolated.
• Zero Knowledge Proofs: much of the computation is represented as polynomials. Verifiers do not verify each point, they only sample points from the polynomial. Thanks to Schwartz-Zippel lemma and interpolation, it’s easy to compare polynomials by knowing just a few points.
• Graphics: computer graphics often rely on interpolation to generate smooth motion between points.

We’re not alone

Lagrange interpolation is not the only cool kid on the block: other interpolation techniques exist as well.

In fact, it’s usually not the most efficient way to interpolate points. But it is one of the easiest to understand and work with, which makes it perfect for learning and teaching.

For real-world applications, something called Fast Fourier Transform is often utilized instead.

Conclusions

Okay, this is not super useful for children’s drawings. But it’s a powerful method when you need to find a polynomial that passes through a given set of points.

The core idea stays the same no matter how many points you add: build simple intermediary polynomials, weight them, and add them together. The more points you have, the more work there is in the details, but the principle never changes.

That’s what makes Lagrange interpolation valuable: it’s simple to understand, guaranteed to give a unique result, and easy enough to implement in code.

Thanks

Thanks to Frank Mangone for reviewing a version of this article and making sure it makes sense!

About the author

I’m a ZK & EVM freelancer. I do development and write mostly about Zero Knowledge topics and ecosystems. Wanna have a chat? Get in touch!