Least Squares Solver using Normal Equations

Find the best approximate solution to \(A \mathbf{x} \approx \mathbf{b}\) using the Normal Equations¹.
Solves \(A^TA\mathbf{x} = A^T\mathbf{b}\) to minimize \(\| A \mathbf{x} - \mathbf{b} \|_2\)².

The Normal Equations provide a direct method for solving least squares problems:

\[ A^TA\mathbf{x} = A^T\mathbf{b} \]

Derivation:

Minimizing \(\| A\mathbf{x} - \mathbf{b} \|_2^2\) requires the gradient to be zero:

\[ \nabla_{\mathbf{x}} \| A\mathbf{x} - \mathbf{b} \|^2 = 2A^T(A\mathbf{x} - \mathbf{b}) = \mathbf{0} \]

Key Points:

When \(A\) has full column rank, \(A^TA\) is invertible³
Simple and direct approach for small to medium problems
Less numerically stable than QR for ill-conditioned matrices⁴

Equations \(m\): Variables \(n\):

Enter dimensions and click Generate Matrix to create the input grid and b vector.

Display values as: Decimal Fraction

1 — Set Up

Loads a pre-filled 4×2 overdetermined system — ready to compute.

2 — Compute

Solves the least-squares problem via the normal equations AᵀAx = Aᵀb.

Resets all dimensions, matrix entries, and results.

Footnotes

The Normal Equations \(A^TA\mathbf{x} = A^T\mathbf{b}\) arise from setting the gradient of \(\|A\mathbf{x} - \mathbf{b}\|^2\) to zero. They transform an overdetermined system into a square system that can be solved directly. ↑
The least squares solution minimizes the 2-norm of the residual \(\mathbf{r} = A\mathbf{x} - \mathbf{b}\). Geometrically, it finds the point in the column space of \(A\) closest to \(\mathbf{b}\). ↑
When \(A\) has full column rank, the matrix \(A^TA\) is symmetric positive definite, guaranteeing a unique least squares solution. If \(A\) is rank-deficient, infinitely many solutions exist and the minimum-norm solution is selected. ↑
The condition number of \(A^TA\) is the square of the condition number of \(A\). For ill-conditioned matrices, QR factorization or SVD-based methods are preferred as they avoid squaring the condition number. ↑