Lagrange Interpolation I: Runge’s Phenomenon

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:

Interpolation of f(x) = cos(x) by Lagrange Polynomials constructed by successively more interpolation points.
Interpolation of f(x) = cos(x) by Lagrange Polynomials constructed by successively more interpolation points.

You can see that as we use more and more interpolation points, our result systematically converges toward the function that we are approximating:

Errors caused by Lagrange Interpolation using various numbers of points.
Errors caused by Lagrange Interpolation using various numbers of points.

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:

Non-uniform convergence in interpolating polynomials due to high oscillation near interval endpoints.
Non-uniform convergence in interpolating polynomials due to high oscillation near interval endpoints.

As you can see, we no longer obtain well-behaved convergence with higher-order polynomials:

Errors do not decrease uniformly with increasing degree of the interpolating polynomial.
Errors do not decrease uniformly with increasing degree of the interpolating polynomial.

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.

Just another WordPress site