Rigorous uniform approximation of D-finite functions using Chebyshev expansions
HTML articles powered by AMS MathViewer
- by Alexandre Benoit, Mioara Joldeş and Marc Mezzarobba PDF
- Math. Comp. 86 (2017), 1303-1341
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
- 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, DOI 10.1090/S0002-9947-1928-1501443-6
- 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
- A. Benoit, Algorithmique semi-numérique rapide des séries de Tchebychev, Thèse de doctorat, École polytechnique, 2012.
- 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, DOI 10.1145/1576702.1576709
- 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. 10, University Press, Cambridge, 1952. MR 0050973
- George D. Birkhoff, Formal theory of irregular linear difference equations, Acta Math. 54 (1930), no. 1, 205–246. MR 1555307, DOI 10.1007/BF02547522
- George D. Birkhoff and W. J. Trjitzinsky, Analytic theory of singular difference equations, Acta Math. 60 (1933), no. 1, 1–89. MR 1555364, DOI 10.1007/BF02398269
- 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, DOI 10.1145/1390768.1390806
- 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
- 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, DOI 10.1145/1837934.1837966
- M. Bronstein and B. Salvy, Full partial fraction decomposition of rational functions, In M. Bronstein, editor, ISSAC ’93, ACM, 1993, pp. 157–160.
- E. W. Cheney, Introduction to approximation theory, AMS Chelsea Publishing, Providence, RI, 1998. Reprint of the second (1982) edition. MR 1656150
- 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, DOI 10.1016/j.tcs.2010.11.052
- 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.
- C. W. Clenshaw, A note on the summation of Chebyshev series, Math. Tables Aids Comput. 9 (1955), 118–120. MR 71856, DOI 10.1090/S0025-5718-1955-0071856-0
- C. W. Clenshaw, The numerical solution of linear differential equations in Chebyshev series, Proc. Cambridge Philos. Soc. 53 (1957), 134–149. MR 82196, DOI 10.1017/s0305004100032072
- 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, DOI 10.1007/s10543-008-0198-4
- 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.
- 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, DOI 10.1016/0898-1221(93)90145-L
- 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, DOI 10.1016/0378-4754(82)90045-3
- 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, DOI 10.1016/0378-4754(82)90046-5
- L. Fox, Chebyshev methods for ordinary differential equations, Comput. J. 4 (1961/62), 318–331. MR 136521, DOI 10.1093/comjnl/4.4.318
- L. Fox and I. B. Parker, Chebyshev polynomials in numerical analysis, Oxford University Press, London-New York-Toronto, Ont., 1968. MR 0228149
- 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.
- 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, DOI 10.1016/0012-365X(95)00133-H
- A. O. Guelfond, Calcul des différences finies, Collection Universitaire de Mathématiques, XII, Dunod, Paris, 1963 (French). Traduit par G. Rideau. MR 0157139
- 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, DOI 10.1137/0522014
- 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, DOI 10.1006/jdeq.1996.0093
- M. Joldeş, Rigorous polynomial approximations and applications, Thèse de doctorat, École normale supérieure de Lyon, 2011.
- Edgar W. Kaucher and Willard L. Miranker, Self-validating numerics for function space problems, Notes and Reports in Computer Science and Applied Mathematics, vol. 9, Academic Press, Inc., Orlando, FL, 1984. Computation with guarantees for differential and integral equations. MR 772203
- 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
- M. Kauers, The holonomic toolkit, Computer Algebra in Quantum Field Theory: Integration, Summation and Special Functions, Texts and Monographs in Symbolic Computation, 2013.
- C. Lanczos, Trigonometric interpolation of empirical and analytical functions, Journal of Mathematical Physics 17 (1938), 123–199.
- Cornelius Lanczos, Applied analysis, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1956. MR 0084175
- 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 418488
- 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
- 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
- Maplesoft (Waterloo Maple, Inc.), Maple, 1980.
- J. C. Mason and D. C. Handscomb, Chebyshev polynomials, Chapman & Hall/CRC, Boca Raton, FL, 2003. MR 1937591
- Richard J. Mathar, Chebyshev series expansion of inverse polynomials, J. Comput. Appl. Math. 196 (2006), no. 2, 596–607. MR 2249448, DOI 10.1016/j.cam.2005.10.013
- Herbert Meschkowski, Differenzengleichungen, Studia Mathematica, Bd. XIV, Vandenhoeck & Ruprecht, Göttingen, 1959 (German). MR 0109264
- M. Mezzarobba, Autour de l’évaluation numérique des fonctions D-finies, Thèse de doctorat, École polytechnique, Nov. 2011.
- L. M. Milne-Thomson, The Calculus of Finite Differences, Macmillan & Co., Ltd., London, 1951. MR 0043339
- 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
- Arnold Neumaier, Taylor forms—use and limits, Reliab. Comput. 9 (2003), no. 1, 43–79. MR 1952128, DOI 10.1023/A:1023061927787
- Sheehan Olver and Alex Townsend, A fast and well-conditioned spectral method, SIAM Rev. 55 (2013), no. 3, 462–489. MR 3089410, DOI 10.1137/120865458
- V. Y. Pan, Optimal and nearly optimal algorithms for approximating polynomial zeros, Comput. Math. Appl. 31 (1996), no. 12, 97–138. MR 1418708, DOI 10.1016/0898-1221(96)00080-6
- 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, DOI 10.1016/S0898-1221(97)00283-6
- Stefan Paszkowski, Zastosowania numeryczne wielomianów i szeregów Czebyszewa, Podstawowe Algorytmy Numeryczne. [Fundamental Numerical Algorithms], Państwowe Wydawnictwo Naukowe, Warsaw, 1975 (Polish). MR 0455295
- 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, DOI 10.2307/2369270
- Louis B. Rall, Computational solution of nonlinear operator equations, John Wiley & Sons, Inc., New York-London-Sydney, 1969. With an appendix by Ramon E. Moore. MR 0240944
- 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.
- Theodore J. Rivlin, The Chebyshev polynomials, Pure and Applied Mathematics, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. MR 0450850
- B. Salvy, D-finiteness: Algorithms and applications, In M. Kauers, editor, ISSAC ’05, ACM, 2005, pp. 2–3.
- F. W. Schäfke, Lösungstypen von Differenzengleichungen und Summengleichungen in normierten abelschen Gruppen, Math. Z. 88 (1965), 61–104 (German). MR 176247, DOI 10.1007/BF01112693
- R. P. Stanley, Differentiably finite power series, European J. Combin. 1 (1980), no. 2, 175–188. MR 587530, DOI 10.1016/S0195-6698(80)80051-5
- É. Tournier, Solutions formelles d’équations différentielles, Doctorat d’tat, Université scientifique, technologique et médicale de Grenoble, 1987.
- Lloyd N. Trefethen, Computing numerically with functions instead of numbers, Math. Comput. Sci. 1 (2007), no. 1, 9–19. MR 2384813, DOI 10.1007/s11786-007-0001-y
- Lloyd N. Trefethen, Approximation theory and approximation practice, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2013. MR 3012510
- Warwick Tucker, Validated numerics, Princeton University Press, Princeton, NJ, 2011. A short introduction to rigorous computations. MR 2807595
- 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 136888
- 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, DOI 10.1007/BFb0096118
- Joachim von zur Gathen and Jürgen Gerhard, Modern computer algebra, 2nd ed., Cambridge University Press, Cambridge, 2003. MR 2001757
- J. Wimp, On recursive computation, Technical Report ARL 69-0186, Aerospace Research Laboratories, 1969.
- Jet Wimp, Computation with recurrence relations, Applicable Mathematics Series, Pitman (Advanced Publishing Program), Boston, MA, 1984. MR 727118
- R. V. M. Zahar, A mathematical analysis of Miller’s algorithm, Numer. Math. 27 (1976/77), no. 4, 427–447. MR 440969, DOI 10.1007/BF01399606
- Doron Zeilberger, A holonomic systems approach to special functions identities, J. Comput. Appl. Math. 32 (1990), no. 3, 321–368. MR 1090884, DOI 10.1016/0377-0427(90)90042-X
Additional Information
- Alexandre Benoit
- Affiliation: Éducation nationale, France
- Email: alexandrebenoit@yahoo.fr
- Mioara Joldeş
- Affiliation: CNRS, LAAS, 7 Avenue du Colonel Roche, 31077 Toulouse, Cedex 4, France
- MR Author ID: 931466
- Email: joldes@laas.fr
- 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
- MR Author ID: 904789
- Email: marc@mezzarobba.net
- 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. - © Copyright 2016 by the authors
- Journal: Math. Comp. 86 (2017), 1303-1341
- MSC (2010): Primary 68W30, 33C45, 65L05, 65G20
- DOI: https://doi.org/10.1090/mcom/3135
- MathSciNet review: 3614019