Lagrange Interpolation Primer

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 .

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 points for a polynomial of degree , noted .

The most straightforward way of seeing this is by setting an equation for each point we have:

We can see that we have equations for factors of , noted , which could also be represented with the following Vandermonde matrix equation:

Written as , we can solve this by inverting :

This is doable by applying the Jordan-Gauss algorithm to the augmented matrix , 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 and . 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 , which is of degree . We can guess and deduce we need at least points to describe a polynomial function .

The same goes if we add a third point :

If we did not add this third point and still tried to find a polynomial , 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 , , and to demonstrate this method.

The main principle behind this is to split the wanted function into multiple sub-functions , that each contribute to one given point, also called "node".

We want to construct so that:

Making a function equal to at a certain point is as simple as multiplying it by . Based on this property, we can already "guess" :

Why does multiplying by

add a root ?

For a function , when :

That's a good start! But we have a problem: is not equal to at . We can fix this by dividing by :

And we effectively have . We can now repeat this process for , and :

The polynomial is computed by summing all the together and multiplying them by the corresponding :

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

Generalizing this process, we can write the function that goes through points :