Choosing Chebyshev Interpolation Points

In polynomial interpolation, the choice of interpolation points plays a critical role in the accuracy of the resulting polynomial. A poor choice of points can lead to large oscillations near the endpoints of the interval, a phenomenon known as Runge's phenomenon. To reduce these oscillations and improve approximation, mathematicians have introduced the concept of Chebyshev points, which are specifically designed to minimize the maximum error of the interpolating polynomial over a given interval.

Theorem — Chebyshev Interpolation Points

Let \( f \in \mathcal{C}^{n+1}([a, b]) \) and \( p_n(x) \) be the polynomial of degree \( n \) interpolating \( f \) at \( n+1 \) points \( x_0, x_1, \dots, x_n \). The interpolation error is

\[ E_n(x) = f(x) - p_n(x) \]

The maximum error \( \max_{x \in [a, b]} |E_n(x)| \) is minimized when the points are chosen as the Chebyshev points:

\[ x_i = \frac{a + b}{2} + \frac{b - a}{2} \cos\left( \frac{2i + 1}{2n + 2} \pi \right), \quad i = 0, 1, \dots, n \]

These points cluster near the endpoints, reducing the risk of large oscillations. The corresponding interpolation error is bounded by:

\[ |E_n(x)| \leq \frac{1}{2^n (n+1)!} \max_{x \in [a, b]} |f^{(n+1)}(x)| \]

Example 1 — Interpolating \( \sin(x) \) on \([0, \pi]\)

Let us consider \( f(x) = \sin(x) \) and interpolate it using a polynomial of degree 2. We will compare the results using equally spaced points and Chebyshev points.

1. Equally spaced points

• Interpolation points: \( x_0 = 0, \ x_1 = \pi/2, \ x_2 = \pi \)
• Interpolating polynomial:

\[ p_2(x) = -\frac{4}{\pi^2} x^2 + \frac{4}{\pi} x \]

Although this polynomial passes through the points, it exhibits slight oscillations between points, especially near \( x = 0 \) and \( x = \pi \).

2. Chebyshev points

• Computed points on \([0, \pi]\) (rounded):

\( x_0 \approx 2.931 \), \( x_1 \approx 1.571 \), \( x_2 \approx 0.210 \)

• Interpolating polynomial (rounded coefficients):

\[ p_T(x) = -0.4275 x^2 + 1.343 x - 0.0548 \]

Using Chebyshev points, the polynomial approximates \( \sin(x) \) more accurately across the interval and reduces the extreme oscillations seen with equally spaced points. This demonstrates the advantage of careful node selection in polynomial interpolation.

Illustration

Figure: The following plot compares the two interpolations:

• Blue curve: original function \( \sin(x) \)
• Red curve: degree-2 polynomial with equally spaced points
• Green curve: degree-2 polynomial with Chebyshev points