Least squares: the best approximate solution of Ax = b
A system Ax = b has no solution, because the data that built it carry measurement error. Which x comes closest, and how do you find it without trying every x?
Where you are 3 in Orthogonality and least squares
When you reach for it
Corsin, Seraina and Flurin run an alpine cheese cellar. A wheel loses water as it ages, so it loses weight, and once a week they weigh one wheel and record y, the weight it has lost since it left the brine bath, in hundreds of grams. At weeks t = 0, 1, 2, 3 they record y = 1, 3, 4, 4. They want a trend line y = c_0 + c_1 t.
Asking the line to pass through every point gives one equation per weighing:
or A\mathbf{x} = \mathbf{b} with
The first two equations force c_0 = 1 and c_1 = 2, and then the third says 5 = 4. The system is inconsistent (Homogeneous systems and solutions in parametric vector form), as four measured points with real error almost always are. Row reduction can only report “no solution”. The useful question is which \mathbf{x} makes A\mathbf{x} as close to \mathbf{b} as possible. You reach for least squares whenever A\mathbf{x} = \mathbf{b} has no solution, typically more equations than unknowns built from measurements, and an approximate one is wanted.
The procedure
Let A be an m \times n matrix and \mathbf{b} a vector in \mathbb{R}^m. A least-squares solution of A\mathbf{x} = \mathbf{b} is a vector \hat{\mathbf{x}} in \mathbb{R}^n with
The vector \mathbf{b} - A\hat{\mathbf{x}} is the residual, and its length \lVert \mathbf{b} - A\hat{\mathbf{x}} \rVert is the least-squares error. The name comes from the square of the distance: if \mathbf{b} - A\mathbf{x} has entries r_1, \dots, r_m, then \lVert \mathbf{b} - A\mathbf{x} \rVert^2 = r_1^2 + \dots + r_m^2, and \hat{\mathbf{x}} makes that sum of squares least.
The closest point is a projection. Every A\mathbf{x} is a combination of the columns of A, so it lies in the column space \operatorname{Col} A (Image), and minimizing \lVert \mathbf{b} - A\mathbf{x} \rVert means finding the point of \operatorname{Col} A closest to \mathbf{b}. The best approximation theorem of Orthogonal bases and projection onto a subspace says that point is
the unique point of \operatorname{Col} A whose difference from \mathbf{b} is orthogonal to \operatorname{Col} A. Every subspace has an orthogonal basis (The Gram-Schmidt process), so \hat{\mathbf{b}} always exists. Since \hat{\mathbf{b}} is in \operatorname{Col} A, the system A\mathbf{x} = \hat{\mathbf{b}} is consistent, and its solutions are exactly the least-squares solutions of A\mathbf{x} = \mathbf{b}.
The normal equations skip the projection, and with it the orthogonal basis. A vector is orthogonal to \operatorname{Col} A exactly when it is orthogonal to each column \mathbf{a}_1, \dots, \mathbf{a}_n, and the dot products \mathbf{a}_j \cdot \mathbf{v} are the entries of A^{T}\mathbf{v}, because the rows of A^{T} are the columns of A (The transpose and symmetric matrices). So
Theorem 1 (normal equations). The least-squares solutions of A\mathbf{x} = \mathbf{b} are exactly the solutions of the normal equations A^{T}A\mathbf{x} = A^{T}\mathbf{b}, and there is always at least one.
Why. If A\hat{\mathbf{x}} = \hat{\mathbf{b}}, then \mathbf{b} - A\hat{\mathbf{x}} = \mathbf{b} - \hat{\mathbf{b}} is orthogonal to \operatorname{Col} A, so \hat{\mathbf{x}} solves the normal equations. Conversely, if A^{T}(\mathbf{b} - A\hat{\mathbf{x}}) = \mathbf{0}, then \mathbf{b} = A\hat{\mathbf{x}} + (\mathbf{b} - A\hat{\mathbf{x}}) splits \mathbf{b} into a piece in \operatorname{Col} A and a piece orthogonal to it. That split is unique (the orthogonal decomposition theorem), so A\hat{\mathbf{x}} = \hat{\mathbf{b}}. The same split gives, for any \mathbf{x},
by the Pythagorean theorem, since \mathbf{b} - A\mathbf{x} = (\mathbf{b} - A\hat{\mathbf{x}}) + A(\hat{\mathbf{x}} - \mathbf{x}) with orthogonal pieces.
The matrix A^{T}A is n \times n and symmetric, since (A^{T}A)^{T} = A^{T}(A^{T})^{T} = A^{T}A. Its (i, j) entry is \mathbf{a}_i \cdot \mathbf{a}_j, and the jth entry of A^{T}\mathbf{b} is \mathbf{a}_j \cdot \mathbf{b}.
Theorem 2 (when the answer is unique). A^{T}A is invertible exactly when the columns of A are linearly independent (Linear independence). In that case the least-squares solution is unique,
Why. If A^{T}A\mathbf{x} = \mathbf{0}, then 0 = \mathbf{x}^{T}A^{T}A\mathbf{x} = \lVert A\mathbf{x} \rVert^2, so A\mathbf{x} = \mathbf{0}; the converse is clear. So A^{T}A and A have the same null space (Kernel), and the square A^{T}A is invertible exactly when it is \{\mathbf{0}\}, that is, when the columns of A are independent (The invertible matrix theorem).
In practice you solve the normal equations by row reducing \begin{bmatrix} A^{T}A & A^{T}\mathbf{b} \end{bmatrix} (Solving a system by row reduction: one, none or infinitely many solutions); the inverse (Finding an inverse by row reducing A next to I) pays only for a 2 \times 2 matrix or when the same A meets many right-hand sides. With dependent columns the row reduction still works and shows a free variable.
Fitting a model. A model is linear in its coefficients when it has the form y = c_1 f_1(t) + \dots + c_n f_n(t) for fixed functions f_j: a line (1 and t), a parabola (1, t, t^2), \displaystyle c\sqrt{t}, or several inputs, c_0 + c_1 u + c_2 v. Each data point gives one equation, so row i of A is \begin{bmatrix} f_1(t_i) & \cdots & f_n(t_i) \end{bmatrix} and \mathbf{b} lists the observed y_i. The entries of \mathbf{b} - A\mathbf{x} are the vertical misses at the data points, and least squares makes the sum of their squares least. The statistics of that criterion are in The least squares criterion and its line; here one theorem covers every model of this form. With as many data points as coefficients and A invertible, the fit is exact, as for the cubic through four points in Linear systems in use: networks, chemical equations, fitting curves.
When an orthonormal basis of \operatorname{Col} A is at hand as the columns of Q, with A = QR, the same solution is \hat{\mathbf{x}} = R^{-1}Q^{T}\mathbf{b}; that factorization comes from the The Gram-Schmidt process.
Worked examples
Day 1: the cellar’s best line
Find the least-squares solution of the cellar system above, the best line, the residual and the least-squares error. Check that the residual is orthogonal to \operatorname{Col} A.
SolutionThe columns of A are \mathbf{a}_1 = (1, 1, 1, 1) and \mathbf{a}_2 = (0, 1, 2, 3). The entries of A^{T}A are their dot products, \mathbf{a}_1 \cdot \mathbf{a}_1 = 4, \mathbf{a}_1 \cdot \mathbf{a}_2 = 6, \mathbf{a}_2 \cdot \mathbf{a}_2 = 14, and A^{T}\mathbf{b} has entries \mathbf{a}_1 \cdot \mathbf{b} = 12 and \mathbf{a}_2 \cdot \mathbf{b} = 0 + 3 + 8 + 12 = 23. The normal equations are
The columns of A are independent, so by Theorem 2 the matrix is invertible (determinant 56 - 36 = 20), and by Inverse of a 2 by 2 matrix, and solving with it
The best line is \displaystyle y = \frac{3}{2} + t: 150 grams at week 0 and 100 grams more each week. Its values at the four weeks are \displaystyle A\hat{\mathbf{x}} = \left(\frac{3}{2}, \frac{5}{2}, \frac{7}{2}, \frac{9}{2}\right), so the residual is
Check: its dot product with \mathbf{a}_1 is \displaystyle -\frac{1}{2} + \frac{1}{2} + \frac{1}{2} - \frac{1}{2} = 0, and with \mathbf{a}_2 it is \displaystyle 0 + \frac{1}{2} + 1 - \frac{3}{2} = 0. The least-squares error is \displaystyle \sqrt{4 \cdot \frac{1}{4}} = 1, and the sum of squared misses is 1.
Day 1: a 3 by 2 system, checked against the projection
Find the least-squares solution of A\mathbf{x} = \mathbf{b} with
then compute \hat{\mathbf{b}} = \operatorname{proj}_{\operatorname{Col} A}\mathbf{b} directly from an orthogonal basis and confirm that A\hat{\mathbf{x}} = \hat{\mathbf{b}}.
SolutionThe system is inconsistent: the first row gives x_1 = 2, the second then x_2 = -2, and the third asks -4 = 5.
With \mathbf{a}_1 = (1, 1, 0) and \mathbf{a}_2 = (0, 1, 2), the dot products give A^{T}A = \begin{bmatrix} 2 & 1 \\ 1 & 5 \end{bmatrix} and A^{T}\mathbf{b} = \begin{bmatrix} 2 \\ 10 \end{bmatrix}. Row reduce the augmented matrix: subtract half of row 1 from row 2.
So x_2 = 2, then 2x_1 + 2 = 2 gives x_1 = 0, and \hat{\mathbf{x}} = (0, 2) with A\hat{\mathbf{x}} = (0, 2, 4).
Now the projection, found without the normal equations. The columns are not orthogonal (\mathbf{a}_1 \cdot \mathbf{a}_2 = 1), so first remove from \mathbf{a}_2 its projection onto \mathbf{a}_1: \displaystyle \mathbf{a}_2 - \frac{1}{2}\mathbf{a}_1 = \left(-\frac{1}{2}, \frac{1}{2}, 2\right), and scale by 2 to get \mathbf{u}_2 = (-1, 1, 4). With \mathbf{u}_1 = \mathbf{a}_1, the set \{\mathbf{u}_1, \mathbf{u}_2\} is an orthogonal basis of \operatorname{Col} A, and
The two routes agree, as Theorem 1 says. The residual (2, -2, 1) is orthogonal to both columns, and the error, the distance from \mathbf{b} to \operatorname{Col} A, is \displaystyle \sqrt{4 + 4 + 1} = 3.
Day 1: any other line does worse, by an exact amount
Flurin suggests the line through the first and last weighings, y = 1 + t. Find its sum of squared misses, and show it exceeds the best line’s by exactly \lVert A(\hat{\mathbf{x}} - \mathbf{x}) \rVert^2.
SolutionFlurin’s line is \mathbf{x} = (1, 1), with values A\mathbf{x} = (1, 2, 3, 4) at the four weeks. The misses are \mathbf{b} - A\mathbf{x} = (0, 1, 1, 0), so the sum of squares is 2, against 1 for the best line.
The identity in Theorem 1 predicts the gap. Here \displaystyle \hat{\mathbf{x}} - \mathbf{x} = \left(\frac{1}{2}, 0\right), so \displaystyle A(\hat{\mathbf{x}} - \mathbf{x}) = \frac{1}{2}\mathbf{a}_1 = \left(\frac{1}{2}, \frac{1}{2}, \frac{1}{2}, \frac{1}{2}\right), of squared length 1, and indeed 2 = 1 + 1. The best line sits half a unit above Flurin’s, and since the best residual is orthogonal to that shift, the squared lengths add with no cross term.
Day 2: a parabola through five weighings
A second, larger wheel is weighed every two weeks, at weeks t = 0, 2, 4, 6, 8, and has lost 30, 220, 320, 380 and 450 grams. Seraina expects the loss to slow, so she fits y = c_0 + c_1 s + c_2 s^2, where s = (t - 4)/2 counts two-week steps from the middle weighing. Find the best parabola and its least-squares error.
SolutionThe values of s are -2, -1, 0, 1, 2, and each row of A is \begin{bmatrix} 1 & s & s^2 \end{bmatrix}:
The model is linear in c_0, c_1, c_2, which is all the method needs. Centering s makes every odd power sum to zero, so
with, for instance, \sum s^2 y = 120 + 220 + 0 + 380 + 1800 = 2520. The middle equation is alone: 10c_1 = 1000, so c_1 = 100. The other two are 5c_0 + 10c_2 = 1400 and 10c_0 + 34c_2 = 2520. Subtract twice the first from the second: 14c_2 = -280, so c_2 = -20, and then 5c_0 = 1600, so c_0 = 320. The best parabola is
Its values are (40, 200, 320, 400, 440), the residual is (-10, 20, 0, -20, 10), and the error is \displaystyle \sqrt{1000} = 10\sqrt{10} \approx 31.6 grams. The negative c_2 measures Seraina’s slowing.
Day 2: two inputs at a ski area
In winter Corsin works the snowmaking crew at a ski area. On five nights the crew logs h, the hours below freezing, g, the number of snow guns running, and d, the depth of new snow on a test plot in centimeters:
| night | h | g | d |
|---|---|---|---|
| 1 | 4 | 2 | 11 |
| 2 | 6 | 2 | 16 |
| 3 | 8 | 2 | 23 |
| 4 | 6 | 1 | 11 |
| 5 | 6 | 3 | 19 |
Fit d = c_0 + c_1 h + c_2 g by least squares and find the error.
SolutionEach night gives a row \begin{bmatrix} 1 & h & g \end{bmatrix} of A, and \mathbf{b} = (11, 16, 23, 11, 19). The entries of A^{T}A are sums such as \sum h^2 = 16 + 36 + 64 + 36 + 36 = 188 and \sum hg = 8 + 12 + 16 + 6 + 18 = 60; the entries of A^{T}\mathbf{b} are \sum d = 80, \sum hd = 504 and \sum gd = 168. Row reduce the normal equations, taking 6 times row 1 from row 2 and 2 times row 1 from row 3:
So c_1 = 3, c_2 = 4, and 5c_0 + 90 + 40 = 80 gives c_0 = -10. The fit is d = -10 + 3h + 4g: each extra hour of cold adds about 3 centimeters and each extra gun about 4. Its values are (10, 16, 22, 12, 20), the residual is (1, 0, 1, -1, -1), and the error is 2 centimeters. The intercept -10 predicts nothing: no night in the data is near h = 0, g = 0.
Day 2: dependent columns and infinitely many answers
The cellar log has the age both in weeks t and in days 7t, and Flurin uses both: y = c_0 + c_1 t + c_2(7t). Find every least-squares solution for the data y = 1, 3, 4, 4, and show they all give the same fitted values.
SolutionThe columns of A are (1, 1, 1, 1), (0, 1, 2, 3) and (0, 7, 14, 21). The third is 7 times the second, so by Theorem 2 the matrix A^{T}A is singular, but the normal equations still have solutions (Theorem 1):
Row 3 is 7 times row 2, right side included (7 \cdot 23 = 161), so it reduces to zeros. The first two rows involve c_1 and c_2 only through c_1 + 7c_2, and with u = c_1 + 7c_2 they read 4c_0 + 6u = 12 and 6c_0 + 14u = 23, the normal equations of Example 1. So \displaystyle c_0 = \frac{3}{2} and c_1 + 7c_2 = 1, with c_2 free:
Every one gives c_1 t + 7c_2 t = t, the same line \displaystyle y = \frac{3}{2} + t and the same fitted values \displaystyle \left(\frac{3}{2}, \frac{5}{2}, \frac{7}{2}, \frac{9}{2}\right). The projection \hat{\mathbf{b}} is unique; only its description by the columns is not, since the solutions differ by multiples of (0, -7, 1), which spans the null space of A.
Boundaries
- A least-squares solution always exists, but it is unique only when the columns of A are independent. Otherwise the solutions form \hat{\mathbf{x}} + \operatorname{Nul} A, all with the same A\hat{\mathbf{x}} = \hat{\mathbf{b}} (Example 6). When m < n the columns are always dependent (Rank and nullity).
- The model must be linear in its coefficients. In y = c\,e^{kt} the unknown k sits in the exponent, so no matrix A exists. Logarithms give \ln y = \ln c + kt, linear in \ln c and k, but that minimizes the squared misses of \ln y, not of y, and the answers differ.
- Only misses in \mathbf{b} count; the rows of A are treated as exact.
- A fit says nothing reliable outside the range of its data (Example 5).
- With rounded decimals and nearly dependent columns the normal equations lose accuracy, and software uses the QR route instead; stated here without proof.
Where this goes next
Least squares ends the path through orthogonality: Orthogonal bases and projection onto a subspace gives the closest point, the The Gram-Schmidt process the orthogonal basis it needs, and the normal equations one square system. The statistics of the same criterion is in The least squares criterion and its line. Fits with several inputs, like the snowmaking model, are the matrix form of multiple regression.
Exercises
Day 1: normal equations and the best line
- Let A = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 1 \end{bmatrix} and \mathbf{b} = \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix}. Show that A\mathbf{x} = \mathbf{b} is inconsistent, then find \hat{\mathbf{x}}, \hat{\mathbf{b}} and the least-squares error.
- Find the least-squares solution and the least-squares error of A\mathbf{x} = \mathbf{b} for A = \begin{bmatrix} 2 & 1 \\ 0 & 1 \\ 1 & 1 \\ 1 & -1 \end{bmatrix} and \mathbf{b} = \begin{bmatrix} 3 \\ 3 \\ 4 \\ 0 \end{bmatrix}.
- Find the least-squares solution and error of A\mathbf{x} = \mathbf{b} for A = \begin{bmatrix} 1 & 2 \\ 0 & 1 \\ 1 & 1 \end{bmatrix} and \mathbf{b} = \begin{bmatrix} 3 \\ 1 \\ 2 \end{bmatrix}. What does the answer say about the system?
- A wheel’s recorded losses at weeks t = 1, 2, 3, 4 are y = 2, 3, 5, 6 hundred grams. Find the least-squares line y = c_0 + c_1 t and its sum of squared misses.
- A small wheel weighs 8.2, 7.9 and 7.9 kilograms at weeks t = 0, 1, 2. Fit w = c_0 + c_1 t by least squares, and give the residual.
- For the matrix A of Exercise 1, compute P = A(A^{T}A)^{-1}A^{T}. Use it to project (0, 0, 3) onto \operatorname{Col} A.
- Decide, by computing \det(A^{T}A), whether A\mathbf{x} = \mathbf{b} has a unique least-squares solution for every \mathbf{b}, for A_1 = \begin{bmatrix} 1 & 2 \\ 1 & 3 \\ 1 & 4 \end{bmatrix} and for A_2 = \begin{bmatrix} 1 & -2 \\ 2 & -4 \\ -1 & 2 \end{bmatrix}.
Day 1: reasoning
- Show that A^{T}A is symmetric for every matrix A, and that \mathbf{x}^{T}A^{T}A\mathbf{x} = \lVert A\mathbf{x} \rVert^2. Why does the second fact mean no diagonal entry of A^{T}A is negative?
- Show that if A\mathbf{x} = \mathbf{b} is consistent, its least-squares solutions are exactly its ordinary solutions, with error 0.
- A model has a column of ones in A (an intercept). Explain why the residual of its least-squares fit always has entries that sum to 0.
- The normal equations always have a solution, even when A^{T}A is singular. Give the reason, using the projection \hat{\mathbf{b}}.
Day 2: models and dependent columns
- Fit y = c_0 + c_1 s + c_2 s^2 by least squares to the points (-2, 2), (-1, 3), (0, 1), (1, 1), (2, 8), and find the error.
- On four test nights the snowmaking crew runs the north gun (u = 1) or not (u = 0) and the south gun (v = 1) or not (v = 0), one night for each combination: (u, v) = (0, 0), (1, 0), (0, 1), (1, 1), with depths 3, 4, 2, 7 centimeters. Fit z = c_0 + c_1 u + c_2 v and give the error.
- Corsin models a wheel’s loss as \displaystyle y = c\sqrt{t}. At weeks t = 1, 4, 9 the losses are 3, 5, 5 hundred grams. Find the least-squares c and the error.
- Find every least-squares solution of A\mathbf{x} = \mathbf{b} for A = \begin{bmatrix} 1 & 2 \\ 2 & 4 \\ 1 & 2 \end{bmatrix} and \mathbf{b} = \begin{bmatrix} 1 \\ 1 \\ 4 \end{bmatrix}, and the vector \hat{\mathbf{b}} they all share.
- A wheel is weighed at s = -2, -1, 0, 1, 2 (weeks from the middle weighing): 10.4, 10.1, 9.9, 9.8, 9.3 kilograms. Fit w = c_0 + c_1 s and find the sum of squared misses.
Day 2: reasoning
- Fitting y = c_0 + c_1 t + c_2 t^2 + c_3 t^3 to four points with different t values always gives error 0. Explain why.
- Explain why y = c_0 + c_1 e^{kt}, with c_0, c_1 and k all unknown, cannot be fitted by the normal equations, while y = c_0 + c_1 e^{t} can.
- Prove that the residual \mathbf{b} - A\hat{\mathbf{x}} is orthogonal to A\hat{\mathbf{x}}, and deduce \lVert \mathbf{b} \rVert^2 = \lVert \hat{\mathbf{b}} \rVert^2 + \lVert \mathbf{b} - \hat{\mathbf{b}} \rVert^2.
- Let \hat{\mathbf{x}}_1 be one least-squares solution. Prove that the set of all least-squares solutions is \{\hat{\mathbf{x}}_1 + \mathbf{n} : A\mathbf{n} = \mathbf{0}\}, and that all of them give the same A\hat{\mathbf{x}}.
Answers
- The first two rows force x_1 = x_2 = 1, and then the third says 2 = 0. A^{T}A = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}, A^{T}\mathbf{b} = (1, 1), so \displaystyle \hat{\mathbf{x}} = \left(\frac{1}{3}, \frac{1}{3}\right) and \displaystyle \hat{\mathbf{b}} = \left(\frac{1}{3}, \frac{1}{3}, \frac{2}{3}\right). The residual is \displaystyle \left(\frac{2}{3}, \frac{2}{3}, -\frac{2}{3}\right), so the error is \displaystyle \frac{2\sqrt{3}}{3}.
- A^{T}A = \begin{bmatrix} 6 & 2 \\ 2 & 4 \end{bmatrix}, A^{T}\mathbf{b} = (10, 10). Solving, \hat{\mathbf{x}} = (1, 2). Then A\hat{\mathbf{x}} = (4, 2, 3, -1), the residual is (-1, 1, 1, 1), and the error is 2.
- A^{T}A = \begin{bmatrix} 2 & 3 \\ 3 & 6 \end{bmatrix}, A^{T}\mathbf{b} = (5, 9), so \hat{\mathbf{x}} = (1, 1), with error 0 because A\hat{\mathbf{x}} = (3, 1, 2) = \mathbf{b}. The system is consistent, and this is its exact solution.
- A^{T}A = \begin{bmatrix} 4 & 10 \\ 10 & 30 \end{bmatrix}, A^{T}\mathbf{b} = (16, 47), determinant 20. The line is \displaystyle y = \frac{1}{2} + \frac{7}{5}t, with values 1.9, 3.3, 4.7, 6.1, misses 0.1, -0.3, 0.3, -0.1, and sum of squares \displaystyle \frac{1}{5}.
- A^{T}A = \begin{bmatrix} 3 & 3 \\ 3 & 5 \end{bmatrix}, A^{T}\mathbf{b} = (24, 23.7). Solving gives w = 8.15 - 0.15t, with values 8.15, 8.0, 7.85 and residual (0.05, -0.1, 0.05).
- \displaystyle (A^{T}A)^{-1} = \frac{1}{3}\begin{bmatrix} 2 & -1 \\ -1 & 2 \end{bmatrix}, so \displaystyle P = \frac{1}{3}\begin{bmatrix} 2 & -1 & 1 \\ -1 & 2 & 1 \\ 1 & 1 & 2 \end{bmatrix}. Then P(0, 0, 3) = (1, 1, 2).
- A_1^{T}A_1 = \begin{bmatrix} 3 & 9 \\ 9 & 29 \end{bmatrix} has determinant 6, so the solution is always unique. A_2^{T}A_2 = \begin{bmatrix} 6 & -12 \\ -12 & 24 \end{bmatrix} has determinant 0 (column 2 is -2 times column 1), so never unique.
- (A^{T}A)^{T} = A^{T}(A^{T})^{T} = A^{T}A. And \mathbf{x}^{T}A^{T}A\mathbf{x} = (A\mathbf{x})^{T}(A\mathbf{x}) = (A\mathbf{x}) \cdot (A\mathbf{x}) = \lVert A\mathbf{x} \rVert^2. Taking \mathbf{x} = \mathbf{e}_j picks out the (j, j) entry, which is therefore \lVert \mathbf{a}_j \rVert^2 \ge 0.
- If \mathbf{b} is in \operatorname{Col} A, the closest point of \operatorname{Col} A to \mathbf{b} is \mathbf{b} itself, so \hat{\mathbf{b}} = \mathbf{b} and the least-squares solutions are the solutions of A\mathbf{x} = \mathbf{b}, with error 0.
- By the normal equations the residual is orthogonal to every column, in particular to (1, 1, \dots, 1), and that dot product is the sum of its entries.
- \hat{\mathbf{b}} lies in \operatorname{Col} A, so A\mathbf{x} = \hat{\mathbf{b}} has a solution \hat{\mathbf{x}}, and \mathbf{b} - \hat{\mathbf{b}} is orthogonal to \operatorname{Col} A, so A^{T}(\mathbf{b} - A\hat{\mathbf{x}}) = \mathbf{0}.
- A^{T}A is the matrix of Example 4 and A^{T}\mathbf{b} = (15, 10, 44). Then 10c_1 = 10, 14c_2 = 44 - 30, and 5c_0 = 15 - 10, so y = 1 + s + s^2. Its values are (3, 1, 1, 3, 7), the residual (-1, 2, 0, -2, 1), and the error \displaystyle \sqrt{10}.
- A^{T}A = \begin{bmatrix} 4 & 2 & 2 \\ 2 & 2 & 1 \\ 2 & 1 & 2 \end{bmatrix}, A^{T}\mathbf{b} = (16, 11, 9). Solving gives z = 2 + 3u + v, with values (2, 5, 3, 6), residual (1, -1, -1, 1) and error 2.
- A is the single column (1, 2, 3), so the normal equation is 14c = 3 + 10 + 15 = 28 and c = 2. The values are (2, 4, 6), the residual (1, 1, -1), and the error \displaystyle \sqrt{3}.
- A^{T}A = \begin{bmatrix} 6 & 12 \\ 12 & 24 \end{bmatrix} and A^{T}\mathbf{b} = (7, 14); the second equation is twice the first, leaving 6x_1 + 12x_2 = 7. So \displaystyle \hat{\mathbf{x}} = \left(\frac{7}{6} - 2k, k\right) for any k, and every one gives \displaystyle \hat{\mathbf{b}} = \left(\frac{7}{6}, \frac{7}{3}, \frac{7}{6}\right), the projection of \mathbf{b} onto the line spanned by (1, 2, 1).
- A^{T}A = \begin{bmatrix} 5 & 0 \\ 0 & 10 \end{bmatrix} and A^{T}\mathbf{b} = (49.5, -2.5), so w = 9.9 - 0.25s. The values are 10.4, 10.15, 9.9, 9.65, 9.4, the misses 0, -0.05, 0, 0.15, -0.1, and the sum of squares 0.035.
- A is 4 \times 4 with rows \begin{bmatrix} 1 & t_i & t_i^2 & t_i^3 \end{bmatrix}. A nonzero cubic has at most three roots, so A\mathbf{c} = \mathbf{0} only for \mathbf{c} = \mathbf{0} and A is invertible. So A\mathbf{x} = \mathbf{b} is always consistent, and by Exercise 9 the error is 0.
- The method needs y = c_1 f_1(t) + \dots + c_n f_n(t) with known functions f_j. With k unknown, e^{kt} is not known and y is not linear in k (e^{2kt} is not twice e^{kt}), so no matrix A exists. With k = 1, row i of A is \begin{bmatrix} 1 & e^{t_i} \end{bmatrix}.
- A\hat{\mathbf{x}} \cdot (\mathbf{b} - A\hat{\mathbf{x}}) = \hat{\mathbf{x}}^{T}A^{T}(\mathbf{b} - A\hat{\mathbf{x}}) = \hat{\mathbf{x}}^{T}\mathbf{0} = 0 by the normal equations. Since \mathbf{b} = \hat{\mathbf{b}} + (\mathbf{b} - \hat{\mathbf{b}}) with orthogonal pieces, the Pythagorean theorem gives the identity.
- If A\mathbf{n} = \mathbf{0}, then A^{T}A(\hat{\mathbf{x}}_1 + \mathbf{n}) = A^{T}A\hat{\mathbf{x}}_1 = A^{T}\mathbf{b}. Conversely, if \hat{\mathbf{x}}_2 is another least-squares solution, then A\hat{\mathbf{x}}_1 = \hat{\mathbf{b}} = A\hat{\mathbf{x}}_2 by Theorem 1, so \mathbf{n} = \hat{\mathbf{x}}_2 - \hat{\mathbf{x}}_1 has A\mathbf{n} = \mathbf{0}. Every solution has A\hat{\mathbf{x}} = \hat{\mathbf{b}}.