Lebesgue constants

I alluded to Lebesgue constants in the previous post without giving them a name. There I said that the bound on order n interpolation error has the form

$ch^{n+1} + \lambda \delta$

where h is the spacing between interpolation points and δ is the error in the tabulated values. The constant c depends on the function f being interpolated, and to a lesser extent on n. The constant λ is independent of f but depends on n and on the relative spacing between the interpolation nodes. This post will look closer at λ.

Given a set of n + 1 nodes T

$a = x_0 < x_1 < x_2 < \cdots < x_{n-1} < x_n = b$

define

$\ell_j(x) := \prod_{\begin{smallmatrix}i=0\\ j\neq i\end{smallmatrix}}^{n} \frac{x-x_i}{x_j-x_i}$

Then the Lebesgue function is defined by

$\lambda_n(x) = \sum_{j=0}^n |\ell_j(x)|$

and the Lebesgue constant for the grid is the maximum value of the Lebesgue function

$\Lambda_n(T)=\max_{x\in[a,b]} \lambda_n(x)$

The values of Λ are difficult to compute, but there are nice asymptotic expressions for Λ when the grid is evenly spaced:

$\Lambda_n \sim \frac{2^{n+1}}{n \log n}$

When the grid points are at the roots of a Chebyshev polynomial then

$\Lambda_n \approx \frac{2}{\pi} \log(n + 1) + 1$

The previous post mentioned the cases n = 11 and n = 29 for evenly spaced grids. The corresponding values of Λ are approximately 155 and 10995642. So 11th order interpolation is amplifying the rounding error in the tabulated points by a factor of 155, which might be acceptable. But 29th order interpolation is amplifying the rounding error by a factor of over 10 million.

The corresponding values of Λ for Chebyshev-spaced nodes are 2.58 and 3.17. Chebyshev spacing is clearly better for high-order interpolation, which you have that option.

Leave a Reply