Rounding error analysis of linear recurrences using generating series
From MaRDI portal
Abstract: We develop a toolbox for the error analysis of linear recurrences with constant or polynomial coefficients, based on generating series, Cauchy's method of majorants, and simple results from analytic combinatorics. We illustrate the power of the approach by several nontrivial application examples. Among these examples are a new worst-case analysis of an algorithm for computing Bernoulli numbers, and a new algorithm for evaluating differentially finite functions in interval arithmetic while avoiding interval blow-up.
Recommendations
- Error Bounds for Linear Recurrence Relations
- Rounding error analysis for forward continued fraction algorithms
- scientific article; zbMATH DE number 1543291
- scientific article; zbMATH DE number 4011779
- The effect of rounding errors on a certain class of iterative methods
- On the numerical evaluation of linear recurrences
- scientific article; zbMATH DE number 440777
- scientific article; zbMATH DE number 4039122
- Rounding Error Analysis of Interval Algorithms
- scientific article; zbMATH DE number 1225892
Cites work
- A New Approach to Probabilistic Rounding Error Analysis
- Accuracy and Stability of Numerical Algorithms
- Analytic combinatorics
- Effective bounds for P-recursive sequences
- Error analysis of an algorithm for summing certain finite series
- Error Analysis of Miller's Recurrence Algorithm
- Evaluation of Chebyshev polynomials by a three-term recurrence in floating-point arithmetic
- Explicit a-priori error bounds and adaptive error control for approximation of nonlinear initial value differential systems
- Fast and Rigorous Arbitrary-Precision Computation of Gauss--Legendre Quadrature Nodes and Weights
- Fast computation of Bernoulli, tangent and secant numbers
- Floats and Ropes: A Case Study for Formal Numerical Program Verification
- Forward computation in second order difference equations†
- scientific article; zbMATH DE number 3889483 (Why is no real title available?)
- scientific article; zbMATH DE number 3153275 (Why is no real title available?)
- scientific article; zbMATH DE number 3864449 (Why is no real title available?)
- scientific article; zbMATH DE number 3534862 (Why is no real title available?)
- scientific article; zbMATH DE number 1024452 (Why is no real title available?)
- scientific article; zbMATH DE number 3182507 (Why is no real title available?)
- scientific article; zbMATH DE number 3110365 (Why is no real title available?)
- John von Neumann's Analysis of Gaussian Elimination and the Origins of Modern Numerical Analysis
- Linear differential equations as a data structure
- Modern computer arithmetic
- Numerical inverting of matrices of high order
- On location and approximation of clusters of zeros of analytic functions
- On the numerical evaluation of linear recurrences
- Ore polynomials in Sage
- Relative error propagation in the recursive solution of linear recurrence relations
- Rounding error bounds for the Clenshaw and Forsythe algorithms for the evaluation of orthogonal polynomial series
- ROUNDING-OFF ERRORS IN MATRIX PROCESSES
- Tensor product B-spline mesh generation for accurate surface visualizations in the NIST digital library of mathematical functions
- The holonomic toolkit
- Truncation bounds for differentially finite series
- Trusting computations: a mechanized proof from partial differential equations to actual program
- Unrestricted algorithms for elementary and special functions
- Wave equation numerical resolution: a comprehensive mechanized proof of a C program
Cited in
(8)- On recurrences converging to the wrong limit in finite precision and some new examples
- Rounding Error Analysis of Interval Algorithms
- scientific article; zbMATH DE number 5778212 (Why is no real title available?)
- scientific article; zbMATH DE number 62660 (Why is no real title available?)
- scientific article; zbMATH DE number 1225892 (Why is no real title available?)
- Floating-point arithmetic
- Effective bounds for P-recursive sequences
- Bessel's labyrinth -- rounding errors are not necessarily small
This page was built for publication: Rounding error analysis of linear recurrences using generating series
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6163326)
