×

zbMATH — the first resource for mathematics

Effective bounds for P-recursive sequences. (English) Zbl 1201.65219
Authors’ abstract: We describe an algorithm that takes as input a complex sequence \((u_n)\) given by a linear recurrence relation with polynomial coefficients along with initial values, and outputs a simple explicit upper bound \((v_n)\) such that \(|u_n|\leq v_n\) for all \(n\). Generically, the bound is tight, in the sense that its asymptotic behaviour matches that of \(u_n\). We discuss applications to the evaluation of power series with guaranteed precision.

MSC:
65Q30 Numerical aspects of recurrence relations
65B10 Numerical summation of series
Software:
ACETAF; na20; Asyrec; gfun
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abramowitz, M.; Stegun, I.A., Handbook of mathematical functions, (1972), Dover Publications New York · Zbl 0515.33001
[2] Apéry, R., Irrationalité de \(\zeta(2)\) et \(\zeta(3)\), Astérisque, 61, 11-13, (1979) · Zbl 0401.10049
[3] Bini, D.; Fiorentino, G., Design, analysis, and implementation of a multiprecision polynomial rootfinder, Numerical algorithms, 23, 2, 127-173, (2000) · Zbl 1018.65061
[4] Bronstein, M., Symbolic integration. I, () · Zbl 0880.12005
[5] Buslaev, V.I.; Buslaeva, S.F., Poincare theorem for difference equations, Mathematical notes, 78, 5-6, 877-882, (2005), (translated from Matematicheskie Zametki 78 (6) (2005) pp. 943—947) · Zbl 1108.39015
[6] Chudnovsky, D.V.; Chudnovsky, G.V., Computer assisted number theory with applications, (), 1-68 · Zbl 0617.10001
[7] Chudnovsky, D.V.; Chudnovsky, G.V., Approximations and complex multiplication according to Ramanujan, (), 375-472 · Zbl 0647.10002
[8] Du, Z.; Yap, C., Uniform complexity approximating hypergeometric functions with absolute error, (), 246-249
[9] Eble, I.; Neher, M., ACETAF: A software package for computing validated bounds for Taylor coefficients of analytic functions, ACM transactions on mathematical software, 29, 3, 263-286, (2003) · Zbl 1070.65540
[10] Flajolet, P.; Salvy, B.; Zimmermann, P., Automatic average-case analysis of algorithms, Theoretical computer science, series A, 79, 1, 37-109, (1991) · Zbl 0768.68041
[11] Flajolet, P.; Sedgewick, R., Analytic combinatorics, (2009), Cambridge University Press, URL: http://algo.inria.fr/flajolet/Publications/book.pdf · Zbl 1165.05001
[12] Gourdon, X.; Salvy, B., Effective asymptotics of linear recurrences with rational coefficients, Discrete mathematics, 153, 1-3, 145-163, (1996) · Zbl 0852.68075
[13] Graham, R.L.; Knuth, D.E.; Patashnik, O., Concrete mathematics, (1989), Addison-Wesley · Zbl 0668.00003
[14] Guelfond, A.O., 1963. Calcul des différences finies. Collection Universitaire de Mathématiques, XII. Dunod, Paris (translated from the Russian). · Zbl 0108.27503
[15] Hoefkens, J., 2001. Rigorous numerical analysis with high-order Taylor models. Ph.D. Thesis, Michigan State University.
[16] Ince, E.L., Ordinary differential equations, (1956), Dover New York · Zbl 0063.02971
[17] Karatsuba, E.A., 1999. Fast evaluation of hypergeometric functions by FEE. In: Papamichael, N., Ruscheweyh, S., Saff, E.B. (Eds.), Proceedings of the 3rd CMFT Conference on Computational Methods and Function Theory. pp. 303-314. · Zbl 1017.65014
[18] Knuth, D.E., ()
[19] Kooman, R.; Tijdeman, R., Convergence properties of linear recurrence sequences, Nieuw archief voor wiskunde, ser., 4, 4, 13-25, (1990) · Zbl 0713.11010
[20] Kreuser, P., 1914. Über das Verhalten der Integrale homogener linearer Differenzengleichungen im Unendlichen. Ph.D. thesis, Universität Tübingen, Borna-Leipzig. · JFM 45.0503.01
[21] Lipshitz, L., \(D\)-finite power series, Journal of algebra, 122, 2, 353-373, (1989) · Zbl 0695.12018
[22] Makino, K.; Berz, M., Taylor models and other validated functional inclusion methods, International journal of pure and applied mathematics, 4, 4, 379-456, (2003), URL: http://bt.pa.msu.edu/pub/papers/TMIJPAM03/TMIJPAM03.pdf · Zbl 1022.65051
[23] Malgrange, B., Sur LES points singuliers des équations différentielles, L’enseignement mathématique, XX, 1-2, 147-176, (1974) · Zbl 0299.34011
[24] Meschkowski, H., Differenzengleichungen, (1959), Vandenhoeck & Ruprecht · Zbl 0084.29202
[25] Mezzino, M.; Pinsky, M., Leibniz’s formula, Cauchy majorants, and linear differential equations, Mathematics magazine, 71, 5, 360-368, (1998) · Zbl 1016.34009
[26] Neher, M., Improved validated bounds for Taylor coefficients and for Taylor remainder series, Journal of computational and applied mathematics, 152, 393-404, (2003), URL: http://iamlasun8.mathematik.uni-karlsruhe.de/ ae16/preprnts/neher_2003_improved_taylor_JCAM152.pdf · Zbl 1018.65030
[27] Neher, M.; Jackson, K.R.; Nedialkov, N.S., On Taylor model based integration of odes, SIAM journal on numerical analysis, 45, 1, 236-262, (2007), URL: http://www.cs.toronto.edu/NA/reports.html#TM_ODE_2005 · Zbl 1141.65056
[28] Neumaier, A., Taylor forms — use and limits, Reliable computing, 9, 1, 43-79, (2003) · Zbl 1071.65070
[29] Odlyzko, A.M., Asymptotic enumeration methods, (), 1063-1229, URL: http://www.dtc.umn.edu/ odlyzko/doc/asymptotic.enum.pdf · Zbl 0845.05005
[30] Perron, O., Über die poincarésche lineare differenzengleichung, Journal für die reine und angewandte Mathematik, 137, 6-64, (1909) · JFM 40.0385.02
[31] Perron, O., Über ein satz des herrn Poincaré, Journal Für die reine und angewandte Mathematik, 136, 17-37, (1909) · JFM 40.0385.01
[32] Perron, O., Über lineare differenzengleichungen, Acta Mathematica, 34, 109-137, (1910) · JFM 41.0368.01
[33] Perron, O., Über summengleichungen und poincarésche differenzengliechungen, Mathematische annalen, 84, 1-15, (1921) · JFM 48.0479.01
[34] Pituk, M., Asymptotic behavior of a Poincaré recurrence system, Journal of approximation theory, 91, 2, 226-243, (1997) · Zbl 0892.39008
[35] Poincaré, H., Sur LES équations linéaires aux différentielles ordinaires et aux différences finies, American journal of mathematics, 7, 3, 203-258, (1885) · JFM 17.0290.01
[36] Rihm, R., Interval methods for initial value problems in odes, (), 173-207 · Zbl 0815.65095
[37] Salvy, B.; Zimmermann, P., Gfun: A Maple package for the manipulation of generating and holonomic functions in one variable, ACM transactions on mathematical software, 20, 2, 163-177, (1994) · Zbl 0888.65010
[38] Schäfke, F. W., Lösungstypen von differenzengleichungen und summengleichungen in normierten abelschen gruppen, Mathematische zeitschrift, 88, 1, 61-104, (1965) · Zbl 0134.06401
[39] Schönhage, A., 1982. The fundamental theorem of algebra in terms of computational complexity. Tech. rep., Mathematisches Institut der Universität Tübingen.
[40] Stanley, R.P., Differentiably finite power series, European journal of combinatorics, 1, 2, 175-188, (1980) · Zbl 0445.05012
[41] Stanley, R.P., Enumerative combinatorics, vol. 2, (1999), Cambridge University Press · Zbl 0928.05001
[42] Tournier, E., 1987. Solutions formelles d’équations différentielles. Doctorat d’État, Université scientifique, technologique et médicale de Grenoble. URL: http://tel.archives-ouvertes.fr/tel-00323706/fr/.
[43] van der Hoeven, J., Fast evaluation of holonomic functions, Theoretical computer science, 210, 1, 199-216, (1999), URL: http://www.math.u-psud.fr/ vdhoeven/Publs/1997/TCS.ps.gz · Zbl 0912.68081
[44] van der Hoeven, J., Fast evaluation of holonomic functions near and in regular singularities, Journal of symbolic computation, 31, 6, 717-743, (2001), URL: http://www.math.u-psud.fr/ vdhoeven/Publs/2000/singhol.ps.gz · Zbl 0982.65024
[45] van der Hoeven, J., 2003. Majorants for formal power series. Tech. Rep. 2003-15, Université Paris-Sud, Orsay, France. URL: http://www.math.u-psud.fr/ vdhoeven/Publs/2003/maj.ps.gz.
[46] van der Hoeven, J., On effective analytic continuation, Mathematics in computer science, 1, 1, 111-175, (2007) · Zbl 1154.68574
[47] Wimp, J.; Zeilberger, D., Resurrecting the asymptotics of linear recurrences, Journal of mathematical analysis and applications, 111, 162-176, (1985) · Zbl 0579.05007
[48] Zeilberger, D., A holonomic systems approach to special functions identities, Journal of computational and applied mathematics, 32, 3, 321-368, (1990) · Zbl 0738.33001
[49] Zeilberger, D., 2008. Asyrec: A Maple package for computing the asymptotics of solutions of linear recurrence equations with polynomial coefficients. URL: http://www.math.rutgers.edu/ zeilberg/mamarim/mamarimhtml/asy.html.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.