Lagrange Interpolation Primer

A quick and simple explaination on the concept of polynomial interpolation, here Lagrange's in particular.

04/12/2024 · 4 min read · sapling 🪴

You may remember, when in High School, being asked to find the equation of a line that goes through two points. The process was straightforward: you would calculate the slope and the intercept of the line f(x) = a x + b .

This is a simple example of polynomial interpolation, where we are trying to find a polynomial that goes through a set of points. While the process is simple for a line, it becomes slightly more complex for higher degree polynomials.

Polynomials

One of the most, if not the most important property of polynomials, is that each one of them can uniquely be described by n+1 n+1 points for a polynomial of degree , noted f(x) in PP_n .

The most straightforward way of seeing this is by setting an equation for each point A_i (x_i, y_i) we have:

$P_n (x) = u_0 + u_1 x + ... + u_n x^n = f(x) \ ca$ $P_n (x) = u_0 + u_1 x + ... + u_n x^n = f(x) \ ca$

We can see that we have n+1 n+1 equations for n+1 n+1 factors of , noted u_i | 0 <= i <= n , which could also be represented with the following Vandermonde matrix equation:

Written as V u = y V u = y , we can solve this by inverting :

This is doable by applying the Jordan-Gauss algorithm to the augmented matrix V | I V | I , where is the identity matrix (diagonal filled with s), until we only have pivots equal to :

If you prefer to see this in a graphical way, let’s consider the following example:

We have two points A_0 (1, 2) and A_1 (-2, -3) . We can represent them as follows:

It is visually obvious that we can only draw a single line that goes through both points.

A line is essentially just f(x) = a x + b , which is of degree . We can guess and deduce we need at least n+1 n+1 points to describe a polynomial function f(x) in PP_n .

The same goes if we add a third point A_2 (0, 4) :

If we did not add this third point and still tried to find a polynomial P_2 (x) P_2 (x) , we would have an infinite number of solutions:

But now the question is: how do we actually find the polynomial that goes through all the points? This is where Lagrange interpolation comes into play.

Lagrange Interpolation

Let’s take A_0 (0, 1) , A_1 (1, 3) , A_2 (2, 2) and A_3 (3, 4) to demonstrate this method.

The main principle behind this is to split the wanted function into multiple sub-functions l_i (x) l_i (x) , that each contribute to one given point, also called “node”.

We want to construct l_i (x) l_i (x) so that:

Making a function equal to at a certain point x_j x_j is as simple as multiplying it by (x - x_j) . Based on this property, we can already “guess” l_1^* (x) :

Why does multiplying by (x-x_j)

add a root ?

For a function f(x) = (x - x_j) dot g(x) | g(x) <- RR[x] , when x = x_j x = x_j :

That’s a good start! But we have a problem: l_1^* (x) is not equal to at x = 1 x = 1 . We can fix this by dividing by l_1^* (1) :

$l_1 (x) &= (l_1^* (x)) / (l_1^* (1)) \ &=$ $l_1 (x) &= (l_1^* (x)) / (l_1^* (1)) \ &=$

And we effectively have l_1 (1) = 1 . We can now repeat this process for l_0 (x) l_0 (x) , l_2 (x) l_2 (x) and l_3 (x) l_3 (x) :

The polynomial f(x) in PP_3 is computed by summing all the l_i (x) l_i (x) together and multiplying them by the corresponding y_i y_i :

And we have our final polynomial which effectively goes through all the points:

Generalizing this process, we can write the function f(x) in PP_n (x) that goes through n+1 n+1 points A_i (x_i, y_i) :

$f(x) &= sum_(i=0)^n y_i l_i (x) \ &= sum_($ $f(x) &= sum_(i=0)^n y_i l_i (x) \ &= sum_($