Lagrange interpolation is one of the coolest numerical methods that I have ever studied; there is much beauty in its sublime simplicity. In the post I want to discuss the basic idea of the technique as well as a problem with the technique that has been missing from the textbooks that I have consulted thus far. We wish to solve the following problem: given some function , can we construct a convenient approximate polynomial that reproduces the exact value of at some set of points . Lagrange approached this problem by approximating as a linear combination of its values at the interpolation points:
Examining this functional form, we can see that in order to satisfy our requirement that , we need our functions to satisfy the following conditions:
Lagrange constructed the following functions to satisfy these conditions:
You can verify that this function satisfies the requirements above. For a cool illustration of how well this process can work, consider the figure below:
You can see that as we use more and more interpolation points, our result systematically converges toward the function that we are approximating:
An interesting property of Lagrange interpolation is that adding more interpolation points, and thus using a higher-degree polynomial to approximate our function, can actually lead to worse accuracy in some cases. This problem is known as Runge’s Phenomenon, and is illustrated in the figure below:
As you can see, we no longer obtain well-behaved convergence with higher-order polynomials:
This problem can be ameliorated by the use of better interpolation points such as the Chebyshev nodes, which I will discuss in a future post. The source code used to prepare these plots is available on my github.