# 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:

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.

# Hello world!

Welcome to WordPress. This is your first post. Edit or delete it, then start blogging!