the ill-conditioned Vandermonde basis
/ VAN-der-mond /
When you fit a polynomial with the obvious basis — the plain powers 1, x, x^2, x^3, and so on — you build a design matrix called a Vandermonde matrix, whose rows are (1, x_i, x_i^2, ...). It looks innocent, but it hides a trap: as the polynomial degree climbs, this matrix becomes wildly ill-conditioned. The columns grow nearly parallel, the least-squares problem becomes acutely sensitive, and the coefficients you compute can be off by orders of magnitude even though the fitted curve still looks fine.
Why do the columns become parallel? On a typical interval, the functions x^k and x^(k+1) look more and more alike as k grows — they all bend upward in much the same way — so the columns of the Vandermonde matrix point in nearly the same direction. The condition number of a Vandermonde matrix grows EXPONENTIALLY with degree (on [0,1] it roughly doubles with every added degree). At a condition number of 10^16 you have lost all 16 of your double-precision digits, so for a degree-20-ish monomial fit the coefficients are pure noise. This is the problem's fault, baked into the chosen basis — not the solver's.
The fix is to change the basis, not the solver. Use orthogonal polynomials (Chebyshev or Legendre) whose columns are near-perpendicular by construction, or at least center and scale the data (replace x by (x - mean)/spread) before forming the powers — that one cheap step can rescue many degrees of accuracy. The barycentric Lagrange form sidesteps the Vandermonde matrix entirely for interpolation. The lesson generalizes: the same mathematical fit can be well- or ill-conditioned depending purely on how you parameterize it, so choosing a good basis is a real and consequential part of numerical modeling.
Fitting a degree-15 polynomial on [0, 1] with the monomial basis gives a Vandermonde matrix with condition number around 10^10 or worse; the computed coefficients can be meaningless. The very same data fit in the Chebyshev basis has a condition number of order one and yields trustworthy coefficients.
Same fit, different basis: monomials are exponentially ill-conditioned, Chebyshev is tame.
An ill-conditioned Vandermonde fit can still produce a curve that looks right while its coefficients are garbage — conditioning is a property of the parameterization, not of whether the picture looks plausible. Centering and scaling x, or switching to an orthogonal-polynomial basis, fixes it.