Overdetermined Linear Systems

More Equations Than Unknowns

Suppose we want to fit a curve to measured data. We often have more observations than model parameters. Writing $one equation$ for each observation then produces an $overdetermined linear system$ .

A system is overdetermined when the number $m$ of equations is greater than the number $n$ of unknowns, so $m > n$ . Such a system can have an exact solution. Measurement data usually contain points that do not lie exactly on the chosen model.

Quadratic Fit for Seven Observations

Consider $7$ data points that we want to fit with a $quadratic polynomial$ .

The observations are:

$i$	$1$	$2$	$3$	$4$	$5$	$6$	$7$
$t_i$	$-3$	$-2$	$-1$	$0$	$1$	$2$	$3$
$y_i$	$-2.2$	$-4.2$	$-4.2$	$-1.8$	$1.8$	$8.2$	$15.8$

We seek a parabola of the form:

y = a_2 \cdot t^2 + a_1 \cdot t + a_0

The unknowns are the $3$ parameters $a_2$ (quadratic coefficient), $a_1$ (linear coefficient), and $a_0$ (constant term).

Setting Up the System of Equations

Substituting each pair $(t_i,y_i)$ into the polynomial gives one equation. The $7$ observations therefore give $7$ equations for only $3$ $unknown coefficients$ .

a_2 \cdot (-3)^2 + a_1 \cdot (-3) + a_0 = -2.2

Evaluating the powers of each $t_i$ turns the system into:

9a_2 - 3a_1 + a_0 = -2.2

Matrix Form

The system of equations above can be written in $matrix form$ $A \cdot x = b$ .

\begin{pmatrix} 9 & -3 & 1 \\ 4 & -2 & 1 \\ 1 & -1 & 1 \\ 0 & 0 & 1 \\ 1 & 1 & 1 \\ 4 & 2 & 1 \\ 9 & 3 & 1 \end{pmatrix} \begin{pmatrix} a_2 \\ a_1 \\ a_0 \end{pmatrix} = \begin{pmatrix} -2.2 \\ -4.2 \\ -4.2 \\ -1.8 \\ 1.8 \\ 8.2 \\ 15.8 \end{pmatrix}

For a quadratic model fitted to $m$ data points, the same construction has the general form:

\begin{pmatrix} t_1^2 & t_1 & 1 \\ \vdots & \vdots & \vdots \\ t_m^2 & t_m & 1 \end{pmatrix} \begin{pmatrix} a_2 \\ a_1 \\ a_0 \end{pmatrix} = \begin{pmatrix} y_1 \\ \vdots \\ y_m \end{pmatrix}

Why There Is No Exact Solution

In this example, matrix $A$ has size $7 \times 3$ and the coefficient vector $x$ has size $3 \times 1$ . We therefore have $7$ equations for $3$ unknowns.

An exact solution exists exactly when $\operatorname{rank}(A)=\operatorname{rank}(A\mid b)$ . Matrix dimensions alone do not decide this.

The three columns of $A$ are linearly independent. Indeed, a polynomial $c_2t^2+c_1t+c_0$ of degree at most $2$ that vanishes at all seven distinct values of $t_i$ must be the zero polynomial. Therefore $\operatorname{rank}(A)=3$ .

Appending $b$ forms the augmented matrix $(A\mid b)$ . The first four rows already give the nonzero minor

\det\begin{pmatrix}9&-3&1&-2.2\\4&-2&1&-4.2\\1&-1&1&-4.2\\0&0&1&-1.8\end{pmatrix}=-\frac45

This nonzero minor shows that $\operatorname{rank}(A\mid b)=4$ .

Because $\operatorname{rank}(A) \ne \operatorname{rank}(A\mid b)$ , the system $has no exact solution$ . No single quadratic polynomial passes through all $7$ observations.

Solution with Least Squares

When an overdetermined system has no exact solution, we can instead find the polynomial that is closest to the observations in the $least-squares$ sense.

For observation $i$ , the vertical residual is $r_i = y_i-(a_2t_i^2+a_1t_i+a_0)$ . Least squares chooses the coefficients that $minimize the sum of the squared residuals$ :

\min_{a_2,a_1,a_0}\sum_{i=1}^{7}\left[y_i-(a_2t_i^2+a_1t_i+a_0)\right]^2

This criterion penalizes large misses more strongly and produces one best-fitting parabola because $A$ has full column rank. The normal equations are

A^TA=\begin{pmatrix}196&0&28\\0&28&0\\28&0&7\end{pmatrix}

The middle equation directly gives the linear coefficient. Use the last equation to express the constant through the quadratic coefficient, then substitute into the first equation.

28a_1=\frac{424}{5}\quad\Rightarrow\quad a_1=\frac{106}{35}

Solving them gives

\hat x=\begin{pmatrix}\hat a_2\\\hat a_1\\\hat a_0\end{pmatrix}=\begin{pmatrix}\frac{103}{105}\\\frac{106}{35}\\-\frac{211}{105}\end{pmatrix}

The fitted values do not equal every observation, which is expected. The residual vector is

r=b-A\hat x=\begin{pmatrix}\frac1{15}\\-\frac2{35}\\-\frac17\\\frac{22}{105}\\-\frac15\\\frac8{35}\\-\frac{11}{105}\end{pmatrix}

The residual vector $r$ satisfies

A^Tr=0

The equation $A^Tr=0$ says that the remaining error is orthogonal to every column of $A$ . Geometrically, $A\hat x$ is the orthogonal projection of $b$ onto the column space of $A$ .

Overdetermined systems are common in engineering and science because experiments often provide many measurements for a model with relatively few parameters. Least squares uses all of those measurements without pretending that noisy data fit the model exactly.

The curve shows the fitted model, while the points mark observations. Rotate or zoom to compare each point with the curve. Its vertical difference is the residual at the same time value.

Least-squares fit

\hat{y}(t)=0.98095t^2+3.02857t-2.00952

The cyan curve is the fitted polynomial, while the orange points are the seven observations in

b

$x$: $[-3, 3]$
$y$: $[-4.35, 15.9]$