Truncation Bounds for Differentially Finite Series
[Bornes de troncature pour les séries différentiellement finies]
Annales Henri Lebesgue, Tome 2 (2019), pp. 99-148.

Nous décrivons un algorithme symbolique-numérique souple pour le calcul de bornes sur les restes de solutions séries d’équations différentielles linéaires à coefficients polynomiaux. Ces bornes sont destinées au calcul numérique rigoureux, et utiles notamment dans des versions rigoureuses de la méthode de Taylor d’intégration des EDO ou d’autres algorithmes apparentés. L’objectif principal de ce travail est d’obtenir des bornes fines en pratique pour un coût de calcul acceptable, y compris dans le cas d’équations d’ordre élevé à coefficients de grand degré. Notre algorithme couvre entièrement le cas des développement en séries généralisées au voisinage de points singuliers réguliers. Nous présentons une implémentation complète de la méthode en SageMath, et nous l’utilisons pour valider son bon comportement en pratique.

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.

Reçu le :
Révisé le :
Accepté le :
Première publication :
Publié le :
DOI : 10.5802/ahl.17
Classification : 33F05, 34M03, 65G20, 65L70
Mots clés : rigorous computing, symbolic-numeric algorithms, D-finite functions, error bounds
Mezzarobba, Marc 1

1 Sorbonne Université, CNRS Laboratoire d’informatique de Paris 6, LIP6 F-75005 Paris (France)
@article{AHL_2019__2__99_0,
     author = {Mezzarobba, Marc},
     title = {Truncation {Bounds} for {Differentially} {Finite} {Series}},
     journal = {Annales Henri Lebesgue},
     pages = {99--148},
     publisher = {\'ENS Rennes},
     volume = {2},
     year = {2019},
     doi = {10.5802/ahl.17},
     mrnumber = {3974489},
     zbl = {07099976},
     language = {en},
     url = {http://archive.numdam.org/articles/10.5802/ahl.17/}
}
TY  - JOUR
AU  - Mezzarobba, Marc
TI  - Truncation Bounds for Differentially Finite Series
JO  - Annales Henri Lebesgue
PY  - 2019
SP  - 99
EP  - 148
VL  - 2
PB  - ÉNS Rennes
UR  - http://archive.numdam.org/articles/10.5802/ahl.17/
DO  - 10.5802/ahl.17
LA  - en
ID  - AHL_2019__2__99_0
ER  - 
%0 Journal Article
%A Mezzarobba, Marc
%T Truncation Bounds for Differentially Finite Series
%J Annales Henri Lebesgue
%D 2019
%P 99-148
%V 2
%I ÉNS Rennes
%U http://archive.numdam.org/articles/10.5802/ahl.17/
%R 10.5802/ahl.17
%G en
%F AHL_2019__2__99_0
Mezzarobba, Marc. Truncation Bounds for Differentially Finite Series. Annales Henri Lebesgue, Tome 2 (2019), pp. 99-148. doi : 10.5802/ahl.17. http://archive.numdam.org/articles/10.5802/ahl.17/

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

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

[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), p. 14 (Reproduced in [Cau92, Section 169, p. 5-17].)

[Cau92] Cauchy, Augustin Œuvres complètes d’Augustin Cauchy, Ière série, VII, Gauthier-Villars, 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) (Lecture Notes in Pure and Applied Mathematics), Volume 125, Dekker (1990), pp. 109-232 | MR | Zbl

[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 | DOI | Numdam | MR | Zbl

[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 | DOI | MR | Zbl

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

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

[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 | DOI | MR | Zbl

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

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

[Hen86] Henrici, Peter 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] Hille, Einar Ordinary differential equations in the complex domain, Dover, 1997 (Unabridged and unaltered republication of the 1976 edition) | Zbl

[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 | DOI | MR | Zbl

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

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

[KJJ15] Kauers, Manuel; Jaroschek, Maximilian; Johansson, Fredrik 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] 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 | DOI | MR | Zbl

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

[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 | DOI | MR | Zbl

[Mez11] Mezzarobba, Marc Autour de l’évaluation numérique des fonctions D-finies, Ph. D. Thesis, École polytechnique (France) (2011) (http://tel.archives-ouvertes.fr/pastel-00663017/)

[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, Ph. D. Thesis, Stanford University (1962) (Published as Applied Mathematics and Statistics Laboratories Technical Report No. 25, http://interval.louisiana.edu/moores_early_papers/disert.pdf)

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[Neh03] Neher, Markus 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] 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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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]) | 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] Poole, E. G. C. Introduction to the theory of linear differential equations, Clarendon Press, 1936 | Zbl

[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) (Studies in Computational Mathematics), Volume 5, Elsevier (1994), pp. 173-207 | MR | Zbl

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

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

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

Cité par Sources :