Metadata
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] Breaking the limits: The Taylor series method, Appl. Math. Comput., Volume 217 (2011) no. 20, pp. 7940-7954 | DOI | MR | Zbl
[Bro09] Bessel moments, random walks and Calabi–Yau equations (2009) (https://www.researchgate.net/publication/267204045)
[BS05] Polynomial evaluation and interpolation on special sets of points, J. Complexity, Volume 21 (2005) no. 4, pp. 420-446 | DOI | MR | Zbl
[BZ10] Modern computer arithmetic, Cambridge Monographs on Applied and Computational Mathematics, 18, Cambridge University Press, 2010 | Zbl
[Cau42] 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), p. 14 (Reproduced in [Cau92, Section 169, p. 5-17].)
[Cau92] Œuvres complètes d’Augustin Cauchy, Ière série, VII, Gauthier-Villars, 1892
[CC90] Computer algebra in the service of mathematical physics and number theory, Computers in Mathematics (Stanford University, 1986) (Lecture Notes in Pure and Applied Mathematics), Volume 125 (1990), pp. 109-232 | MR | Zbl
[DM90] On finding the largest root of a polynomial, RAIRO, Modélisation Math. Anal. Numér., Volume 24 (1990) no. 6, pp. 693-696 | DOI | Numdam | MR | Zbl
[DY05] 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] 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 | DOI | MR | Zbl
[Fro73] Über die Integration der linearen Differentialgleichungen durch Reihen, J. Reine Angew. Math., Volume 76 (1873), pp. 214-235 | Zbl
[Ger04] Modular algorithms in symbolic summation and symbolic integration, Lecture Notes in Computer Science, 3218, Springer, 2004 | DOI | Zbl
[Gré12] Certified polynomial approximations for D-finite functions, rapport de stage, École normale supérieure de Lyon, 2012
[Gut09] Lattice Green functions and Calabi–Yau differential equations, J. Phys. A, Math. Theor., Volume 42 (2009) no. 23, 232001, 6 pages | DOI | MR | Zbl
[Hef94] Einleitung in die Theorie der linearen Differentialgleichungen, Teubner, 1894 | Zbl
[Hen77] Applied and computational complex analysis. Vol. 2: Special functions, integral transforms, asymptotics, continued fractions, Pure and Applied Mathematics, John Wiley & Sons, 1977 | Zbl
[Hen86] Applied and computational complex analysis. Vol. 3: Discrete Fourier analysis, Cauchy integrals, construction of conformal maps, univalent functions, Pure and Applied Mathematics, John Wiley & Sons, 1986 | Zbl
[Hil97] Ordinary differential equations in the complex domain, Dover, 1997 (Unabridged and unaltered republication of the 1976 edition) | Zbl
[HKMZ16] Lattice Green functions: the -dimensional face-centered cubic lattice, , J. Phys. A, Math. Theor., Volume 49 (2016) no. 16, 164003, 30 pages | DOI | MR | Zbl
[Joh16] Computing hypergeometric functions rigorously (2016) (https://arxiv.org/abs/1606.06977) | Zbl
[Joh17] Arb: Efficient arbitrary-precision midpoint-radius interval arithmetic, IEEE Trans. Comput., Volume 66 (2017) no. 8, pp. 1281-1292 | DOI | MR | Zbl
[KJJ15] Ore polynomials in Sage, Computer algebra and polynomials. Applications of algebra and number theory (Gutierrez, Jaime; Schicho, Josef; Weimann, Martin, eds.) (Lecture Notes in Computer Science), Volume 8642, Springer, 2015, pp. 105-125 | DOI | Zbl
[Kou13] Lattice Green functions of the higher-dimensional face-centered cubic lattices, J. Phys. A, Math. Theor., Volume 46 (2013) no. 12, 125005, 14 pages | DOI | MR | Zbl
[KP11] The concrete tetrahedron. Symbolic sums, recurrence equations, generating functions, asymptotic estimates, Texts and Monographs in Symbolic Computation, Springer, 2011 | Zbl
[Mez10] 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 (2010), pp. 139-146 | DOI | MR | Zbl
[Mez11] Autour de l’évaluation numérique des fonctions D-finies (2011) (http://tel.archives-ouvertes.fr/pastel-00663017/) (Ph. D. Thesis)
[Mez16] 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] Interval arithmetic and automatic error analysis in digital computing (1962) (Published as Applied Mathematics and Statistics Laboratories Technical Report No. 25, http://interval.louisiana.edu/moores_early_papers/disert.pdf) (Ph. D. Thesis)
[MPF ] The MPFR library: algorithms and proofs, 2001– (https://www.mpfr.org/, available in the MPFR source tree)
[MS10] Effective bounds for P-recursive sequences, J. Symb. Comput., Volume 45 (2010) no. 10, pp. 1075-1096 | DOI | MR | Zbl
[Neh99] An enclosure method for the solution of linear ODEs with polynomial coefficients, Numer. Funct. Anal. Optim., Volume 20 (1999), pp. 779-803 | DOI | MR | Zbl
[Neh01] Geometric series bounds for the local errors of Taylor methods for linear -th order ODEs, Symbolic algebraic methods and verification methods, Springer, 2001, pp. 183-193 | DOI | MR | Zbl
[Neh03] Improved validated bounds for Taylor coefficients and for Taylor remainder series, J. Comput. Appl. Math., Volume 152 (2003), pp. 393-404 | DOI | MR | Zbl
[NJC99] Validated solutions of initial value problems for ordinary differential equations, Appl. Math. Comput., Volume 105 (1999) no. 1, pp. 21-68 | DOI | MR | Zbl
[NJN07] On Taylor model based integration of ODEs, SIAM J. Numer. Anal., Volume 45 (2007) no. 1, pp. 236-262 | DOI | MR | Zbl
[OLBC10a] Digital Library of Mathematical Functions, 2010 (http://dlmf.nist.gov/, Companion to the NIST Handbook of Mathematical Functions [OLBC10b]) | Zbl
[OLBC10b] NIST Handbook of Mathematical Functions (Olver, Frank W. J.; Lozier, Daniel W.; Boisvert, Ronald F.; Clark, Charles W., eds.), Cambridge University Press, 2010 | Zbl
[Poo36] Introduction to the theory of linear differential equations, Clarendon Press, 1936 | Zbl
[Rih94] Interval methods for initial value problems in ODEs, Topics in validated computations. Proceedings of the IMACS-GAMM international workshop (University of Oldenburg, 1993) (Studies in Computational Mathematics), Volume 5 (1994), pp. 173-207 | MR | Zbl
[Sta99] Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, 62, Cambridge University Press, 1999 | MR | Zbl
[vdH99] Fast evaluation of holonomic functions, Theor. Comput. Sci., Volume 210 (1999) no. 1, pp. 199-216 | DOI | MR | Zbl
[vdH01] Fast evaluation of holonomic functions near and in regular singularities, J. Symb. Comput., Volume 31 (2001) no. 6, pp. 717-743 | DOI | MR | Zbl
[vdH03] Majorants for formal power series, 2003 (http://www.texmacs.org/joris/maj/maj-abs.html)
[vdH07] Efficient accelero-summation of holonomic functions, J. Symb. Comput., Volume 42 (2007) no. 4, pp. 389-428 | DOI | MR | Zbl
[WWS + 06] 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 | DOI | MR | Zbl
[ZHM15] Lattice Green functions: the seven-dimensional face-centred cubic lattice, J. Phys. A, Math. Theor., Volume 48 (2015) no. 3, 035205, 19 pages | DOI | MR | Zbl