Chebyshev extreme points

Section 22.3 Chebyshev extreme points

Figure 22.2.2 involves the midpoints of equal arcs, which should remind us of the Midpoint Rule. There is a parallel “trapezoidal” story, in which we consider the endpoints of all these arcs and give half the weight to the smallest and largest.

🔗

Figure 22.3.1. Chebyshev points of the second kind
🔗

These projections are called “Chebyshev extreme points” or “Chebyshev points of the second kind”. Explicitly, they are

\begin{equation} x_k = \cos(\pi k/n) \quad \text{where } k=0, 1, \dots, n\tag{22.3.1} \end{equation}

In Matlab one could write

x = cos(linspace(0, pi, n+1));

While the midpoint projections (Chebyshev points of the first kind) are the roots of polynomials \(T_n\text{,}\) the points (22.3.1) are the extreme points of \(T_n\text{.}\) Indeed, the identity (22.2.2) says that \(T_n\) attains extreme values \(\pm 1\) when \(\cos (n\theta) = \pm 1\text{,}\) hence \(\theta = \pi k/n\text{,}\) hence \(x = \cos(\pi k/n)\text{.}\)

🔗

Note that in this section, unlike the previous ones, we have \(n+1\) points of interpolation, rather than \(n\text{.}\) This is more convenient notation-wise, similarly to how the Trapezoidal rule with \(n\) subintervals uses \(n+1\) points of evaluation, while the Midpoint rule with the same subintervals uses \(n\) points.

🔗

An advantage of using Chebyshev extreme points (22.3.1) as the points of interpolation is that one does not need to compute the weights like we did in Example 22.2.3. For this specific choice of points, the weights in the barycentric formula (21.2.5) turn out to be

\begin{equation} w_k = (-1)^k \quad \text{except } w_0=1/2, w_n = (-1)^n/2\tag{22.3.2} \end{equation}

This means that the barycentric formula for interpolation can be written as

\begin{equation} p(x) = \frac{\sum'_{0\le k\le n} y_k (-1)^k (x-x_k)^{-1}}{ \sum'_{0\le k\le n} (-1)^k (x-x_k)^{-1} } \tag{22.3.3} \end{equation}

where primes over summation signs mean that the terms with \(k=0, n\) should be divided by 2 (the “trapezoidal” adjustment). Formula (22.3.3) also works for an arbitrary interval \([a, b]\text{,}\) where the Chebyshev extreme points are

\begin{equation*} x_k = \frac{b-a}{2} \cos(\pi k/n) + \frac{a+b}{2} \end{equation*}

Note that the function \(p\) is in fact a polynomial of degree \(n\text{,}\) even if the formula does not look like it. The straightforward way of expressing a polynomial of high degree, as a sum of powers with constant coefficients, is likely to cause numerical issues (see Section 21.1), while the barycentric formula (22.3.3) is numerically stable.

🔗

Example 22.3.2. Interpolate through Chebyshev extreme points.

Use the formula (22.3.3) to interpolate a few functions such as

\(f(x) = 1/(x^2+1)\) on \([-5, 5]\)

🔗
\(f(x) = \tan^{-1} x\) on \([-7, 11]\)

🔗
\(f(x) = \cos(2x)\) on \([1, 15]\)

🔗
\(f(x) = \sin(x^2)\) on \([0, 5]\)

🔗
\(f(x) = \operatorname{sign} x\) on \([-1, 1]\)

🔗

Use \(20\) Chebyshev extreme points (or more if you prefer).

🔗

Answer.

f = @(x) 1./(x.^2+1);  % or another f 
n = 19;   % there will be n+1 = 20 points
a = -5;   % or another a
b = 5;    % or another b

x = cos(linspace(0, pi, n+1)) * (b-a)/2 + (a+b)/2;  % Chebyshev extreme points
y = f(x);
w = (-1).^(0:n);             % simple formula for weights
w([1 end]) = w([1 end])/2;   % trapezoidal adjustment 

p = @(t) (y.*w*(t - x').^(-1)) ./ (w*(t - x').^(-1));
t = linspace(a-0.01, b+0.01, 1000);
plot(x, y, 'k*', t, f(t), 'r', t, p(t), 'b')

The plot includes the points of interpolation as black asterisks, the original function is a red curve, and the interpolating polynomial as a blue curve. Often the blue curve follows the red one so precisely that it covers it completely.

🔗

Prev Top Next