Newton interpolation in Fejér and Chebyshev points
Authors:
Bernd Fischer and Lothar Reichel
Journal:
Math. Comp. 53 (1989), 265278
MSC:
Primary 65D05; Secondary 30E10, 65E05
MathSciNet review:
969487
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: Let be a Jordan curve in the complex plane, and let be the compact set bounded by . Let f denote a function analytic on . We consider the approximation of f on by a polynomial p of degree less than n that interpolates f in n points on . A convenient way to compute such a polynomial is provided by the Newton interpolation formula. This formula allows the addition of one interpolation point at a time until an interpolation polynomial p is obtained which approximates f sufficiently accurately. We choose the sets of interpolation points to be subsets of sets of Fejér points. The interpolation points are ordered using van der Corput's sequence, which ensures that p converges uniformly and maximally to f on as n increases. We show that p is fairly insensitive to perturbations of f if is smooth and is scaled to have capacity one. If is an interval, then the Fejér points become Chebyshev points. This special case is also considered. A further application of the interpolation scheme is the computation of an analytic continuation of f in the exterior of .
 [1]
J.
H. Curtiss, Riemann sums and the fundamental polynomials of
Lagrange interpolation, Duke Math. J. 8 (1941),
525–532. MR 0005190
(3,115c)
 [2]
Philip
J. Davis, Interpolation and approximation, Blaisdell
Publishing Co. Ginn and Co. New YorkTorontoLondon, 1963. MR 0157156
(28 #393)
 [3]
Michael
Eiermann and Wilhelm
Niethammer, Interpolation methods for numerical analytic
continuation, Multivariate approximation theory, II (Oberwolfach,
1982) Internat. Ser. Numer. Math., vol. 61, Birkhäuser, Basel,
1982, pp. 131–141. MR 719903
(85d:30050)
 [4]
Bernd
Fischer and Lothar
Reichel, A stable Richardson iteration method for complex linear
systems, Numer. Math. 54 (1988), no. 2,
225–242. MR
965923 (90a:65060), http://dx.doi.org/10.1007/BF01396976
 [5]
Dieter
Gaier, Vorlesungen über Approximation im Komplexen,
Birkhäuser Verlag, BaselBoston, Mass., 1980 (German). MR 604011
(82i:30055)
 [6]
Walter
Gautschi, Questions of numerical condition related to
polynomials, Studies in numerical analysis, MAA Stud. Math.,
vol. 24, Math. Assoc. America, Washington, DC, 1984,
pp. 140–177. MR
925213
 [7]
K.
O. Geddes and J.
C. Mason, Polynomial approximation by projections on the unit
circle, SIAM J. Numer. Anal. 12 (1975),
111–120. MR 0364977
(51 #1230)
 [8]
Peter
Henrici, Essentials of numerical analysis with pocket calculator
demonstrations, John Wiley & Sons, Inc., New York, 1982. MR 655251
(83h:65002)
 [9]
Peter
Henrici, Applied and computational complex analysis. Vol. 3,
Pure and Applied Mathematics (New York), John Wiley & Sons, Inc., New
York, 1986. Discrete Fourier analysis—Cauchy
integrals—construction of conformal maps—univalent functions; A
WileyInterscience Publication. MR 822470
(87h:30002)
 [10]
Edmund
Hlawka, The theory of uniform distribution, A B Academic
Publishers, Berkhamsted, 1984. With a foreword by S. K. Zaremba; Translated
from the German by Henry Orde. MR 750652
(85f:11056)
 [11]
Lloyd
N. Trefethen (ed.), Numerical conformal mapping, NorthHolland
Publishing Co., Amsterdam, 1986. Reprint of J. Comput.\ Appl.\ Math.\ {14}
(1986), no.\ 12. MR 874989
(87m:30013)
 [12]
J.
L. Walsh, Interpolation and approximation by rational functions in
the complex domain, Third edition. American Mathematical Society
Colloquium Publications, Vol. XX, American Mathematical Society,
Providence, R.I., 1960. MR 0218587
(36 #1672a)
 [13]
Wilhelm
Werner, Polynomial interpolation: Lagrange
versus Newton, Math. Comp.
43 (1984), no. 167, 205–217. MR 744931
(86g:65024), http://dx.doi.org/10.1090/S00255718198407449310
 [1]
 J. H. Curtiss, "Riemann sums and the fundamental polynomials of Lagrange interpolation," Duke Math. J., v. 8, 1941, pp. 525532. MR 0005190 (3:115c)
 [2]
 P. J. Davis, Interpolation and Approximation, Blaisdell, New York, 1963. MR 0157156 (28:393)
 [3]
 M. Eiermann & W. Niethammer, "Interpolation methods for numerical analytic continuation," in Multivariate Approximation Theory II (W. Schempp and K. Zeller, eds.), ISNM 61, Birkhäuser, Basel, 1982. MR 719903 (85d:30050)
 [4]
 B. Fischer & L. Reichel, "A stable Richardson iteration method for complex linear systems," Numer. Math., v. 54, 1988, pp. 225242. MR 965923 (90a:65060)
 [5]
 D. Gaier, Vorlesungen über Approximation im Komplexen, Birkhäuser, Basel, 1980. MR 604011 (82i:30055)
 [6]
 W. Gautschi, "Questions of numerical condition related to polynomials," in Studies in Numerical Analysis (G. H. Golub, ed.), Math. Assoc. Amer., 1984, pp. 140177. MR 925213
 [7]
 K. O. Geddes & J. C. Mason, "Polynomial approximation by projections on the unit circle," SIAM J. Numer. Anal., v. 12, 1975, pp. 111120. MR 0364977 (51:1230)
 [8]
 P. Henrici, Essentials of Numerical Analysis, Wiley, New York, 1982. MR 655251 (83h:65002)
 [9]
 P. Henrici, Applied and Computational Complex Analysis, vol. 3, Wiley, New York, 1986. MR 822470 (87h:30002)
 [10]
 E. Hlawka, The Theory of Uniform Distribution, Academic Publishers, Berkhamsted, 1984. MR 750652 (85f:11056)
 [11]
 L. N. Trefethen (Ed.), "Numerical conformal mapping," Special Issue of J. Comput. Appl. Math., v. 16, 1986. MR 874989 (87m:30013)
 [12]
 J. L. Walsh, Interpolation and Approximation by Rational Functions in the Complex Domain, 3rd ed., Amer. Math. Soc., Providence, RI, 1960. MR 0218587 (36:1672a)
 [13]
 W. Werner, "Polynomial interpolation: Lagrange versus Newton," Math. Comp., v. 43, 1984, pp. 205217. MR 744931 (86g:65024)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65D05,
30E10,
65E05
Retrieve articles in all journals
with MSC:
65D05,
30E10,
65E05
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198909694873
PII:
S 00255718(1989)09694873
Keywords:
Polynomial interpolation,
Newton form,
Fejér points,
Chebyshev points,
van der Corput's sequence,
complex approximation,
analytic continuation
Article copyright:
© Copyright 1989
American Mathematical Society
