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 \(f(x)\), can we construct a convenient approximate polynomial that reproduces the exact value of \(f(x)\) at some set of points \(\{x_i\}\). Lagrange approached this problem by approximating \(f(x)\) as a linear combination of its values at the interpolation points:

\(\displaystyle P(x) \approx \sum_{k = 0}^{N} L_{n,k}(x) f(x_k) \)

Examining this functional form, we can see that in order to satisfy our requirement that \(\forall k\ P(x_k) = f(x_k)\), we need our functions \(L_{n,k}(x)\) to satisfy the following conditions:

\(\displaystyle L_{n,k}(x_j) = 1 \iff j = k\)\(\displaystyle L_{n,k}(x_j) = 0 \iff j \neq k\)

Lagrange constructed the following functions to satisfy these conditions:

\(\displaystyle L_{n,k}(x) = \prod_{i \neq k} \frac{(x – x_i)}{(x_k – x_i)}\)

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:

**Runge’s Phenomenon**

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.