Does Lagrange interpolation at Chebyshev points solve the Runge phenomenon?

Question

I recently came across the concept of the Runge phenomenon while studying numerical methods for special functions in the book "Numerical Methods for Special Functions" by Amparo Gil, specifically in Chapter 3, Section 3.2.1. It was highlighted that the Runge phenomenon often occurs when equispaced interpolating points are used in Lagrange interpolation. This raised a couple of questions in my mind. Firstly, if we were to utilize Chebyshev points (roots of the K-th Chebyshev polynomial) instead of equispaced points but still apply Lagrange interpolation at these Chebyshev points, would this approach effectively solve the Runge phenomenon? Additionally, assuming the above is true, I am curious about the specific advantages or additional benefits of employing Chebyshev interpolation in the first place. What distinguishes Chebyshev interpolation using Lagrange polynomials at Chebyshev points, and what advantages does it offer over traditional Lagrange interpolation with equispaced points? I would greatly appreciate any insights or clarification on these questions.

Answer 1

Let's consider a function $f(x)$ over the interval $[0,1]$. For instance, we can use $f(x) = \sin^2(e^{2x})$. The following plot illustrates this function along with its polynomial interpolant using 11 equally spaced nodes:

This look fine, however, when we plot the error as we increase the number of nodes, an interesting pattern emerges:

Contrary to what one might expect, increasing the number of nodes $n$ does not always decrease the error. In fact, the error begins to increase, indicating a loss of convergence, a sign of ill conditioning due to the use of equally spaced nodes. Using the polynomial interpolation error formula (see Lagrange remainder form), we can visualize the error indicator:

Here, we observe that $\Phi(x)$ decreases exponentially at each fixed location in the interval and $\Phi(x)$ is larger at the ends of the interval than in the middle, by an exponentially growing factor. This gap is what can ruin the convergence of polynomial interpolation.

To further illustrate the Runge phenomenon, consider the function $f(x)=1/(x^2+16)$ over $[-1,1]$ using the same approach as above

This instability in convergence is the Runge phenomenon. Chebyshev nodes are introduced to mitigate this issue. Having more nodes near the ends of the interval than in the middle could decrease the error.

By employing Chebyshev nodes, we obtain the following result:

The error remains consistently within machine epsilon, and it stays stable as the number of nodes increases. Importantly, as predicted by the error indicator function, the error is uniform across the interval at each value of $n$.