Annales Henri Lebesgue

Mezzarobba, Marc

Truncation Bounds for Differentially Finite Series

Annales Henri Lebesgue, Volume 2 (2019), p. 99-148

Metadata

Keywordsrigorous computing, symbolic-numeric algorithms, D-finite functions, error bounds

Abstract

We describe a flexible symbolic-numeric algorithm for computing bounds on the tails of series solutions of linear differential equations with polynomial coefficients. Such bounds are useful in rigorous numerics, in particular in rigorous versions of the Taylor method of numerical integration of ODEs and related algorithms. The focus of this work is on obtaining tight bounds in practice at an acceptable computational cost, even for equations of high order with coefficients of large degree. Our algorithm fully covers the case of generalized series expansions at regular singular points. We provide a complete implementation in SageMath and use it to validate the method in practice.

References

[BRAB11] Barrio, Roberto; Rodríguez, Marcos; Abad, Alberto; Blesa, Fernando Breaking the limits: The Taylor series method, Appl. Math. Comput., Volume 217 (2011) no. 20, pp. 7940-7954 | Article | Zbl 1219.65064

[Bro09] Broadhurst, David Bessel moments, random walks and Calabi–Yau equations (2009) (https://www.researchgate.net/publication/267204045 )

[BS05] Bostan, Alin; Schost, Éric Polynomial evaluation and interpolation on special sets of points, J. Complexity, Volume 21 (2005) no. 4, pp. 420-446 | Article | Zbl 1101.68039

[BZ10] Brent, Richard P.; Zimmermann, Paul Modern computer arithmetic, Cambridge University Press, Cambridge Monographs on Applied and Computational Mathematics, Volume 18 (2010) | Zbl 1230.68014

[Cau42] Cauchy, Augustin Mémoire sur l’emploi du nouveau calcul, appelé calcul des limites, dans l’intégration d’un système d’équations différentielles, Comptes-rendus de l’Académie des Sciences, Volume 15 (1842), 14 pages (Reproduced in [Cau92, Section 169, p. 5-17].)

[Cau92] Cauchy, Augustin Œuvres complètes d’Augustin Cauchy, Ière série, Gauthier-Villars Volume VII (1892)

[CC90] Chudnovsky, David V.; Chudnovsky, Gregory V. Computer algebra in the service of mathematical physics and number theory, Computers in Mathematics (Stanford University, 1986), Dekker (Lecture Notes in Pure and Applied Mathematics) Volume 125 (1990), pp. 109-232 | Zbl 0712.11078

[DM90] Davenport, James H.; Mignotte, Maurice On finding the largest root of a polynomial, RAIRO, Modélisation Math. Anal. Numér., Volume 24 (1990) no. 6, pp. 693-696 | Zbl 0715.65033

[DY05] Du, Zilin; Yap, Chee Uniform complexity of approximating hypergeometric functions with absolute error, Proceedings of the 7th Asian Symposium on Computer Mathematics (ASCM 2005) (2005), pp. 246-249

[EN03] Eble, Ingo; Neher, Markus ACETAF: A software package for computing validated bounds for Taylor coefficients of analytic functions, ACM Trans. Math. Softw., Volume 29 (2003) no. 3, pp. 263-286 | Article | Zbl 1070.65540

[Fro73] Frobenius, Ferdinand Georg Über die Integration der linearen Differentialgleichungen durch Reihen, J. Reine Angew. Math., Volume 76 (1873), pp. 214-235 | Zbl 05.0180.01

[Ger04] Gerhard, Jürgen Modular algorithms in symbolic summation and symbolic integration, Springer, Lecture Notes in Computer Science, Volume 3218 (2004) | Article | Zbl 1131.68121

[Gré12] Grégoire, Thomas Certified polynomial approximations for D-finite functions, rapport de stage, École normale supérieure de Lyon (2012)

[Gut09] Guttmann, Anthony J. Lattice Green functions and Calabi–Yau differential equations, J. Phys. A, Math. Theor., Volume 42 (2009) no. 23, 232001, 6 pages | Article | Zbl 1167.82007

[Hef94] Heffter, Lothar Einleitung in die Theorie der linearen Differentialgleichungen, Teubner (1894) | Zbl 25.0512.02

[Hen77] Henrici, Peter Applied and computational complex analysis. Vol. 2: Special functions, integral transforms, asymptotics, continued fractions, John Wiley & Sons, Pure and Applied Mathematics (1977) | Zbl 0363.30001

[Hen86] Henrici, Peter Applied and computational complex analysis. Vol. 3: Discrete Fourier analysis, Cauchy integrals, construction of conformal maps, univalent functions, John Wiley & Sons, Pure and Applied Mathematics (1986) | Zbl 0578.30001

[Hil97] Hille, Einar Ordinary differential equations in the complex domain, Dover (1997) (Unabridged and unaltered republication of the 1976 edition) | Zbl 0901.34001

[HKMZ16] Hassani, Saoud; Koutschan, Christoph; Maillard, Jean-Marie; Zenine, Nadjah Lattice Green functions: the $d$ -dimensional face-centered cubic lattice, $d = 8, 9, 10, 11, 12$ , J. Phys. A, Math. Theor., Volume 49 (2016) no. 16, 164003, 30 pages | Article | Zbl 1357.35096

[Joh16] Johansson, Fredrik Computing hypergeometric functions rigorously (2016) (https://arxiv.org/abs/1606.06977 )

[Joh17] Johansson, Fredrik Arb: Efficient arbitrary-precision midpoint-radius interval arithmetic, IEEE Trans. Comput., Volume 66 (2017) no. 8, pp. 1281-1292 | Article | Zbl 1388.65037

[KJJ15] Kauers, Manuel; Jaroschek, Maximilian; Johansson, Fredrik; Gutierrez, Jaime; Schicho, Josef; Weimann, Martin Ore polynomials in Sage, Computer algebra and polynomials. Applications of algebra and number theory, Springer (Lecture Notes in Computer Science) Volume 8642 (2015), pp. 105-125 | Article | Zbl 06585202

[Kou13] Koutschan, Christoph Lattice Green functions of the higher-dimensional face-centered cubic lattices, J. Phys. A, Math. Theor., Volume 46 (2013) no. 12, 125005, 14 pages | Article | Zbl 1267.82059

[KP11] Kauers, Manuel; Paule, Peter The concrete tetrahedron. Symbolic sums, recurrence equations, generating functions, asymptotic estimates, Springer, Texts and Monographs in Symbolic Computation (2011) | Zbl 1225.00001

[Mez10] Mezzarobba, Marc NumGfun: a package for numerical and analytic computation with D-finite functions, ISSAC’10: Proceedings of the 2010 international symposium on symbolic and algebraic computation, Association for Computing Machinery (2010), pp. 139-146 | Article | Zbl 1321.65202

[Mez11] Mezzarobba, Marc Autour de l’évaluation numérique des fonctions D-finies, École polytechnique (France) (2011) (Ph. D. Thesis)

[Mez16] Mezzarobba, Marc Rigorous multiple-precision evaluation of D-finite functions in SageMath (2016) (https://arxiv.org/abs/1607.01967, Extended abstract of a talk at the 5th International Congress on Mathematical Software)

[Moo62] Moore, Ramon E. Interval arithmetic and automatic error analysis in digital computing, Stanford University (1962) (Ph. D. Thesis)

[MPF ] MPFR Team The MPFR library: algorithms and proofs (2001–) (https://www.mpfr.org/, available in the MPFR source tree)

[MS10] Mezzarobba, Marc; Salvy, Bruno Effective bounds for P-recursive sequences, J. Symb. Comput., Volume 45 (2010) no. 10, pp. 1075-1096 | Article

[Neh99] Neher, Markus An enclosure method for the solution of linear ODEs with polynomial coefficients, Numer. Funct. Anal. Optim., Volume 20 (1999), pp. 779-803 | Article | Zbl 0936.65084

[Neh01] Neher, Markus Geometric series bounds for the local errors of Taylor methods for linear $n$ -th order ODEs, Symbolic algebraic methods and verification methods, Springer (2001), pp. 183-193 | Article | Zbl 0987.65064

[Neh03] Neher, Markus Improved validated bounds for Taylor coefficients and for Taylor remainder series, J. Comput. Appl. Math., Volume 152 (2003), pp. 393-404 | Article | Zbl 1018.65030

[NJC99] Nedialkov, Nedialko S.; Jackson, Kenneth R.; Corliss, George F. Validated solutions of initial value problems for ordinary differential equations, Appl. Math. Comput., Volume 105 (1999) no. 1, pp. 21-68 | Article | Zbl 0934.65073

[NJN07] Neher, Markus; Jackson, Kenneth R.; Nedialkov, Nedialko S. On Taylor model based integration of ODEs, SIAM J. Numer. Anal., Volume 45 (2007) no. 1, pp. 236-262 | Article | Zbl 1141.65056

[OLBC10a] Olver, Frank W.; Lozier, Daniel W.; Boisvert, Ronald F.; Clark, Charles W. Digital Library of Mathematical Functions (2010) (http://dlmf.nist.gov/, Companion to the NIST Handbook of Mathematical Functions [OLBC10b])

[OLBC10b] Olver, Frank W. J.; Lozier, Daniel W.; Boisvert, Ronald F.; Clark, Charles W. NIST Handbook of Mathematical Functions, Cambridge University Press (2010) | Zbl 1198.00002

[Poo36] Poole, E. G. C. Introduction to the theory of linear differential equations, Clarendon Press (1936) | Zbl 62.1277.01

[Rih94] Rihm, Robert Interval methods for initial value problems in ODEs, Topics in validated computations. Proceedings of the IMACS-GAMM international workshop (University of Oldenburg, 1993), Elsevier (Studies in Computational Mathematics) Volume 5 (1994), pp. 173-207 | Zbl 0815.65095

[Sta99] Stanley, Richard P. Enumerative combinatorics. Vol. 2, Cambridge University Press, Cambridge Studies in Advanced Mathematics, Volume 62 (1999) | Zbl 0928.05001

[vdH99] van der Hoeven, Joris Fast evaluation of holonomic functions, Theor. Comput. Sci., Volume 210 (1999) no. 1, pp. 199-216 | Article | Zbl 0912.68081

[vdH01] van der Hoeven, Joris Fast evaluation of holonomic functions near and in regular singularities, J. Symb. Comput., Volume 31 (2001) no. 6, pp. 717-743 | Article | Zbl 0982.65024

[vdH03] van der Hoeven, Joris Majorants for formal power series (2003) (http://www.texmacs.org/joris/maj/maj-abs.html )

[vdH07] van der Hoeven, Joris Efficient accelero-summation of holonomic functions, J. Symb. Comput., Volume 42 (2007) no. 4, pp. 389-428 | Article | Zbl 1125.34072

[WWS + 06] Warne, Paul G.; Warne, D. A. P.; Sochacki, James S.; Parker, G. Edgar; Carothers, David C. Explicit a-priori error bounds and adaptive error control for approximation of nonlinear initial value differential systems, Comput. Math. Appl., Volume 52 (2006) no. 12, pp. 1695-1710 | Article | Zbl 1134.65354

[ZHM15] Zenine, Nadjah; Hassani, Saoud; Maillard, Jean-Marie Lattice Green functions: the seven-dimensional face-centred cubic lattice, J. Phys. A, Math. Theor., Volume 48 (2015) no. 3, 035205, 19 pages | Article