A numerical comparison of seven grids for polynomial interpolation on the interval

Seven types of Chebyshev-like grids in one dimension are compared according to four different criteria for accuracy. The grid which minimizes the Lebesgue constant is the best because it performs fairly well by all four criteria. For the same reason, minimizing the Lebesgue constant seems to be the most useful measure of optimality because grids that are good according to this criterion are good when measured by other criteria, too. CFM-optimality, which is the property that all cardinal functions (Lagrange fundamental polynomials) have maxima at the interpolation points, seems to be the least-discriminating criterion because all seven grids generate cardinal functions that have maxima at or very near the interpolation points. The difference between these grids on all four criteria, always less than a factor of two and usually much smaller, are sufficiently modest so that the final choice between grids should probably not be made because of accuracy, but rather based on other criteria such as ease-of-programming, analytical simplicity, conformality with other approximations, and timestep in applications to partial differential equations. To explore such nonaccuracy issues, we also compared six of the grids on the basis of maximum allowed timestep when the grid is used to discretize the spatial coordinate and an explicit scheme is used for time-marching. The Lebesgue-optimal grid is also nearly optimal in the sense of allowing the longest timestep. With a pseudospectral (collocation) algorithm, the Lebesgue grid allows a timestep three-halves as long as that of the Legendre-Lobatto spectral element method.