ROUNDING ERROR ANALYSIS OF LINEAR RECURRENCES USING GENERATING SERIES

Marc Mezzarobba

doi:10.1553/etna_vol58s196

ROUNDING ERROR ANALYSIS OF LINEAR RECURRENCES USING GENERATING SERIES

Marc Mezzarobba

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

Résumé

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 the Bernoulli numbers and a new algorithm for evaluating differentially finite functions in interval arithmetic while avoiding interval blow-up.

langue originale	Anglais
Pages (de - à)	196-227
Nombre de pages	32
journal	Electronic Transactions on Numerical Analysis
Volume	58
Les DOIs	https://doi.org/10.1553/etna_vol58s196
état	Publié - 1 janv. 2023

Accès au document

10.1553/etna_vol58s196

Contient cette citation

@article{fb473106f5324e0b99c23a2ade8308f0,

title = "ROUNDING ERROR ANALYSIS OF LINEAR RECURRENCES USING GENERATING SERIES",

abstract = "We develop a toolbox for the error analysis of linear recurrences with constant or polynomial coefficients, based on generating series, Cauchy{\textquoteright}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 the Bernoulli numbers and a new algorithm for evaluating differentially finite functions in interval arithmetic while avoiding interval blow-up.",

keywords = "Bernoulli numbers, complex variable, differentially finite function, majorant series, rigorous computing, rounding error, vibrating string",

author = "Marc Mezzarobba",

note = "Publisher Copyright: Copyright {\textcopyright} 2023, Kent State University.",

year = "2023",

month = jan,

day = "1",

doi = "10.1553/etna\_vol58s196",

language = "English",

volume = "58",

pages = "196--227",

journal = "Electronic Transactions on Numerical Analysis",

issn = "1068-9613",

}

TY - JOUR

T1 - ROUNDING ERROR ANALYSIS OF LINEAR RECURRENCES USING GENERATING SERIES

AU - Mezzarobba, Marc

PY - 2023/1/1

Y1 - 2023/1/1

N2 - 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 the Bernoulli numbers and a new algorithm for evaluating differentially finite functions in interval arithmetic while avoiding interval blow-up.

AB - 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 the Bernoulli numbers and a new algorithm for evaluating differentially finite functions in interval arithmetic while avoiding interval blow-up.

KW - Bernoulli numbers

KW - complex variable

KW - differentially finite function

KW - majorant series

KW - rigorous computing

KW - rounding error

KW - vibrating string

U2 - 10.1553/etna_vol58s196

DO - 10.1553/etna_vol58s196

M3 - Article

AN - SCOPUS:85152592665

SN - 1068-9613

VL - 58

SP - 196

EP - 227

JO - Electronic Transactions on Numerical Analysis

JF - Electronic Transactions on Numerical Analysis

ER -

ROUNDING ERROR ANALYSIS OF LINEAR RECURRENCES USING GENERATING SERIES

Résumé

Accès au document

Empreinte digitale

Contient cette citation