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 | Article | MR 2802205 | Zbl 1219.65064
[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 | Article | MR 2152715 | Zbl 1101.68039
[BZ10] Modern computer arithmetic, Cambridge Monographs on Applied and Computational Mathematics, Volume 18, Cambridge University Press, 2010 | Zbl 1230.68014
[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), 14 pages (Reproduced in [Cau92, Section 169, p. 5-17].)
[Cau92] Œuvres complètes d’Augustin Cauchy, Ière série Volume 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 1068536 | Zbl 0712.11078
[DM90] On finding the largest root of a polynomial, RAIRO, Modélisation Math. Anal. Numér., Volume 24 (1990) no. 6, pp. 693-696 | Article | Numdam | MR 1080714 | Zbl 0715.65033
[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 | Article | MR 2002732 | Zbl 1070.65540
[Fro73] Über die Integration der linearen Differentialgleichungen durch Reihen, J. Reine Angew. Math., Volume 76 (1873), pp. 214-235 | Zbl 05.0180.01
[Ger04] Modular algorithms in symbolic summation and symbolic integration, Lecture Notes in Computer Science, Volume 3218, Springer, 2004 | Article | Zbl 1131.68121
[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, 6 pages | Article | MR 2515546 | Zbl 1167.82007
[Hef94] Einleitung in die Theorie der linearen Differentialgleichungen, Teubner, 1894 | Zbl 25.0512.02
[Hen77] Applied and computational complex analysis. Vol. 2: Special functions, integral transforms, asymptotics, continued fractions, Pure and Applied Mathematics, John Wiley & Sons, 1977 | Zbl 0363.30001
[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 0578.30001
[Hil97] Ordinary differential equations in the complex domain, Dover, 1997 (Unabridged and unaltered republication of the 1976 edition) | Zbl 0901.34001
[HKMZ16] Lattice Green functions: the -dimensional face-centered cubic lattice, , J. Phys. A, Math. Theor., Volume 49 (2016) no. 16, 30 pages | Article | MR 3491321 | Zbl 1357.35096
[Joh16] Computing hypergeometric functions rigorously (2016) (https://arxiv.org/abs/1606.06977) | Zbl 07193379
[Joh17] Arb: Efficient arbitrary-precision midpoint-radius interval arithmetic, IEEE Trans. Comput., Volume 66 (2017) no. 8, pp. 1281-1292 | Article | MR 3681746 | Zbl 1388.65037
[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 | Article | Zbl 06585202
[Kou13] Lattice Green functions of the higher-dimensional face-centered cubic lattices, J. Phys. A, Math. Theor., Volume 46 (2013) no. 12, 14 pages | Article | MR 3035343 | Zbl 1267.82059
[KP11] The concrete tetrahedron. Symbolic sums, recurrence equations, generating functions, asymptotic estimates, Texts and Monographs in Symbolic Computation, Springer, 2011 | Zbl 1225.00001
[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 | Article | MR 2920547 | Zbl 1321.65202
[Mez11] Autour de l’évaluation numérique des fonctions D-finies (2011) (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) (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 | Article | MR 2679389 | Zbl 1201.65219
[Neh99] An enclosure method for the solution of linear ODEs with polynomial coefficients, Numer. Funct. Anal. Optim., Volume 20 (1999), pp. 779-803 | Article | MR 1714890 | Zbl 0936.65084
[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 | Article | MR 1832424 | Zbl 0987.65064
[Neh03] Improved validated bounds for Taylor coefficients and for Taylor remainder series, J. Comput. Appl. Math., Volume 152 (2003), pp. 393-404 | Article | MR 1991304 | Zbl 1018.65030
[NJC99] Validated solutions of initial value problems for ordinary differential equations, Appl. Math. Comput., Volume 105 (1999) no. 1, pp. 21-68 | Article | MR 1706055 | Zbl 0934.65073
[NJN07] On Taylor model based integration of ODEs, SIAM J. Numer. Anal., Volume 45 (2007) no. 1, pp. 236-262 | Article | MR 2285853 | Zbl 1141.65056
[OLBC10a] Digital Library of Mathematical Functions, 2010 (http://dlmf.nist.gov/, Companion to the NIST Handbook of Mathematical Functions [OLBC10b]) | Zbl 1198.00002
[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 1198.00002
[Poo36] Introduction to the theory of linear differential equations, Clarendon Press, 1936 | Zbl 62.1277.01
[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 1318955 | Zbl 0815.65095
[Sta99] Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, Volume 62, Cambridge University Press, 1999 | MR 1676282 | Zbl 0928.05001
[vdH99] Fast evaluation of holonomic functions, Theor. Comput. Sci., Volume 210 (1999) no. 1, pp. 199-216 | Article | MR 1650888 | Zbl 0912.68081
[vdH01] Fast evaluation of holonomic functions near and in regular singularities, J. Symb. Comput., Volume 31 (2001) no. 6, pp. 717-743 | Article | MR 1834006 | Zbl 0982.65024
[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 | Article | MR 2317557 | Zbl 1125.34072
[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 | Article | MR 2293971 | Zbl 1134.65354
[ZHM15] Lattice Green functions: the seven-dimensional face-centred cubic lattice, J. Phys. A, Math. Theor., Volume 48 (2015) no. 3, 19 pages | Article | MR 3299625 | Zbl 1311.34057