From Equations to a Fitting Problem
A system of linear equations asks whether one vector of unknowns satisfies every equation exactly. When there are more equations than unknowns, the system is called overdetermined. Such a system may still have an exact solution, but it need not. If the equations are inconsistent, one useful question is not whether all equations can be satisfied, but which choice of unknowns makes the discrepancies collectively as small as possible.
Let \(m,n\in\mathbb{N}\) with \(m>n\), let \(\mathbf{A}\in\mathbb{R}^{m\times n}\), and let \(\mathbf{b}\in\mathbb{R}^m\). The system \(\mathbf{A}\mathbf{x}=\mathbf{b}\) has \(m\) equations and \(n\) unknowns, where \(\mathbf{x}\in\mathbb{R}^n\) and \(\mathbf{b}\) is the target vector. The matrix-vector product \(\mathbf{A}\mathbf{x}\) is the vector of predicted left-hand sides. The difference between the target and that product records the error in each equation.
For a vector \(\mathbf{y}=(y_1,\dots,y_m)^\top\in\mathbb{R}^m\), the Euclidean norm satisfies \(\|\mathbf{y}\|^2=y_1^2+\cdots+y_m^2\). Thus, if \(a_{ij}\) is the entry in row \(i\), column \(j\) of \(\mathbf{A}\), the objective can be written one coordinate at a time:
Each summand is the square of one equation's residual. Squaring prevents positive and negative errors from cancelling one another, and adding the squares gives a single nonnegative measure of the overall discrepancy. This is the unweighted Euclidean least-squares formulation; the objective treats the coordinates through their ordinary squared Euclidean errors.
Exact Solutions and Least-Squares Solutions
An exact solution makes every residual coordinate zero. A least-squares solution, by contrast, minimizes the total squared residual; its individual residuals do not have to be zero. The two ideas are connected, but they are not interchangeable.
Proof. Write \(\mathbf{r}(\mathbf{x})=\mathbf{b}-\mathbf{A}\mathbf{x}\), and let its \(i\)-th coordinate be \(r_i(\mathbf{x})=b_i-\sum_{j=1}^{n}a_{ij}x_j\), by the definition of matrix-vector multiplication. The Euclidean norm therefore gives \(f(\mathbf{x})=\|\mathbf{r}(\mathbf{x})\|^2=\sum_{i=1}^{m}r_i(\mathbf{x})^2\), which is the stated coordinate formula. Every square in this sum is nonnegative. The sum equals zero exactly when every square is zero, which is equivalent to \(r_i(\mathbf{x})=0\) for each \(i\). That coordinate condition says precisely \(\mathbf{b}-\mathbf{A}\mathbf{x}=\mathbf{0}\), or \(\mathbf{A}\mathbf{x}=\mathbf{b}\). \(\square\)
Proof. Assume that an exact solution \(\mathbf{x}_0\) exists. The proposition gives \(f(\mathbf{x}_0)=0\). Since \(f(\mathbf{x})\) is a sum of squares for every \(\mathbf{x}\), it is nonnegative, so no vector can have objective value below zero. Thus the minimum is zero. If \(\mathbf{x}\) is an exact solution, then \(f(\mathbf{x})=0\), so it attains that minimum and is a least-squares solution. Conversely, if \(\mathbf{x}\) is a least-squares solution, its objective value is the minimum, which is zero. The proposition then implies \(\mathbf{A}\mathbf{x}=\mathbf{b}\). This proves both directions. \(\square\)
If no exact solution exists, the proposition says that no vector has objective value zero. A least-squares solution, when identified, is instead a vector attaining the smallest possible squared error, which is then positive. The formulation itself does not say that a particular candidate is a minimizer; that must be established by calculation or by a result suited to finding minimizers.
Worked Fits in Small Systems
Worked Example: An Overdetermined System with an Exact Fit
Consider three equations in two unknowns, written as \(\mathbf{A}\mathbf{x}=\mathbf{b}\), with \(\mathbf{x}=(x_1,x_2)^\top\):
There are three equations and two unknowns, so the system is overdetermined. For the proposed vector \(\mathbf{x}=(2,-1)^\top\), compute the product row by row:
The residual is therefore \(\mathbf{r}(\mathbf{x})=\mathbf{b}-\mathbf{A}\mathbf{x}=(0,0,0)^\top\), and the objective is \(f(\mathbf{x})=0^2+0^2+0^2=0\). Since the objective cannot be negative, this is a least-squares solution, and it is also an exact solution. Substitution into all three equations confirms the fit: \(x_1=2\), \(x_2=-1\), and \(x_1+x_2=1\).
Worked Example: One Unknown and Three Inconsistent Equations
Now consider \(\mathbf{A}\mathbf{x}=\mathbf{b}\), where \(x\in\mathbb{R}\):
The equations ask for \(x=1\), \(x=2\), and \(x=3\) simultaneously, so there is no exact solution. For a proposed value \(x=t\), the predicted vector and residual are
Consequently, the squared-error objective is \(f(t)=(1-t)^2+(2-t)^2+(3-t)^2\). Complete squares by grouping around \(t=2\):
Because \((t-2)^2\geq0\), the objective is at least \(2\), with equality at \(t=2\). Thus \(\widehat{x}=2\) is a least-squares solution. Its predicted vector is \(\mathbf{A}\widehat{x}=(2,2,2)^\top\), so its residual is \((-1,0,1)^\top\), and direct substitution gives \(f(2)=(-1)^2+0^2+1^2=2\). This confirms the minimum found by completing squares. The residual is not zero, so this best fit is not an exact solution.
Worked Example: Two Unknowns with Four Equations
Let \(\mathbf{x}=(s,t)^\top\) and take
The predicted vector is \(\mathbf{A}\mathbf{x}=(s,t,s,t)^\top\), so the residual and squared error are
Group the terms involving \(s\), and then those involving \(t\). For \(s\), write \(s-1=(s-2)+1\) and \(s-3=(s-2)-1\). For \(t\), write \(t-2=(t-3)+1\) and \(t-4=(t-3)-1\). This gives
Both squared terms are nonnegative, so \(f(s,t)\geq4\), with equality when \(s=2\) and \(t=3\). Hence \(\widehat{\mathbf{x}}=(2,3)^\top\) minimizes the objective. Check the matrix product and residual:
The nonzero residual confirms that this is an approximate fit, not an exact solution. In this example the completed-square expression also shows directly that no other pair gives the same minimum: equality requires both \(s=2\) and \(t=3\).
How to Read the Formulation Correctly
The matrix \(\mathbf{A}\) and target \(\mathbf{b}\) specify the fitting problem; the variable \(\mathbf{x}\) is what can be chosen. For every candidate \(\mathbf{x}\), first compute \(\mathbf{A}\mathbf{x}\), then subtract it from \(\mathbf{b}\) to obtain the residual, and then sum the squares of the residual's coordinates. This translates a system into an objective function on \(\mathbb{R}^n\). It does not by itself supply a minimizing vector.
For an overdetermined system, \(\mathbf{A}\) has \(m\) rows and \(n\) columns with \(m>n\); \(\mathbf{b}\) has \(m\) entries and \(\mathbf{x}\) has \(n\).
For a proposed \(\mathbf{x}\), calculate \(\mathbf{r}(\mathbf{x})=\mathbf{b}-\mathbf{A}\mathbf{x}\), keeping each equation's discrepancy in its own coordinate.
Use \(f(\mathbf{x})=\|\mathbf{r}(\mathbf{x})\|^2\), or expand it as the sum of the squared coordinate errors.
A zero residual means an exact solution. A least-squares claim means the objective is no larger than at any other candidate.
A common mistake is to solve one equation and treat its answer as an exact fit to an inconsistent system. In the one-unknown example, using the first equation gives \(x=1\). The incorrect conclusion is that \(x=1\) solves the system. Substitution into all three equations gives the predicted vector \((1,1,1)^\top\), not \((1,2,3)^\top\); the residual is \((0,1,2)^\top\), and the squared error is \(0^2+1^2+2^2=5\). The correction is to check every equation for an exact solution, or, when exact satisfaction fails, compare candidates using the full squared-error objective. A small error in one equation is not enough to establish that the total error is minimized.
| Question | Mathematical test | Meaning |
|---|---|---|
| Is \(\mathbf{x}\) an exact solution? | \(\mathbf{b}-\mathbf{A}\mathbf{x}=\mathbf{0}\) | Every equation is satisfied. |
| What is its squared error? | \(\sum_{i=1}^{m}r_i(\mathbf{x})^2\) | The sum of all coordinate errors squared. |
| Is \(\mathbf{x}\) a least-squares solution? | \(f(\mathbf{x})\leq f(\mathbf{z})\) for every \(\mathbf{z}\in\mathbb{R}^n\) | No candidate has smaller squared error. |
| Can an exact solution be least squares? | Yes; its objective is \(0\). | Every exact solution is a least-squares solution. |
Check Your Understanding
For each question, keep the residual and objective distinct from the claim that a candidate minimizes the objective.
- For \(\mathbf{A}=\begin{bmatrix}1\\2\\1\end{bmatrix}\), \(\mathbf{b}=\begin{bmatrix}2\\4\\2\end{bmatrix}\), and \(x=2\), compute the predicted vector, residual, and squared error. Is the fit exact?
- Write the squared-error objective for \(\mathbf{A}=\begin{bmatrix}1&0\\1&1\\0&1\end{bmatrix}\), \(\mathbf{b}=\begin{bmatrix}1\\3\\4\end{bmatrix}\), and \(\mathbf{x}=(s,t)^\top\).
- Explain why a zero value of the squared-error objective guarantees that every equation is satisfied.
- For the system in the worked example with \(\mathbf{A}=(1,1,1)^\top\) and \(\mathbf{b}=(1,2,3)^\top\), compute the residual and squared error at \(x=1\).
- State the difference between proving that a vector is an exact solution and proving that it is a least-squares solution.
