Optimal stability of the Lagrange formula and conditioning of the Newton formula (Q1711823)

In this paper, both Lagrange and Newton interpolation formulae are considered with respect to conditioning and stability. A special, i.e., pointwise, condition number is introduced for this interpolation problem, and it is shown that with respect to this particular condition number, the Lagrange expression for the polynomial interpolation is the best. Next, there is a relation of the stability of the Newton description of the polynomial interpolant in comparison to the Lagrange formulation (where a so-called Leja ordering of the interpolation nodes can improve the situation which is otherwise known to be critical). The behaviour that can be observed with Newton as compared to Lagrange can even be identified at (at least) one of the nodes for which the pointwise condition number is useful. In fact, both conditioning and the mentioned stability are regarded in this article. The comparison of Newton and Lagrange is considered in the paper not only for ordinary nodes but specifically also for Leja nodes. In fact, the best uniform upper bounds for conditioning of the Newton situation are very concretely \(3^n\) while we have a bounds of \(2^n\) for the Lagrange case. These are obtained by using \(n+1\) equally spaced interpolation points. The bounds are attained at the final node.