Backward and forward stability analysis of Neville's algorithm for interpolation and a pyramid algorithm for the computation of Lebesgue functions.

In our previous paper (Camargo, Numer. Algor., 85:591–606, 2020), we proved that the algorithms in a certain class of divided differences schemes are backward stable and, in particular, we proved that Neville's algorithm for Lagrange interpolation is backward stable for extrapolation for monotonically ordered nodes. That proof was based on a very particular pattern of the signs of the components of the divided differences which, in the case of Neville's algorithm for monotonically ordered nodes, is not satisfied when interpolation is considered instead of extrapolation. In this note we present a different argument that shows that Neville's algorithm is backward stable on the whole real line for monotonically ordered nodes. Our reasoning is based on a pyramid algorithm for the computation of Lebesgue functions. We also explain that obtaining sharp upper bounds for the numerical error in the computation of Neville's algorithm for generic sets of nodes is difficult. [ABSTRACT FROM AUTHOR]