A Unified Rounding Error Bound for Polynomial Evaluation | Advances in Computational Mathematics Skip to main content
Springer Nature Link
Log in

A Unified Rounding Error Bound for Polynomial Evaluation

  • Published:
Advances in Computational Mathematics Aims and scope Submit manuscript

Abstract

We present a unified rounding error bound for polynomial evaluation. The bound presented here takes the same general form for the evaluation of a polynomial written in any polynomial basis when the evaluation algorithm can be expressed as a linear recurrence or a first-order linear matrix recurrence relation. Examples of these situations are: Horner's algorithm in the evaluation of power series, Clenshaw's and Forsythe's algorithms in the evaluation of orthogonal polynomial series, de-Casteljau's algorithm for Bernstein polynomial series, the modification of Clenshaw's algorithms in the evaluation of Szegő polynomial series, and so on.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. M. Alfaro, F. Marcellán, M.L. Rezola and A. Ronveaux, On orthogonal polynomials of Sobolev type: Algebraic properties and zeros, SIAM J. Math. Anal. 23 (1992) 737–757.

    Google Scholar 

  2. G.S. Ammar, W.B. Gragg and L. Reichel, An analoge for Szegő polynomials of the Clenshaw algorithm, J. Comput. Appl. Math. 46 (1993) 211–216.

    Google Scholar 

  3. R. Barrio, Rounding error bounds for the Clenshaw and Forsythe algorithms for the evaluation of orthogonal polynomial series, J. Comput. Appl. Math. 138 (2002) 185–204.

    Google Scholar 

  4. R. Barrio, B. Melendo and S. Serrano, Generation and evaluation of orthogonal polynomials in discrete Sobolev spaces I: Algorithms, Preprint (2002).

  5. R. Barrio, B. Melendo and S. Serrano, On the numerical evaluation of linear recurrences, J. Comput. Appl. Math. 150 (2003) 71–86.

    Google Scholar 

  6. R. Barrio and J.M. Peña, Numerical evaluation of the pth derivative of the Jacobi series, to appear in Appl. Numer. Math.

  7. C.W. Clenshaw, A note on the summation of Chebyshev series, Math. Tab. Wash. 9 (1955) 118–120.

    Google Scholar 

  8. P. Deuflhard, On algorithms for the summation of certain special functions, Computing 17 (1976) 37–48.

    Google Scholar 

  9. D. Elliott, Error analysis of an algorithm for summing certain finite series, J. Australian Math. Soc. 8 (1968) 213–221.

    Google Scholar 

  10. G. Farin, Curves and Surfaces for Computer Aided Geometric Design, 4th ed. (Academic Press, San Diego, CA, 1996).

    Google Scholar 

  11. R.T. Farouki and T.N.T. Goodman, On the optimal stability of Bernstein basis,Math. Comp. 65 (1996) 1553–1566.

    Google Scholar 

  12. R.T. Farouki and V.T. Rajan, On the numerical condition of polynomials in Bernstein basis, Comp. Aided Geom. Design 4 (1987) 191–216.

    Google Scholar 

  13. G.E. Forsythe, Generation and use of orthogonal polynomials for data fitting with a digital computer, J. SIAM 5 (1957) 74–88.

    Google Scholar 

  14. W. Gautschi, Questions of numerical condition related to polynomials, in: Studies in Numerical Analysis, ed. G.H. Golub, MAA Studies in Mathematics, Vol. 24 (1984) pp. 140–177.

  15. N.J. Higham, Accuracy and Stability of Numerical Algorithms (SIAM, Philadelphia, PA, 1996).

    Google Scholar 

  16. 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).

  17. E. Mainar and J.M. Peña, Error analysis of corner cutting algorithms, Numer. Algorithms 22 (1999) 41–52.

    Google Scholar 

  18. A.C.R. Newbery, Error analysis for polynomial evaluation, Math. Comp. 28 (1974) 789–793.

    Google Scholar 

  19. J. Oliver, An error analysis of the modified Clenshaw method for evaluating Chebyshev and Fourier series, Math. Comp. 20 (1977) 379–391.

    Google Scholar 

  20. J. Oliver, Rounding error propagation in polynomial evaluation schemes, Comput. Appl. Math. 5 (1979) 85–97.

    Google Scholar 

  21. J.L. Schonfelder and M. Ramaz, Error control with polynomial evaluation, IMA J. Numer. Anal. 1 (1980) 105–114.

    Google Scholar 

  22. F.J. Smith, An algorithm for summing orthogonal polynomial series and their derivatives with applications to curve-fitting and interpolation, Math. Comp. 19 (1965) 33–36.

    Google Scholar 

  23. G. Szegő, Orthogonal Polynomials, American Mathematical Society Colloquium Publications, Vol. 23, 4th ed. (Amer. Math. Soc., Providence, RI, 1975).

    Google Scholar 

  24. J.H. Wilkinson, The evaluation of the zeros of ill-conditioned polynomials, Parts I and II, Numer. Math. 1 (1959) 150–166 and 167–180.

    Google Scholar 

  25. J.H. Wilkinson, Rounding Errors in Algebraic Processes, Notes on Applied Science No. 32 (Her Majesty's Stationery Office, London, 1963); reprinted by (Dover, New York, 1994).

    Google Scholar 

  26. H. Zhang, Numerical condition of polynomials in different forms, Electronic Trans. Numer. Anal. 12 (2001) 66–87.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. GME, Departamento de Matemática Aplicada, Universidad de Zaragoza, E-50009, Zaragoza, Spain

    R. Barrio

Authors
  1. R. Barrio
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Barrio, R. A Unified Rounding Error Bound for Polynomial Evaluation. Advances in Computational Mathematics 19, 385–399 (2003). https://doi.org/10.1023/A:1024203520270

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1024203520270

Search

Navigation