Why is Lagrange interpolation numerically unstable? Here is my understanding of the polynomial interpolation problem: Interpolating by inverting the Vandermonde matrix is unstable because the Vandermonde matrix is ill-conditioned, so "difficult" to invert. Lagrange interpolation is much more clever as it computes the same polynomial using a different basis where the matrix is diagonal, so easy to invert. Furthermore, the algorithm for computing Lagrange polynomials is straightforward and I don't see anything that makes it unstable. So why is it commonly claimed in textbooks that Lagrange interpolation is numerically unstable? Thanks!

Instability does not always refer to numerical issues in an algorithm. It can refer to the effect of perturbations in data inputs to the output solution. For example, in the picture below we fit a 4th degree polynomial to two sets of 5 data points. The data sets match except that the data point at the origin has been perturbed slightly (can think of it as measurement error). Although the perturbation is small, the change in the Lagrange polynomial is large.

!4th degree Lagrange polynomial

This behavior is not caused by numerical inaccuracies in the algorithm to compute the coefficients of the polynomial, it is inherent in the interpolation problem itself.