A new efficient algorithm for polynomial interpolation

A new backward stable algorithm (Algorithm 2) for polynomial interpolation based on the Lagrange and the Newton interpolation forms is proposed. It is shown that the Aitken algorithm and the scheme of the divided differences can be significantly less accurate than the proposed unconditionally stable Algorithm 2. Numerical examples that illustrate the advantage of a new algorithm are also given.