Recipe

Solve a least-squares problem with the normal equations

Use when: you have an inconsistent system $A\mathbf x=\mathbf b$ (more conditions than the data can satisfy exactly) and need the best-fit $\hat{\mathbf x}$

Goal: the least-squares solution $\hat{\mathbf x}$ , found by solving one square system built from $A$ and $\mathbf b$

Taught in The normal equations

Quick recipe

Build the design matrix $A$ and the target vector $\mathbf b$
Compute $A^{\mathsf T}A$
Compute $A^{\mathsf T}\mathbf b$
Solve the square system $A^{\mathsf T}A\hat{\mathbf x}=A^{\mathsf T}\mathbf b$
Verify the residual is orthogonal to every column of $A$

1
One row per data point, one column per unknown coefficient — a column of $1$ s for an intercept, a column of $x$ -values for a slope, and so on.

Example

Fit $y=c+mx$ to $(-1,2),\ (0,3),\ (1,7)$ : $A=\begin{bmatrix}1&-1\\1&0\\1&1\end{bmatrix}$ , $\mathbf b=\begin{pmatrix}2\\3\\7\end{pmatrix}$ .

Why: $A^{\mathsf T}A\hat{\mathbf x}=A^{\mathsf T}\mathbf b$ is built entirely out of $A$ and $\mathbf b$ — get these two objects right and everything after is arithmetic.
2
Entry $(1,1)$ is the number of data points; the cross entries are $\sum x_i$ ; entry $(2,2)$ is $\sum x_i^2$ (in general, each entry is a dot product of two columns of $A$ ).

Example

$n=3$ , $\sum x_i = -1+0+1=0$ , $\sum x_i^2=1+0+1=2$ , so $A^{\mathsf T}A=\begin{bmatrix}3&0\\0&2\end{bmatrix}$ .

Why: $A^{\mathsf T}A$ is always square and symmetric, with size equal to the number of unknowns — no matter how many data points went into building it.
3
Entry $1$ is $\sum y_i$ ; entry $2$ is $\sum x_iy_i$ .

Example

$\sum y_i=2+3+7=12$ , $\sum x_iy_i=(-1)(2)+0(3)+1(7)=5$ , so $A^{\mathsf T}\mathbf b=\begin{pmatrix}12\\5\end{pmatrix}$ .

Why: this vector is everything the data has to say about $\mathbf b$ , compressed down to one column the same size as $\hat{\mathbf x}$ .
4
Solve by elimination or by inverting $A^{\mathsf T}A$ , exactly as with any other square system.

Example

$\begin{bmatrix}3&0\\0&2\end{bmatrix}\begin{pmatrix}c\\m\end{pmatrix}=\begin{pmatrix}12\\5\end{pmatrix}$ gives $c=12/3=4$ and $m=5/2=2.5$ .

⚡ Shortcut

If the $x$ -values are centered so that $\sum x_i=0$ (shift every $x_i$ by their mean first if they aren't), $A^{\mathsf T}A$ comes out diagonal automatically and the system decouples completely, with no elimination needed at all: $c=\dfrac{\sum y_i}{n}$ and $m=\dfrac{\sum x_iy_i}{\sum x_i^2}$ . Here that's $c=12/3=4$ and $m=5/2=2.5$ — read straight off two sums, matching the general method exactly.

Why: $A^{\mathsf T}A$ is invertible exactly when $A$ 's columns are independent, and solving this one small square system is the entire payoff of collapsing an inconsistent, many-equation system down to just $n$ equations.
5
Compute $\mathbf r=\mathbf b-A\hat{\mathbf x}$ and confirm $A^{\mathsf T}\mathbf r=\mathbf 0$ — every column of $A$ , dotted with $\mathbf r$ , should come out to $0$ .

Example

$\hat y=(1.5,\ 4,\ 6.5)$ , so $\mathbf r=(0.5,\ -1,\ 0.5)$ . Column $1$ (all $1$ s): $0.5-1+0.5=0$ . Column $2$ ( $x$ -values $-1,0,1$ ): $(-1)(0.5)+0(-1)+1(0.5)=0$ .

Why: this is exactly the perpendicularity condition the normal equations were built to enforce — a nonzero $A^{\mathsf T}\mathbf r$ means an arithmetic error happened upstream, not that least squares occasionally fails.

Common mistakes

Forgetting the transpose and computing $A A$ or $A\mathbf b$ instead of $A^{\mathsf T}A$ and $A^{\mathsf T}\mathbf b$ .
Mixing up which entry of $\hat{\mathbf x}$ is $c$ and which is $m$ after swapping the column order of $A$ .
Using the centered- $x$ shortcut on data that was never actually shifted to have $\sum x_i=0$ .
Treating a tiny nonzero $A^{\mathsf T}\mathbf r$ from rounding decimals as a sign the method failed, instead of just carrying exact fractions further.