Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Rigorous uniform approximation of D-finite functions using Chebyshev expansions

Authors: Alexandre Benoit, Mioara Joldeş and Marc Mezzarobba
Journal: Math. Comp. 86 (2017), 1303-1341
MSC (2010): Primary 68W30, 33C45, 65L05, 65G20
Published electronically: October 20, 2016
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A wide range of numerical methods exists for computing polynomial approximations of solutions of ordinary differential equations based on Chebyshev series expansions or Chebyshev interpolation polynomials. We consider the application of such methods in the context of rigorous computing (where we need guarantees on the accuracy of the result), and from the complexity point of view.

It is well known that the order-$ n$ truncation of the Chebyshev expansion of a function over a given interval is a near-best uniform polynomial approximation of the function on that interval. In the case of solutions of linear differential equations with polynomial coefficients, the coefficients of the expansions obey linear recurrence relations with polynomial coefficients. Unfortunately, these recurrences do not lend themselves to a direct recursive computation of the coefficients, owing among other things to a lack of initial conditions.

We show how they can nevertheless be used, as part of a validated process, to compute good uniform approximations of D-finite functions together with rigorous error bounds, and we study the complexity of the resulting algorithms. Our approach is based on a new view of a classical numerical method going back to Clenshaw, combined with a functional enclosure method.

References [Enhancements On Off] (What's this?)

  • [1] C. Raymond Adams, On the irregular cases of the linear ordinary difference equation, Trans. Amer. Math. Soc. 30 (1928), no. 3, 507-541. MR 1501443,
  • [2] Werner Balser and Thomas Bothner, Computation of formal solutions of systems of linear difference equations, Adv. Dyn. Syst. Appl. 5 (2010), no. 1, 29-47. MR 2771315 (2011m:39002)
  • [3] A. Benoit,
    Algorithmique semi-numérique rapide des séries de Tchebychev,
    Thèse de doctorat, École polytechnique, 2012.
  • [4] Alexandre Benoit and Bruno Salvy, Chebyshev expansions for solutions of linear differential equations, ISSAC 2009--Proceedings of the 2009 International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2009, pp. 23-30. MR 2742688 (2011m:34012),
  • [5] W. G. Bickley, L. J. Comrie, J. C. P. Miller, D. H. Sadler, and A. J. Thompson, Bessel Functions. Part II. Functions of Positive Integer Order, British Association for the Advancement of Science, Mathematical Tables, vol. X, University Press, Cambridge, 1952. MR 0050973
  • [6] George D. Birkhoff, Formal theory of irregular linear difference equations, Acta Math. 54 (1930), no. 1, 205-246. MR 1555307,
  • [7] George D. Birkhoff and W. J. Trjitzinsky, Analytic theory of singular difference equations, Acta Math. 60 (1933), no. 1, 1-89. MR 1555364,
  • [8] Alin Bostan, Bruno Salvy, and Éric Schost, Power series composition and change of basis, ISSAC 2008, ACM, New York, 2008, pp. 269-276. MR 2513515 (2010h:68221),
  • [9] Richard P. Brent and Paul Zimmermann, Modern Computer Arithmetic, Cambridge Monographs on Applied and Computational Mathematics, vol. 18, Cambridge University Press, Cambridge, 2011. MR 2760886 (2012h:65315)
  • [10] Nicolas Brisebarre and Mioara Joldeş, Chebyshev interpolation polynomial-based tools for rigorous computing, ISSAC 2010--Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2010, pp. 147-154. MR 2920548,
  • [11] M. Bronstein and B. Salvy, Full partial fraction decomposition of rational functions,
    In M. Bronstein, editor, ISSAC '93, ACM, 1993, pp. 157-160.
  • [12] E. W. Cheney, Introduction to Approximation Theory, AMS Chelsea Publishing, Providence, RI, 1998. Reprint of the second (1982) edition. MR 1656150 (99f:41001)
  • [13] S. Chevillard, J. Harrison, M. Joldeş, and Ch. Lauter, Efficient and accurate computation of upper bounds of approximation errors, Theoret. Comput. Sci. 412 (2011), no. 16, 1523-1543. MR 2798728 (2012e:65051),
  • [14] S. Chevillard, M. Joldeş, and C. Lauter, Sollya: An environment for the development of numerical codes,
    In K. Fukuda, J. van der Hoeven, M. Joswig, and N. Takayama, editors, Mathematical Software - ICMS 2010, Lecture Notes in Computer Science, vol. 6327, Springer, Heidelberg, Germany, September 2010, pp. 28-31.
  • [15] C. W. Clenshaw, A note on the summation of Chebyshev series, Math. Tables Aids Comput. 9 (1955), 118-120. MR 0071856 (17,194e)
  • [16] C. W. Clenshaw, The numerical solution of linear differential equations in Chebyshev series, Proc. Cambridge Philos. Soc. 53 (1957), 134-149. MR 0082196 (18,516a)
  • [17] Tobin A. Driscoll, Folkmar Bornemann, and Lloyd N. Trefethen, The chebop system for automatic solution of differential equations, BIT 48 (2008), no. 4, 701-723. MR 2465699 (2009j:65381),
  • [18] T. H. Einwohner and R. J. Fateman, A MACSYMA package for the generation and manipulation of Chebyshev series,
    In G. H. Gonnet, editor, ISSAC '89, ACM, 1989, pp. 180-185.
  • [19] M. K. El-Daou, E. L. Ortiz, and H. Samara, A unified approach to the tau method and Chebyshev series expansion techniques, Comput. Math. Appl. 25 (1993), no. 3, 73-82. MR 1199893 (94b:65106),
  • [20] C. Epstein, W. L. Miranker, and T. J. Rivlin, Ultra-arithmetic. I. Function data types, Math. Comput. Simulation 24 (1982), no. 1, 1-18. MR 654650 (83d:65138a),
  • [21] C. Epstein, W. L. Miranker, and T. J. Rivlin, Ultra-arithmetic. II. Intervals of polynomials, Math. Comput. Simulation 24 (1982), no. 1, 19-29. MR 654651 (83d:65138b),
  • [22] L. Fox, Chebyshev methods for ordinary differential equations, Comput. J. 4 (1961/1962), 318-331. MR 0136521 (24 #B2554)
  • [23] L. Fox and I. B. Parker, Chebyshev Polynomials in Numerical Analysis, Oxford University Press, London-New York-Toronto, Ont., 1968. MR 0228149 (37 #3733)
  • [24] K. O. Geddes, Symbolic computation of recurrence equations for the Chebyshev series solution of linear ODE's,
    In Proceedings of the 1977 MACSYMA User's Conference, July 1977, pp. 405-423.
  • [25] Xavier Gourdon and Bruno Salvy, Effective asymptotics of linear recurrences with rational coefficients, Proceedings of the 5th Conference on Formal Power Series and Algebraic Combinatorics (Florence, 1993), 1996, pp. 145-163. MR 1394951 (97c:11013),
  • [26] A. O. Guelfond, Calcul des différences finies, Collection Universitaire de Mathématiques, XII. Traduit par G. Rideau, Dunod, Paris, 1963 (French). MR 0157139 (28 #376)
  • [27] G. K. Immink, Reduction to canonical forms and the Stokes phenomenon in the theory of linear difference equations, SIAM J. Math. Anal. 22 (1991), no. 1, 238-259. MR 1080156 (92c:39005),
  • [28] G. K. Immink, On the relation between global properties of linear difference and differential equations with polynomial coefficients. II, J. Differential Equations 128 (1996), no. 1, 168-205. MR 1392400 (97h:39005),
  • [29] M. Joldeş,
    Rigorous polynomial approximations and applications,
    Thèse de doctorat, École normale supérieure de Lyon, 2011.
  • [30] Edgar W. Kaucher and Willard L. Miranker, Self-validating Numerics for Function Space Problems: Computation with Guarantees for Differential and Integral Equations, Notes and Reports in Computer Science and Applied Mathematics, vol. 9, Academic Press, Inc., Orlando, FL, 1984. MR 772203 (86k:65005)
  • [31] Edgar Kaucher and Willard L. Miranker, Validating computation in a function space, Reliability in computing, Perspect. Comput., vol. 19, Academic Press, Boston, MA, 1988, pp. 403-425. MR 988472 (90c:65067)
  • [32] M. Kauers, The holonomic toolkit,
    Computer Algebra in Quantum Field Theory: Integration, Summation and Special Functions, Texts and Monographs in Symbolic Computation, 2013.
  • [33] C. Lanczos, Trigonometric interpolation of empirical and analytical functions, Journal of Mathematical Physics 17 (1938), 123-199.
  • [34] Cornelius Lanczos, Applied analysis, Prentice Hall, Inc., Englewood Cliffs, NJ, 1956. MR 0084175 (18,823c)
  • [35] S. Lewanowicz, Construction of a recurrence relation of the lowest order for coefficients of the Gegenbauer series, Zastos. Mat. 15 (1976), no. 3, 345-396 (English, with Polish summary). MR 0418488 (54 #6527)
  • [36] S. Lewanowicz, A new approach to the problem of constructing recurrence relations for the Jacobi coefficients, Zastos. Mat. 21 (1991), no. 2, 303-326. MR 1145485 (93d:33006)
  • [37] Kyoko Makino and Martin Berz, Taylor models and other validated functional inclusion methods, Int. J. Pure Appl. Math. 4 (2003), no. 4, 379-456. MR 1962787 (2004b:65061)
  • [38] Maplesoft (Waterloo Maple, Inc.),
    Maple, 1980.
  • [39] J. C. Mason and D. C. Handscomb, Chebyshev Polynomials, Chapman & Hall/CRC, Boca Raton, FL, 2003. MR 1937591 (2004h:33001)
  • [40] Richard J. Mathar, Chebyshev series expansion of inverse polynomials, J. Comput. Appl. Math. 196 (2006), no. 2, 596-607. MR 2249448 (2008a:33009),
  • [41] Herbert Meschkowski, Differenzengleichungen, Studia Mathematica, Bd. XIV, Vandenhoeck & Ruprecht, Göttingen, 1959 (German). MR 0109264 (22 #151)
  • [42] M. Mezzarobba,
    Autour de l'évaluation numérique des fonctions D-finies,
    Thèse de doctorat, École polytechnique, Nov. 2011.
  • [43] L. M. Milne-Thomson, The Calculus of Finite Differences, Macmillan and Co., Ltd., London, 1951. MR 0043339 (13,245c)
  • [44] Ramon E. Moore, Methods and Applications of Interval Analysis, SIAM Studies in Applied Mathematics, vol. 2, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1979. MR 551212 (81b:65040)
  • [45] Arnold Neumaier, Taylor forms--use and limits, Reliab. Comput. 9 (2003), no. 1, 43-79. MR 1952128 (2004j:41030),
  • [46] Sheehan Olver and Alex Townsend, A fast and well-conditioned spectral method, SIAM Rev. 55 (2013), no. 3, 462-489. MR 3089410,
  • [47] V. Y. Pan, Optimal and nearly optimal algorithms for approximating polynomial zeros, Comput. Math. Appl. 31 (1996), no. 12, 97-138. MR 1418708 (98h:65020),
  • [48] V. Y. Pan, New fast algorithms for polynomial interpolation and evaluation on the Chebyshev node set, Comput. Math. Appl. 35 (1998), no. 3, 125-129. MR 1605567,
  • [49] Stefan Paszkowski, Zastosowania numeryczne wielomianów i szeregów Czebyszewa, Państwowe Wydawnictwo Naukowe, Warsaw, 1975 (Polish). Podstawowe Algorytmy Numeryczne. [Fundamental Numerical Algorithms]. MR 0455295 (56 #13534)
  • [50] H. Poincare, Sur les Equations Lineaires aux Differentielles Ordinaires et aux Differences Finies, Amer. J. Math. 7 (1885), no. 3, 203-258 (French). MR 1505385,
  • [51] Louis B. Rall, Computational solution of nonlinear operator equations, With an appendix by Ramon E. Moore, John Wiley & Sons, Inc., New York-London-Sydney, 1969. MR 0240944 (39 #2289)
  • [52] L. Rebillard,
    Etude théorique et algorithmique des séries de Chebyshev solutions d'équations différentielles holonomes,
    Thèse de doctorat, Institut National Polytechnique de Grenoble, 1998.
  • [53] Theodore J. Rivlin, The Chebyshev polynomials, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. Pure and Applied Mathematics. MR 0450850 (56 #9142)
  • [54] B. Salvy, D-finiteness: Algorithms and applications,
    In M. Kauers, editor, ISSAC '05, ACM, 2005, pp. 2-3.
  • [55] F. W. Schäfke, Lösungstypen von Differenzengleichungen und Summengleichungen in normierten abelschen Gruppen, Math. Z. 88 (1965), 61-104 (German). MR 0176247 (31 #522)
  • [56] R. P. Stanley, Differentiably finite power series, European J. Combin. 1 (1980), no. 2, 175-188. MR 587530 (81m:05012),
  • [57] É. Tournier,
    Solutions formelles d'équations différentielles,
    Doctorat d'tat, Université scientifique, technologique et médicale de Grenoble, 1987.
  • [58] Lloyd N. Trefethen, Computing numerically with functions instead of numbers, Math. Comput. Sci. 1 (2007), no. 1, 9-19. MR 2384813 (2009i:41006),
  • [59] Lloyd N. Trefethen, Approximation theory and approximation practice, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2013. MR 3012510
  • [60] Warwick Tucker, Validated Numerics: A Short Introduction to Rigorous Computations, Princeton University Press, Princeton, NJ, 2011. MR 2807595 (2012g:65004)
  • [61] H. L. Turrittin, The formal theory of systems of irregular homogeneous linear difference and differential equations, Bol. Soc. Mat. Mexicana (2) 5 (1960), 255-264. MR 0136888 (25 #349)
  • [62] Marius van der Put and Michael F. Singer, Galois Theory of Difference Equations, Lecture Notes in Mathematics, vol. 1666, Springer-Verlag, Berlin, 1997. MR 1480919 (2000e:39008)
  • [63] Joachim von zur Gathen and Jürgen Gerhard, Modern Computer Algebra, 2nd ed., Cambridge University Press, Cambridge, 2003. MR 2001757 (2004g:68202)
  • [64] J. Wimp, On recursive computation,
    Technical Report ARL 69-0186, Aerospace Research Laboratories, 1969.
  • [65] Jet Wimp, Computation with recurrence relations, Applicable Mathematics Series, Pitman (Advanced Publishing Program), Boston, MA, 1984. MR 727118 (85f:65001)
  • [66] R. V. M. Zahar, A mathematical analysis of Miller's algorithm, Numer. Math. 27 (1976/77), no. 4, 427-447. MR 0440969 (55 #13837)
  • [67] Doron Zeilberger, A holonomic systems approach to special functions identities, J. Comput. Appl. Math. 32 (1990), no. 3, 321-368. MR 1090884 (92b:33014),

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 68W30, 33C45, 65L05, 65G20

Retrieve articles in all journals with MSC (2010): 68W30, 33C45, 65L05, 65G20

Additional Information

Alexandre Benoit
Affiliation: Éducation nationale, France

Mioara Joldeş
Affiliation: CNRS, LAAS, 7 Avenue du Colonel Roche, 31077 Toulouse, Cedex 4, France

Marc Mezzarobba
Affiliation: CNRS, UMR 7606, LIP6, F-75005, Paris, France – and – Sorbonne Universités, UPMC Univ Paris 06, UMR 7606, LIP6, F-75005, Paris, France

Keywords: Rigorous computing, computer algebra, complexity, D-finite functions, recurrence relation, Chebyshev series, Clenshaw method, Miller algorithm, asymptotics, functional enclosure
Received by editor(s): July 10, 2014
Received by editor(s) in revised form: November 7, 2015, and November 22, 2015
Published electronically: October 20, 2016
Additional Notes: This research was partly supported by the Austria Science Fund (FWF) grants P22748-N18 and Y464-N18, and previously by the MSR-Inria joint research center
This work is in the public domain. As such, it is not subject to copyright. In jurisdictions where it is not possible to consider this work as released into the public domain, the authors grant any entity the right to use this work for any purpose, without any conditions, unless such conditions are required by law.
Article copyright: © Copyright 2016 by the authors

American Mathematical Society