×

A unified rounding error bound for polynomial evaluation. (English) Zbl 1036.65025

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. C. W. Clenshaw, Math. Tables Aids Comput. 9, 118–120 (1955; Zbl 0065.05403); 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. P. Levrie and R. Piessens, A note on the evaluation of orthogonal polynomials using recurrence relations, Department of Computer Science, K. U. Leuven, Internal Report TW74 (1985)].

MSC:

65D20 Computation of special functions and constants, construction of tables
65G50 Roundoff error
26A09 Elementary functions
12Y05 Computational aspects of field theory and polynomials (MSC2010)
11C08 Polynomials in number theory
PDFBibTeX XMLCite
Full Text: DOI