Two Results on Polynomial Interpolation in Equally Spaced Points
Original Publication Date: 1899-Dec-30
Included in the Prior Art Database: 2007-Apr-12
Software Patent Institute
Trefethen, L.N.: AUTHOR [+3]
Two Rea,ults on Polynomial Interpolation in Equally Spaced Points L. N. nefethen*
Two Rea,ults on Polynomial Interpolation in Equally Spaced Points
L. N. nefethen*
Department of Mat hematics
Massachusetts Institute of Technology Cambridge, MA 021.39, USA
J. A. C. Weideman
Department of Applied Mathematics
University of the Orange Free State
Bloemfontein 9300, South Africa
We present two results that quantify the poor behavior of polynomial interpolation in equally spaced points. First, in band-limited interpolation of a set of functions such as f,(x) = eianZ (a E R fixed), the error decreases to 0 as n --+ ca if and only if a is small enough to provide at least 6 points per wavelength. Second, the Lebesgue constant A, (supremum norm of the nth interpolation operator) satisfies lirn,,,~Y" = 2.
AMS(M0S) Subject Cl~usification: 41A05, 65D05
Key words and phrases: interpolation, sampling, spectral metholds, Lebesgue constants, Runge phenomenon *Supported by an NSF Presidential Young Investigator Award and by an IBM Faculty Development Award.
It is well known that polynomial interpolation in equally spaced points can be troublesome -
the "Runge phenomenon," discovered by Meray and IEunge at the turn of the century. There is a standard result that quantifies this phenomenon: to ensure p, + f in the supremum norm as n --+ CQ, where p, is the interpolant to a function f in n + 1 equally spaced points on an interval, f must be analytic t,hroughout a certain lens-shaped region of the complex plane [8,10,18,30]. By contrast, pn -+ f is guaranteed for interpolation in Chebyshev points so long as f is somewhat smooth, e.g., Lipschitz continuous. More precisely, it is sufficient for f to satisfy the Dini-Lipschitz condition: w(S) = o(llog 51-'), where w is the modulus of continuity [27, Theorem 14.41.
The purpose of this brief paper is to present two additional results on interpolation in equally spaced points which, although not new except in certain details, are generally unknown even to experts in approximation theory.* Theorem 1 asserts that lip, - f 11 -, 0 is guaranteed for equally spaced points, in a certain sense, if and only iff is appropriately band-limited: the grid must contain at least 6 points per wavelength. This theorem is implicit in the results of a paper by Carlson in 1915
, and generalizations can be found in the literature of entire functions [1,2,4,19,32]. Theorem 2 asserts that the Lebesgue constants An for equispaced interpolation grow asymptotically at a rate given by limn-,A:'" = 2. This result is apparer~tly due first to Turetskii in 1940 , then independently to Scllonhage in 1961 , and an e1emc:ntary proof was devised but not published by Jia in 1980 [I?]. Some references to additional pa.rtia1 results, indep...