The Least-Squares Solution of a Linear System (Without Collinearity)

An overdetermined linear system is a system $A\mathbf{x}=\mathbf{b}$ with more equations than unknowns. In general, no vector $\mathbf{x}$ satisfies every equation exactly. Instead, we look for the vector $\hat{\mathbf{x}}$ that makes $A\mathbf{x}$ as close to $\mathbf{b}$ as possible. This vector is the least-squares solution -- it minimizes

$$\|A\mathbf{x}-\mathbf{b}\|^2.$$

The least-squares solution satisfies the normal equations

$$A^T\!A\,\hat{\mathbf{x}}=A^T\mathbf{b}.$$

When the columns of $A$ are linearly independent (the "no collinearity" condition), $A^T\!A$ is invertible. Solving for $\hat{\mathbf{x}}$ gives

$$\boxed{\;\hat{\mathbf{x}}=(A^T\!A)^{-1}A^T\mathbf{b}.\;}$$

To use this formula, we just need four steps: form $A^T\!A$, form $A^T\mathbf{b}$, invert the $2\times 2$ (or larger) matrix $A^T\!A$, and multiply.