  In recent years many efforts have been devoted to finding bidiagonal
factorizations of nonsingular totally positive matrices, since their accurate
computation allows to numerically solve several important algebraic problems
with great precision, even for large ill-conditioned matrices. In this
framework, the present work provides the factorization of the collocation
matrices of Newton bases -- of relevance when considering the Lagrange
interpolation problem -- together with an algorithm that allows to numerically
compute it to high relative accuracy. This further allows to determine the
coefficients of the interpolating polynomial and to compute the singular values
and the inverse of the collocation matrix. Conditions that guarantee high
relative accuracy for these methods and, in the former case, for the classical
recursion formula of divided differences, are determined. Numerical errors due
to imprecise computer arithmetic or perturbed input data in the computation of
the factorization are analyzed. Finally, numerical experiments illustrate the
accuracy and effectiveness of the proposed methods with several algebraic
problems, in stark contrast with traditional approaches.
