Rigorous uniform approximation of D-finite functions using Chebyshev expansions

Benoit, Alexandre; Joldeş, Mioara; Mezzarobba, Marc

doi:10.1090/mcom/3135

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