Effective Bounds for P-Recursive Sequences
Preprint
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.
Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- On Taylor Model Based Integration of ODEsSIAM Journal on Numerical Analysis, 2007
- Poincare Theorem for Difference EquationsMathematical Notes, 2005
- Improved validated bounds for Taylor coefficients and for Taylor remainder seriesJournal of Computational and Applied Mathematics, 2003
- Fast Evaluation of Holonomic Functions Near and in Regular SingularitiesJournal of Symbolic Computation, 2001
- Design, analysis, and implementation of a multiprecision polynomial rootfinderNumerical Algorithms, 2000
- Fast evaluation of holonomic functionsTheoretical Computer Science, 1999
- Asymptotic Behavior of a Poincaré Recurrence SystemJournal of Approximation Theory, 1997
- Automatic average-case analysis of algorithmsTheoretical Computer Science, 1991
- A holonomic systems approach to special functions identitiesJournal of Computational and Applied Mathematics, 1990
- Resurrecting the asymptotics of linear recurrencesJournal of Mathematical Analysis and Applications, 1985