Visual Tools
Calculators
Tables
Mathematical Keyboard
Converters
Other Tools

How to Solve a Least-Squares Problem

When Ax=bA\mathbf{x} = \mathbf{b} has no solution, find the x^\hat{\mathbf{x}} that makes Ax^A\hat{\mathbf{x}} as close to b\mathbf{b} as possible. Multiply both sides by ATA^T and solve the square system that results.

Recognize the task

More equations than unknowns and no exact solution: a tall matrix AA, data that do not fit a model exactly, "best approximate solution", "minimize ∥Ax−b∥\|A\mathbf{x} - \mathbf{b}\|". Forms: (101112)x=(6,0,0)\begin{pmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \end{pmatrix}\mathbf{x} = (6, 0, 0); x=1x = 1, x=2x = 2, x=6x = 6. Test: row reduce [A∣b][A \mid \mathbf{b}]; a row [0  ⋯  0∣c][0 \; \cdots \; 0 \mid c] with c≠0c \neq 0 means you need least squares.
The problem and its geometry are in the least squares lesson.

Two ways to do it

Normal equationsby hand
ATA x^=ATbA^TA\,\hat{\mathbf{x}} = A^T\mathbf{b}
A square, symmetric system, solvable whenever the columns of AA are independent (normal equations).
QR factorizationnumerically safer
R x^=QTbR\,\hat{\mathbf{x}} = Q^T\mathbf{b}
Factor A=QRA = QR with the QR decomposition, then back-substitute (least squares via QR).

Steps

StepOn A=(101112)A = \begin{pmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \end{pmatrix}, b=(6,0,0)\mathbf{b} = (6, 0, 0)
1Confirm there is no exact solution. The equations x1=6x_1 = 6, x1+x2=0x_1 + x_2 = 0, x1+2x2=0x_1 + 2x_2 = 0 contradict each other.the first two give x2=−6x_2 = -6, the first and third give x2=−3x_2 = -3: inconsistent
2Form the normal equations. Multiply AA and b\mathbf{b} on the left by ATA^T. The result is an n×nn \times n system, nn the number of unknowns.ATA=(3335)A^TA = \begin{pmatrix} 3 & 3 \\ 3 & 5 \end{pmatrix}, ATb=(6,0)A^T\mathbf{b} = (6, 0)
3Solve the square system. Use elimination or the inverse of a 2×2 matrix.3x1+3x2=63x_1 + 3x_2 = 6, 3x1+5x2=03x_1 + 5x_2 = 0 ⇒\Rightarrow x^=(5,−3)\hat{\mathbf{x}} = (5, -3)
4Compute the projection and the error. Ax^A\hat{\mathbf{x}} is the orthogonal projection of b\mathbf{b} onto the column space; e=b−Ax^\mathbf{e} = \mathbf{b} - A\hat{\mathbf{x}} is the error.Ax^=(5,2,−1)A\hat{\mathbf{x}} = (5, 2, -1), e=(1,−2,1)\mathbf{e} = (1, -2, 1), ∥e∥2=6\|\mathbf{e}\|^2 = 6
5Check that the error is orthogonal to the columns. ATeA^T\mathbf{e} must be the zero vector; that is exactly what the normal equations say.ATe=(1−2+1,  0−2+2)=(0,0)A^T\mathbf{e} = (1 - 2 + 1,\; 0 - 2 + 2) = (0, 0) ✓

Worked examples

Example 1 · one unknown, three readings

1 column
x=1x = 1, x=2x = 2, x=6x = 6: A=(1,1,1)TA = (1, 1, 1)^T, b=(1,2,6)\mathbf{b} = (1, 2, 6)
three equations, one unknown
ATA=3A^TA = 3, ATb=9A^T\mathbf{b} = 9
x^=3\hat{x} = 3, the mean of the readings
least squares averages here

Example 2 · orthogonal columns

diagonal normal matrix
A=(111−1111−1)A = \begin{pmatrix} 1 & 1 \\ 1 & -1 \\ 1 & 1 \\ 1 & -1 \end{pmatrix}, b=(1,2,3,6)\mathbf{b} = (1, 2, 3, 6)
the columns are orthogonal
ATA=4IA^TA = 4I, ATb=(12,−4)A^T\mathbf{b} = (12, -4)
no elimination needed
x^=(3,−1)\hat{\mathbf{x}} = (3, -1), e=(−1,−2,1,2)\mathbf{e} = (-1, -2, 1, 2)
divide by 44

Example 3 · a full two-by-two solve

error vector
A=(100111)A = \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ 1 & 1 \end{pmatrix}, b=(1,1,0)\mathbf{b} = (1, 1, 0)
ATA=(2112)A^TA = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}, ATb=(1,1)A^T\mathbf{b} = (1, 1)
x^=(13,13)\hat{\mathbf{x}} = (\frac{1}{3}, \frac{1}{3})
solve 2x+y=12x + y = 1, x+2y=1x + 2y = 1
e=(23,23,−23)\mathbf{e} = (\frac{2}{3}, \frac{2}{3}, -\frac{2}{3}), ∥e∥2=43\|\mathbf{e}\|^2 = \frac{4}{3}
check: ATe=0A^T\mathbf{e} = \mathbf{0}
Fitting a line or a parabola to data is the same computation: see least-squares fitting. Solve the normal equations in the linear systems calculator.

See it happen

The vectors AxA\mathbf{x} fill the column space of AA, a flat subspace, and b\mathbf{b} sticks out of it. The closest point is the foot of the perpendicular from b\mathbf{b}, so the error b−Ax^\mathbf{b} - A\hat{\mathbf{x}} is perpendicular to every column: AT(b−Ax^)=0A^T(\mathbf{b} - A\hat{\mathbf{x}}) = \mathbf{0}, which is the normal equations. See it in the least squares visualizer.

Common mistakes

Cancelling the transpose

✗ ATAx^=ATb⇒Ax^=bA^TA\hat{\mathbf{x}} = A^T\mathbf{b} \Rightarrow A\hat{\mathbf{x}} = \mathbf{b}
✓ ATA^T has no inverse when AA is tall; solve the n×nn \times n system as it stands

Multiplying in the wrong order

✗ AATx^=ATbAA^T\hat{\mathbf{x}} = A^T\mathbf{b}
✓ ATAx^=ATbA^TA\hat{\mathbf{x}} = A^T\mathbf{b}; ATAA^TA is n×nn \times n, matching x^\hat{\mathbf{x}}

Treating the fit as exact

✗ x^=(5,−3)\hat{\mathbf{x}} = (5, -3) solves Ax=bA\mathbf{x} = \mathbf{b}
✓ Ax^=(5,2,−1)≠bA\hat{\mathbf{x}} = (5, 2, -1) \neq \mathbf{b}; the minimum error is ∥e∥=6\|\mathbf{e}\| = \sqrt{6}

Dependent columns

✗ inverting ATAA^TA when the columns of AA are dependent
✓ ATAA^TA is then singular and there are infinitely many x^\hat{\mathbf{x}}; the pseudoinverse picks the shortest
See the pseudoinverse section.