A unified rounding error bound for polynomial evaluation

DOI10.1023/A:1024203520270MaRDI QIDQ1397303zbMATH OpenFDO

Authors D. Massart

Publication date 27 July 2003

Published in Advances in Computational Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/A:1024203520270

zbMATH Keywords

condition numberfirst-order linear matrix recurrence relationHorner's algorithmorthogonal baseorthogonal polynomialpolynomial evaluationReinsch algorithmrounding error boundSzegő polynomials

Mathematics Subject Classification ID

Polynomials in number theory (11C08) Elementary functions (26A09) Computation of special functions and constants, construction of tables (65D20) Roundoff error (65G50)

Review text

The author presents a rounding error bound with the same general form for the evaluation of a polynomial written in any polynomial base when the evaluation algorithm can be expressed as a linear recurrence or a first-order linear matrix recurrence relation. In these bounds the condition number of the polynomials appears in a natural way. In the cases with rounding error bounds in the literature the new bounds generate the same or similar bounds. Examples are Horner's algorithm in the evaluation of power series and Clenshaw's and Forsythe's algorithm in the evaluation of orthogonal polynomial series [cf. \textit{C. W. Clenshaw}, Math. Tables Aids Comput. 9, 118--120 (1955; Zbl 0065.05403); \textit{G. E. Forsythe}, J. Soc. Ind. Appl. Math. 5, 74--88 (1957; Zbl 0083.35503)]. Among the `new' cases the author mentions the polynomial bases for the Szegő polynomials and the modified Reinsch algorithms for the evaluation of orthogonal polynomials near some specific (problematic) points [cf. \textit{P. Levrie} and \textit{R. Piessens}, A note on the evaluation of orthogonal polynomials using recurrence relations, Department of Computer Science, K. U. Leuven, Internal Report TW74 (1985)].

Recommendations

• Rounding error bounds for the Clenshaw and Forsythe algorithms for the evaluation of orthogonal polynomial series
• scientific article; zbMATH DE number 1206081
• Running relative error for the evaluation of polynomials
• Roundoff errors for polynomial evaluation by a family of formulae
• Error Bounds for Polynomial Evaluation and Complex Arithmetic

Cited in

(18)

• On the numerical evaluation of linear recurrences
• Three term recurrence for the evaluation of multivariate orthogonal polynomials
• Accurate evaluation of polynomials in Legendre basis
• Recursive de Casteljau bisection and rounding errors
• Evaluation of the derivative of a polynomial in Bernstein form
• scientific article; zbMATH DE number 1574479 (Why is no real title available?)
• A general condition number for polynomials
• Certification of bounds on expressions involving rounded operators
• Accelerations of Zhao's methods for the numerical inversion of Laplace transform
• Running relative error for the evaluation of polynomials
• scientific article; zbMATH DE number 5124811 (Why is no real title available?)
• Error Bounds for Polynomial Evaluation and Complex Arithmetic
• The three-term recursion for Chebyshev polynomials is mixed forward-backward stable
• Accurate evaluation of a polynomial in Chebyshev form
• Rounding error bounds for the Clenshaw and Forsythe algorithms for the evaluation of orthogonal polynomial series
• Accurate evaluation of a polynomial and its derivative in Bernstein form
• Parameterizing intersecting surfaces via invariants
• Effective bounds for P-recursive sequences

This page was built for publication: A unified rounding error bound for polynomial evaluation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1397303)