Convergence of Chebyshev interpolation

from pylab import *
from scipy.interpolate import barycentric_interpolate

Trefethen, 2019 provides more details and proof regarding these results.

6.6.1Chebyshev series¶

6.6.2Projection and interpolation¶

The Chebyshev projection is obtained by truncating the Chebyshev series

f_n(x) = \sum_{k=0}^n a_k T_k(x)

(4)

Let $p_n(x)$ be the interpolation of $f(x)$ at $n+1$ Chebyshev points, and let us write it as

p_n(x) = \sum_{k=0}^n c_k T_k(x)

(5)

6.6.2.1Differentiable functions¶

Thus $f^{(\nu)}$ of bounded variation implies that the convergence is at an algebraic rate of $\order{n^{-\nu}}$ for $n \to \infty$ . The more derivative the function has, the faster is the convergence.

Example 1 (Piecewise continuous function)

For $\nu = 0$ , e.g., $f(x) = \textrm{sign}(x)$ , we cannot hope for convergence since polynomials are continuous and sign function is not.

Even the projections do not converge, since

|a_k| = \order{ \frac{1}{k} }, \qquad f(x) - f_n(x) = \sum_{k=n+1}^\infty a_k T_k(x)

(8)

and

\norm{f - f_n}_\infty \le \sum_{k=n+1}^\infty |a_k| \not\to 0

(9)

since $\sum_k (1/k)$ is not finite.

f = lambda x: sign(x)
xp = linspace(-1,1,1000)
for n in [11,21,41]:
    theta = linspace(0,pi,n+1)
    x = -cos(theta)
    y = f(x)
    yp = barycentric_interpolate(x,y,xp)
    plot(xp,yp,label='n='+str(n))
plot(xp,f(xp),label='Exact')
legend(), xlabel('x'), ylabel('y');

On the average, the error decreases, but around $x=0$ , it does not decrease. The Gibbs oscillations are observed when we try to approximate a discontinuous function with polynomials.

Example 2 (Piecewise differentiable function)

For $\nu = 1$ , e.g., $f(x) = |x|$ , we have $V=2$ and the above theorem predicts convergence since

\norm{f - f_n}_\infty \le \frac{4}{\pi(n-1)}, \qquad \norm{f - p_n}_\infty \le \frac{8}{\pi (n-1)}

(10)

The degree 10 interpolant looks like this.

f = lambda x: abs(x)
n = 10
xp = linspace(-1,1,1000)
theta = linspace(0,pi,n+1)
x = -cos(theta)
y = f(x)
yp = barycentric_interpolate(x,y,xp)
plot(x,y,'o',label='Data')
plot(xp,f(xp),label='Exact')
plot(xp,yp,label='Interpolant')
legend(), xlabel('x'), ylabel('y')
title('Degree '+str(n)+' interpolant');

Now compute error norm for increasing degree. The norm is only an approximation.

n = 10
nvalues,evalues = [],[]
for i in range(10):
    theta = linspace(0,pi,n+1)
    x = -cos(theta)
    y = f(x)
    yp = barycentric_interpolate(x,y,xp)
    e = abs(f(xp) - yp).max()
    nvalues.append(n), evalues.append(e)
    n = 2 * n
nvalues = array(nvalues)
loglog(nvalues,evalues,'o-',label="Error")
loglog(nvalues, 8/(pi*(nvalues-1)),label="$8/(\\pi (n-1))$")
legend(), xlabel('n'), ylabel('$||f-p_n||$');

In log-log scale, we see that $\log\norm{f-p_n}_\infty$ versus $\log(n)$ is a straight line with slope -1 (check), consistent with the theorem.

6.6.2.2Analytic functions¶

For any $\rho > 1$ , the Bernstein ellipse $E_\rho$ is the ellipse with foci at $x=-1$ and $x=+1$ and

\rho = \textrm{semi-minor axis + semi-major axis}

(11)

It can be obtained by mapping the circle of radius ρ, $\xi = \rho \exp(\ii \theta)$ , under the Joukowsky map

z = \half (\xi + \xi^{-1})

(12)

theta = linspace(0,2*pi,500)
for rho in arange(1.1,2.1,0.1):
    xi = rho * exp(1j * theta)
    z = 0.5 * (xi + 1/xi)
    plot(real(z), imag(z),'k-')
plot([-1,1],[0,0],'r-'), axis('equal')
title('Bernstein ellipses');

Example 3

We interpolate the function $f(x) = 1/(1+16 x^2)$ with Chebyshev points. It is analytic in a region of the complex plane enclosing the real interval $[-1,1]$ .

f = lambda x: 1.0/(1.0 + 16 * x**2)
n = 10
nvalues,evalues = [],[]
for i in range(10):
    theta = linspace(0,pi,n+1)
    x = -cos(theta)
    y = f(x)
    yp = barycentric_interpolate(x,y,xp)
    e = abs(f(xp) - yp).max()
    nvalues.append(n), evalues.append(e)
    n = n + 10
nvalues = array(nvalues)
semilogy(nvalues,evalues,'o-',label="Error")
legend(), xlabel('n'), ylabel('$||f-p_n||$');

We see that $\log\norm{f - p_n}_\infty$ versus $n$ is a straight line, indicating exponential decrease of the error wrt $n$ .

References¶

Trefethen, L. N. (2019). Approximation Theory and Approximation Practice, Extended Edition. Society for Industrial. 10.1137/1.9781611975949

Numerical Analysis

Potential theory