Evaluation of Chebyshev Interpolation and Weierstrass Approximation

Received: 24-Jul-2021 Accepted Date: Jul 29, 2021; Published: 05-Aug-2021, DOI: 10.37532/2752-8081.21.5.33

Citation: A Ramm. Evaluation of Chebyshev Interpolation and Weierstrass Approximation. J Pur Appl Math. 2021; 5(4):50:50.

This open-access article is distributed under the terms of the Creative Commons Attribution Non-Commercial License (CC BY-NC) (http://creativecommons.org/licenses/by-nc/4.0/), which permits reuse, distribution and reproduction of the article, provided that the original work is properly cited and the reuse is restricted to noncommercial purposes. For commercial reuse, contact reprints@pulsus.com

Abstract

How does one evaluate a Chebyshev interpolant? One good approach, involving O(n log n) work for a single point evaluation, is to compute Chebyshev coefficients and use the Chebyshev series. However, there is a direct method requiring just O(n) work, not based on the series expansion, that is both elegant and numerically stable. It also has the advantage of generalizing to sets of points other than Chebyshev. It is called the barycentric interpolation formula, introduced by Salzer, with an earlier closely related formula due to Marcel Riesz.

Introduction

How does one evaluate a Chebyshev interpolant? One good approach, involving O(n log n) work for a single point evaluation, is to compute Chebyshev coefficients and use the Chebyshev series. However, there is a direct method requiring just O(n) work, not based on the series expansion, that is both elegant and numerically stable. It also has the advantage of generalizing to sets of points other than Chebyshev. It is called the barycentric interpolation formula, introduced by Salzer, with an earlier closely related formula due to Marcel Riesz. The more general barycentric formula for arbitrary interpolation points, of which Salzer’s formula is an exceptionally simple special case, was developed earlier by Dupuy, with origins at least as early as Jacobi. Taylor introduced the barycentric formula for equi-spaced grid points. For a survey of barycentric formulas.The study of polynomial interpolation goes back a long time; the word “interpolation” may be due to Wallis. In particular, Newton addressed the topic and devised a method based on divided differences. Many textbooks claim that it is important to use Newton’s formulation for reasons of numerical stability, but this is not true, and we shall not discuss Newton’s approach here. Weierstrass’s theorem establishes that even extremely non-smooth functions can be approximated by polynomials, functions like x sin(x−1) or even sin(x−1) sin(1/ sin(x−1)). The latter function has an infinite number of points near which it oscillates infinitely often, as we begin to see from the plot below over the range. In this calculation Chebfun is called with a user prescribed number of interpolation points, 30,000, since the usual adaptive procedure has no chance of resolving the function to machine precision. Weierstrass’s theorem has an important generalization to complex analytic functions. Suppose a function f is defined on a compact set K in the complex plane whose complement is connected. Mergelyan’s theorem asserts that if f is continuous on K and analytic in the interior, then f can be approximated on K by polynomials. The earlier Runge’s theorem is the weaker result in which f is asumed to be analytic throughout K, not just in the interior. For all its beauty, power, and importance, the Weierstrass approximation theorem has in some respects served as an unfortunate distraction. Knowing that even troublesome functions can be approximated by polynomials, we naturally ask, how can we do it? A famous result of Faber and Bernstein asserts that there is no fixed array of grids of 1, 2, 3, interpolation points, Chebyshev or otherwise, that achieves convergence as n → ∞ for all continuous f. So it becomes tempting to look at approximation methods that go beyond interpolation, and to warn people that interpolation is dangerous, and to try to characterize exactly what minimal properties of f suf-fice to ensure that interpolation will work after all. A great deal is known about these subjects. The trouble with this line of research is that for almost all the functions encountered in practice, Chebyshev interpolation works beautifully.