Note on a comparison of evaluation schemes for the interpolating polynomial

Abstract

In this note the computational efficiency of four methods for evaluating the interpolating polynomial is examined. The methods considered are the Lagrange representation, the Barycentric formula, Aitken's algorithm and Neville's algorithm. In general, the Barycentric formula is found to be best if the degree of the polynomial is large; for polynomials of low degree the Lagrange formula should be used when a large number of evaluations are required but Aiken's or Neville's algorithm is more efficient if few evaluations are needed.