Computable Function Representations Using Effective Chebyshev Polynomial

Authors: Mohammed A. Abutheraa, David Lester

Abstract:

We show that Chebyshev Polynomials are a practical representation of computable functions on the computable reals. The paper presents error estimates for common operations and demonstrates that Chebyshev Polynomial methods would be more efficient than Taylor Series methods for evaluation of transcendental functions.

Keywords: Approximation Theory, Chebyshev Polynomial, Computable Functions, Computable Real Arithmetic, Integration, Numerical Analysis.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1061168

References:

[1] Howard Anton, Calculus With Analytic Geometry, Fourth edition. Anton Textbooks, Inc., 1992.
[2] Nicolas Brisebarre, Jean-Michel Muller, and Arnaud Tisserand, Computing Machine-Efficient Polynomial Approximation. ACM Transactions on Mathematical Software, Number 2, Volume 32,pp. 236-256 ,2006.
[3] B. D-Aguanno, A. Nobile, and E. Roman, CHPACK: A Package For The Manipulation of Chebyshev Approximations. Computer Physics Communications, Number 29, pp. 361-374 ,1983.
[4] David Kincaid and Ward Cheney, Numerical Analysis: Mathematics of Scientific Computing. Brooks/Cole, 2002.
[5] Ker-I Ko, On the Computational Complexity of Best Chebyshev Approximations. Complexity, Number 2,pp. 65-120 ,1986.
[6] Ker-I Ko, Complexity Theory of Real Functions. Boston: Birkhauser, 1991.
[7] Roland E. Larson, Robert P. Hostetler, Bruch H. Edwards and David E. Heyd, Calculus with Analytic Geometry. D. C. Heath and Company, 1994.
[8] J. Mason, Chebyshev Polynomials: Theory and Applications. Kluwer Academic, 1996.
[9] John C. Mason, and David C. Handscomb, Chebyshev Polynomials. CRC Press Compan, 2003.
[10] Jean-Michel Muller, Elementary Functions: Algorithms and Implementation. Birkhauser, 1997.
[11] D. Pavlovic and M.H. Escardo, Calculus in Conductive Form. Thirteenth Annual IEEE Symposium on Logic in Computer Science, pp. 408- 417 ,1998.
[12] Marian Pour-El and J. Ian Richards, Computability in Analysis and Physics. Berlin: Springer-Verlag, 1989.
[13] Theodore J. Rivlin, Chebyshev Polynomials: from approximation theory to algebra and number theory. New York, Chichester : Wiley, 1990.