On the numerical stability of Newton's formula for Lagrange interpolation

It was previously noticed in the literature that the computation of Newton's formula can be very sensitive to the ordering of the input data and it may be numerically unstable even for interpolation at the Chebyshev nodes. Nevertheless, to the best of our knowledge, the effects of rounding errors in the computation of Newton's formula have not been properly quantized yet. In this note we make a full stability analysis of the propagation of rounding errors in the computation of Newton's formula for Lagrange interpolation. We derive sharp upper bounds for the numerical error in the computations of three algorithms for computing polynomial interpolants in Newton form that can be used to understand the instabilities mentioned above. We throw light on and give a practical meaning to the condition number defined in Carnicer et al. (2019) by showing that it is the right thermometer for measuring the effects of rounding errors in the computation of Newton's formula. (C) 2019 Elsevier B.V. All rights reserved.