Polynomial Curve Fitting With Vandermonde Matrices

From Polynomial Fits to Matrix Equations

Suppose measurements \((x_i,y_i)\), for \(i=1,\dots,m\), are given, and we want a polynomial of degree at most \(d\) that fits them. Write the polynomial in the fixed order of powers \(p(x)=c_0+c_1x+\cdots+c_dx^d\). At each input \(x_i\), the fitted value is a linear combination of the coefficients: \(c_0+c_1x_i+\cdots+c_dx_i^d\). Collecting these equations gives a matrix problem. When there are more measurements than coefficients, an exact fit may not exist; least squares chooses coefficients that minimize the sum of squared vertical residuals.

The columns correspond, in order, to the constant term, the coefficient of \(x\), the coefficient of \(x^2\), and so on. A quadratic fit therefore uses three columns, while a cubic fit uses four. A least-squares coefficient vector minimizes \(\|\mathbf{y}-\mathbf{A}\mathbf{c}\|^2\). The normal equations are \(\mathbf{A}^{\top}\mathbf{A}\mathbf{c}=\mathbf{A}^{\top}\mathbf{y}\); the earlier material on least squares establishes that their solutions are precisely the least-squares coefficient vectors.

For a quadratic fit, the \(i\)th row is \([1,x_i,x_i^2]\). For a cubic fit, it is \([1,x_i,x_i^2,x_i^3]\). These are sometimes called Vandermonde matrices even though some conventions display their transpose. Here the rows are observations and the columns are powers, so \(\mathbf{A}\mathbf{c}\) directly lists the fitted values at the sample inputs.

A Quadratic Fit with Four Measurements

Why Distinct Inputs Give a Unique Fit

Having enough data points does not by itself guarantee that the coefficients are identifiable. What matters for the Vandermonde matrix is that there are enough distinct inputs. The polynomial fact behind this condition is that a nonzero polynomial of degree at most \(d\) cannot vanish at more than \(d\) distinct real numbers.

Proof. We use induction on the degree. A nonzero constant polynomial has no roots, which proves the claim for degree \(0\). Now suppose the claim holds for degree at most \(d-1\), and let \(q\) be a nonzero polynomial of degree \(d\). If \(q\) has no root, the claim holds. Otherwise let \(a\) be one of its roots. The factor theorem gives \(q(x)=(x-a)s(x)\), where \(s\) is a nonzero polynomial of degree \(d-1\). Every root of \(q\) different from \(a\) is a root of \(s\), because \(x-a\ne0\) at such a root. By the induction hypothesis, \(s\) has at most \(d-1\) distinct roots. Including \(a\), \(q\) has at most \(d\). \(\square\)

Proof. Let \(\mathbf{c}=(c_0,\dots,c_d)^\top\) satisfy \(\mathbf{A}\mathbf{c}=\mathbf{0}\). Define \(q(x)=c_0+c_1x+\cdots+c_dx^d\). By the definition of the rows of \(\mathbf{A}\), the equation \(\mathbf{A}\mathbf{c}=\mathbf{0}\) says \(q(x_i)=0\) for all \(m\) distinct inputs. Since \(m\ge d+1\), the lemma forces \(q\) to be the zero polynomial. Therefore all its coefficients \(c_0,\dots,c_d\) are zero, proving that the columns are independent.

To verify uniqueness of the least-squares fit, full column rank implies that \(\mathbf{A}^{\top}\mathbf{A}\) is invertible: if \(\mathbf{A}^{\top}\mathbf{A}\mathbf{h}=\mathbf{0}\), then \(\|\mathbf{A}\mathbf{h}\|^2=\mathbf{h}^{\top}\mathbf{A}^{\top}\mathbf{A}\mathbf{h}=0\), so \(\mathbf{A}\mathbf{h}=\mathbf{0}\), and column independence gives \(\mathbf{h}=\mathbf{0}\). Let \(\widehat{\mathbf{c}}\) solve the normal equations and let \(\widehat{\mathbf{r}}=\mathbf{y}-\mathbf{A}\widehat{\mathbf{c}}\). Then \(\mathbf{A}^{\top}\widehat{\mathbf{r}}=\mathbf{0}\). For any other coefficient vector \(\widehat{\mathbf{c}}+\mathbf{h}\), its squared residual norm is

If \(\mathbf{h}\ne\mathbf{0}\), column independence gives \(\mathbf{A}\mathbf{h}\ne\mathbf{0}\), so the last term is positive. Hence \(\widehat{\mathbf{c}}\) is the unique minimizer. \(\square\)

Distinctness is a sufficient condition, not a requirement that every problem must satisfy to have some least-squares solution. If inputs repeat, the design matrix may have dependent columns and the coefficient vector may fail to be unique; least-squares solutions still exist, but the polynomial values at the observed inputs need not identify a unique coefficient vector.

A Cubic Fit with Five Measurements

A Quadratic Fit with Fractional Coefficients

Column Order and a Common Mistake

A coefficient vector has meaning only relative to its stated column order. For the order \([1,x,x^2]\), the coefficient vector \((1,2,1)^\top\) represents \(1+2x+x^2\). If the columns are changed to \([1,x^2,x]\), the same polynomial is represented instead by \((1,1,2)^\top\). The design matrix and coefficient vector must be changed together; merely swapping columns while retaining the old coefficient vector changes the fit.

Common mistake: Suppose the first worked example is rewritten with columns \([1,x^2,x]\). The correct coefficient vector in that order is \((1,1,2)^\top\), still giving \(1+2x+x^2\). A wrong calculation keeps \((1,2,1)^\top\) and then reads it as though the columns were \([1,x,x^2]\), reporting \(1+x+2x^2\). At \(x=2\), that mistaken polynomial predicts \(1+2+8=11\), whereas the fitted value is \(9\). The correction is to keep the column order and coefficients paired: use \((1,2,1)^\top\) with \([1,x,x^2]\), or \((1,1,2)^\top\) with \([1,x^2,x]\).

Other checks help catch setup errors. Each row should use one observation, and each column should correspond to one power. The data vector must list the measured \(y_i\) values in the same order as the rows. After solving, calculate \(\mathbf{A}\mathbf{c}\) and \(\mathbf{y}-\mathbf{A}\mathbf{c}\); the latter should be orthogonal to every column when the normal equations hold. The residual sum of squares is a sum of squared residuals, so it cannot be negative.