Newton interpolation in Fejér and Chebyshev points
Authors: Bernd Fischer and Lothar Reichel
Journal: Math. Comp. 53 (1989), 265-278
MSC: Primary 65D05; Secondary 30E10, 65E05
MathSciNet review: 969487
Full-text PDF Free Access
Abstract: Let $\Gamma$ be a Jordan curve in the complex plane, and let $\Omega$ be the compact set bounded by $\Gamma$. Let f denote a function analytic on $\Omega$. We consider the approximation of f on $\Omega$ by a polynomial p of degree less than n that interpolates f in n points on $\Gamma$. 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 $\Omega$ as n increases. We show that p is fairly insensitive to perturbations of f if $\Gamma$ is smooth and is scaled to have capacity one. If $\Gamma$ 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 $\Gamma$.
- J. H. Curtiss, Riemann sums and the fundamental polynomials of Lagrange interpolation, Duke Math. J. 8 (1941), 525–532. MR 5190
- Philip J. Davis, Interpolation and approximation, Blaisdell Publishing Co. Ginn and Co. New York-Toronto-London, 1963. MR 0157156
- 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
- Bernd Fischer and Lothar Reichel, A stable Richardson iteration method for complex linear systems, Numer. Math. 54 (1988), no. 2, 225–242. MR 965923, DOI https://doi.org/10.1007/BF01396976
- Dieter Gaier, Vorlesungen über Approximation im Komplexen, Birkhäuser Verlag, Basel-Boston, Mass., 1980 (German). MR 604011
- 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
- K. O. Geddes and J. C. Mason, Polynomial approximation by projections on the unit circle, SIAM J. Numer. Anal. 12 (1975), 111–120. MR 364977, DOI https://doi.org/10.1137/0712011
- Peter Henrici, Essentials of numerical analysis with pocket calculator demonstrations, John Wiley & Sons, Inc., New York, 1982. MR 655251
- 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 Wiley-Interscience Publication. MR 822470
- 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
- Lloyd N. Trefethen (ed.), Numerical conformal mapping, North-Holland Publishing Co., Amsterdam, 1986. Reprint of J. Comput. Appl. Math. 14 (1986), no. 1-2. MR 874989
- J. L. Walsh, Interpolation and approximation by rational functions in the complex domain, 3rd ed., American Mathematical Society Colloquium Publications, Vol. XX, American Mathematical Society, Providence, R.I., 1960. MR 0218587
- Wilhelm Werner, Polynomial interpolation: Lagrange versus Newton, Math. Comp. 43 (1984), no. 167, 205–217. MR 744931, DOI https://doi.org/10.1090/S0025-5718-1984-0744931-0
J. H. Curtiss, "Riemann sums and the fundamental polynomials of Lagrange interpolation," Duke Math. J., v. 8, 1941, pp. 525-532.
P. J. Davis, Interpolation and Approximation, Blaisdell, New York, 1963.
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.
B. Fischer & L. Reichel, "A stable Richardson iteration method for complex linear systems," Numer. Math., v. 54, 1988, pp. 225-242.
D. Gaier, Vorlesungen über Approximation im Komplexen, Birkhäuser, Basel, 1980.
W. Gautschi, "Questions of numerical condition related to polynomials," in Studies in Numerical Analysis (G. H. Golub, ed.), Math. Assoc. Amer., 1984, pp. 140-177.
K. O. Geddes & J. C. Mason, "Polynomial approximation by projections on the unit circle," SIAM J. Numer. Anal., v. 12, 1975, pp. 111-120.
P. Henrici, Essentials of Numerical Analysis, Wiley, New York, 1982.
P. Henrici, Applied and Computational Complex Analysis, vol. 3, Wiley, New York, 1986.
E. Hlawka, The Theory of Uniform Distribution, Academic Publishers, Berkhamsted, 1984.
L. N. Trefethen (Ed.), "Numerical conformal mapping," Special Issue of J. Comput. Appl. Math., v. 16, 1986.
J. L. Walsh, Interpolation and Approximation by Rational Functions in the Complex Domain, 3rd ed., Amer. Math. Soc., Providence, RI, 1960.
W. Werner, "Polynomial interpolation: Lagrange versus Newton," Math. Comp., v. 43, 1984, pp. 205-217.
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