Recipe

Solve a least-squares problem via QR factorization

Use when: you have an overdetermined system $A\mathbf x\approx\mathbf b$ ( $A$ has more rows than columns, independent columns) and need a numerically trustworthy $\hat{\mathbf x}$ -- not just any correct one

Goal: the least-squares solution $\hat{\mathbf x}$ , reached without ever forming $A^{\mathsf T}\!A$

Taught in Least squares via QR factorization

Quick recipe

Factor A as QR
Compute Q^T b
Back-substitute to solve R x-hat = Q^T b
Check the residual against every column of A

1
Run Gram-Schmidt (Chapter 11) on $A$ 's columns. This gives $Q$ (orthonormal columns, same shape as $A$ ) and $R$ (upper triangular, square).

Example

For fitting $y=c+mx$ to $(0,0),(3,5),(4,6),(7,7)$ : $A=\begin{bmatrix}1&0\\1&3\\1&4\\1&7\end{bmatrix}$ factors as $Q=\begin{bmatrix}0.5&-0.7\\0.5&-0.1\\0.5&0.1\\0.5&0.7\end{bmatrix}$ , $R=\begin{bmatrix}2&7\\0&5\end{bmatrix}$ . This is the same factorization the widget above steps through.
- A's columns are linearly independent — proceed. $R$ will have a positive entry on every diagonal spot. The factorization is unique.
- A's columns are linearly dependent — $R$ will have a zero on some diagonal spot. There is no unique least-squares solution. The fitting model itself needs fewer or different columns before this recipe applies.
⚡ Shortcut

For a plain line fit ( $A$ has only $2$ columns) where the $x$ -values aren't nearly identical, the normal equations are only a $2\times2$ system. That's small enough that Section 2's direct method works fine; building $Q$ and $R$ by hand buys little here. The danger Section 3 demonstrated only bites hard once the problem grows (more columns) or the columns become nearly dependent (Section 6's ill-conditioned monomial basis). Reach for this recipe when either of those is true, not reflexively on every fit.

Why: this is the one-time cost that lets every later solve skip $A^{\mathsf T}\!A$ altogether. It's Chapter 11's own factorization, reused here for exactly the reason its own proof mentioned.
2
Multiply $Q^{\mathsf T}$ (the thin, $n$ -column $Q$ from Step 1 -- never a square $m\times m$ orthogonal matrix) against $\mathbf b$ .

Example

$Q^{\mathsf T}\mathbf b=\begin{bmatrix}0.5&0.5&0.5&0.5\\-0.7&-0.1&0.1&0.7\end{bmatrix}\begin{bmatrix}0\\5\\6\\7\end{bmatrix}=\begin{bmatrix}9\\5\end{bmatrix}$

Why: this is exactly the substitution the least-squares-via-qr theorem's own proof performs on the right-hand side: $A^{\mathsf T}\mathbf b=(QR)^{\mathsf T}\mathbf b=R^{\mathsf T}(Q^{\mathsf T}\mathbf b)$ . So $Q^{\mathsf T}\mathbf b$ is the only piece of $\mathbf b$ the rest of the solve ever needs.
3
Solve the triangular system from the bottom row up, exactly as any triangular system from Chapter 7.

Example

$\begin{bmatrix}2&7\\0&5\end{bmatrix}\hat{\mathbf x}=\begin{bmatrix}9\\5\end{bmatrix}$ : bottom row gives $5\hat x_2=5\Rightarrow\hat x_2=1$ ; top row gives $2\hat x_1+7(1)=9\Rightarrow\hat x_1=1$ .

Why: $R$ is triangular by construction (Step 1). So back substitution needs no elimination at all -- the bottom row is already solved before the first operation runs.
4
Compute $\mathbf r=\mathbf b-A\hat{\mathbf x}$ and confirm $A^{\mathsf T}\mathbf r\approx\mathbf 0$ .

Example

$A\hat{\mathbf x}=(1,4,5,8)$ , so $\mathbf r=(0,5,6,7)-(1,4,5,8)=(-1,1,1,-1)$ . Check: $\sum r_i=-1+1+1-1=0$ ; $\sum x_ir_i=0(-1)+3(1)+4(1)+7(-1)=3+4-7=0$ .

Why: this is the same orthogonality condition the normal equations were built from in the first place (Section 2). Confirming it holds catches an arithmetic slip in any of the previous three steps.

Common mistakes

Solving $R\hat{\mathbf x}=Q^{\mathsf T}\mathbf b$ by computing $R^{-1}$ and multiplying, instead of back-substituting. This is correct in exact arithmetic, but it throws away the numerical advantage this recipe exists to provide -- computing an inverse is its own source of unnecessary round-off.
Using the square, $m\times m$ orthogonal matrix from a full QR factorization instead of the thin, $m\times n$ $Q$ this recipe needs. For a rectangular $A$ , only the thin $Q$ has the right shape to make $Q^{\mathsf T}\mathbf b$ a length- $n$ vector matching $R$ .
Falling back to $A^{\mathsf T}\!A$ out of habit when computing $Q^{\mathsf T}\mathbf b$ . The entire point of Step 2 is that it needs only $Q$ and $\mathbf b$ , never $A$ multiplied against itself.
Reading $R$ 's diagonal entries as if they were ordinary elimination pivots. They're actually Gram-Schmidt norms ( $\lVert v_j\rVert$ from Chapter 11's own construction) -- a different number, computed a different way, even though both sit on a triangular matrix's diagonal.