Browse Prior Art Database

Two Results on Polynomial Interpolation in Equally Spaced Points

IP.com Disclosure Number: IPCOM000149107D
Original Publication Date: 1899-Dec-30
Included in the Prior Art Database: 2007-Apr-12

Publishing Venue

Software Patent Institute

Related People

Trefethen, L.N.: AUTHOR [+3]

Abstract

Two Rea,ults on Polynomial Interpolation in Equally Spaced Points L. N. nefethen*

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 8% of the total text.

Page 1 of 32

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

Abstract

   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.

[This page contains 1 picture or other non-text object]

Page 2 of 32

[This page contains 1 picture or other non-text object]

Page 3 of 32

1. Introduction


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
[7], 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 [28], then independently to Scllonhage in 1961 [24], and an e1emc:ntary proof was devised but not published by Jia in 1980 [I?]. Some references to additional pa.rtia1 results, indep...