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\ jneq iend{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_{xin[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.

The post Lebesgue constants first appeared on John D. Cook.

Liked Liked