Normal Equations

When $A$ is not square, we cannot solve $Ax = b$ directly. The normal equations transform the overdetermined system into a square one by multiplying both sides by $A^T$. This produces an $n \times n$ system that always has a unique solution when $A$ has full column rank.

---

Derivation

Start with the overdetermined system:

$$A_{m \times n}\, x_{n \times 1} = b_{m \times 1}$$

Multiply both sides on the left by $A^T$ (an $n \times m$ matrix):

$$A^T A\, x = A^T b$$

Examining the dimensions:

$$\underbrace{A^T}_{n \times m} \underbrace{A}_{m \times n} \underbrace{x}_{n \times 1} = \underbrace{A^T}_{n \times m} \underbrace{b}_{m \times 1}$$

The product $A^T A$ is an $n \times n$ square matrix. This is the system we solve to find the least squares solution.

Note

The system $A^T A x = A^T b$ is called the normal equations. Solving it gives the $x$ that minimizes $\|Ax - b\|^2$. You can solve the resulting $n \times n$ system using Gaussian elimination, LU decomposition, or (for small systems) by inverting $A^T A$ directly.

---

Worked Example 1: Polynomial Fitting

Problem: Given the data $f(-3) = 0$, $f(0) = 0$, $f(6) = 2$, find the least squares polynomial $P_1(x) = a_0 + a_1 x$ of degree 1 that best fits these three points.

Step 1 — Set up the overdetermined system

Substituting each data point into $P_1(x) = a_0 + a_1 x$:

$$P_1(-3) = a_0 - 3a_1 = 0$$ $$P_1(0) = a_0 + 0 \cdot a_1 = 0$$ $$P_1(6) = a_0 + 6a_1 = 2$$

In matrix form $Ax = b$:

$$A = \begin{bmatrix} 1 & -3 \\ 1 & 0 \\ 1 & 6 \end{bmatrix}, \qquad x = \begin{bmatrix} a_0 \\ a_1 \end{bmatrix}, \qquad b = \begin{bmatrix} 0 \\ 0 \\ 2 \end{bmatrix}$$

Three equations, two unknowns. This is overdetermined — no exact solution exists in general.

Step 2 — Form the normal equations $A^T A x = A^T b$

$$\begin{bmatrix} 1 & 1 & 1 \\ -3 & 0 & 6 \end{bmatrix} \begin{bmatrix} 1 & -3 \\ 1 & 0 \\ 1 & 6 \end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 \\ -3 & 0 & 6 \end{bmatrix} \begin{bmatrix} 0 \\ 0 \\ 2 \end{bmatrix}$$

Compute $A^T A$:

$$A^T A = \begin{bmatrix} 1+1+1 & -3+0+6 \\ -3+0+6 & 9+0+36 \end{bmatrix} = \begin{bmatrix} 3 & 3 \\ 3 & 45 \end{bmatrix}$$

Compute $A^T b$:

$$A^T b = \begin{bmatrix} 0+0+2 \\ 0+0+12 \end{bmatrix} = \begin{bmatrix} 2 \\ 12 \end{bmatrix}$$

The normal equations become:

$$\begin{bmatrix} 3 & 3 \\ 3 & 45 \end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \end{bmatrix} = \begin{bmatrix} 2 \\ 12 \end{bmatrix}$$

Step 3 — Solve by inverse matrix

$$\begin{bmatrix} a_0 \\ a_1 \end{bmatrix} = \begin{bmatrix} 3 & 3 \\ 3 & 45 \end{bmatrix}^{-1} \begin{bmatrix} 2 \\ 12 \end{bmatrix}$$

The determinant is $\det = 3 \times 45 - 3 \times 3 = 135 - 9 = 126$. The inverse is:

$$\begin{bmatrix} 3 & 3 \\ 3 & 45 \end{bmatrix}^{-1} = \frac{1}{126} \begin{bmatrix} 45 & -3 \\ -3 & 3 \end{bmatrix}$$

Therefore:

$$\begin{bmatrix} a_0 \\ a_1 \end{bmatrix} = \frac{1}{126} \begin{bmatrix} 45 & -3 \\ -3 & 3 \end{bmatrix} \begin{bmatrix} 2 \\ 12 \end{bmatrix} = \frac{1}{126} \begin{bmatrix} 90 - 36 \\ -6 + 36 \end{bmatrix} = \frac{1}{126} \begin{bmatrix} 54 \\ 30 \end{bmatrix}$$

Step 4 — Solution

$$\boxed{a_0 = \frac{54}{126} = \frac{3}{7}, \qquad a_1 = \frac{30}{126} = \frac{5}{21}}$$

The best-fit line is:

$$P_1(x) = \frac{3}{7} + \frac{5}{21}\,x$$

Note

You can also solve the normal equations using Gaussian elimination or LU decomposition instead of the inverse matrix. All three approaches give the same result. In an exam, follow whatever method is specified in the question.

---

Worked Example 2: Four-Equation System

Problem: The following overdetermined system has 4 equations and 3 unknowns. Find the least squares solution.

$a_0 + 2a_1 + 4a_2 = 3$

$a_0 + 3a_1 + 9a_2 = 5$

$a_0 + 5a_1 + 25a_2 = 12$

$a_0 + 6a_1 + 36a_2 = 15$

Step 1 — Identify the coefficient matrix and right-hand side

$$A = \begin{bmatrix} 1 & 2 & 4 \\ 1 & 3 & 9 \\ 1 & 5 & 25 \\ 1 & 6 & 36 \end{bmatrix}, \qquad b = \begin{bmatrix} 3 \\ 5 \\ 12 \\ 15 \end{bmatrix}$$

$A$ is $4 \times 3$. We cannot solve directly — apply the normal equations.

Step 2 — Form $A^T A$ and $A^T b$

$$A^T A = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 2 & 3 & 5 & 6 \\ 4 & 9 & 25 & 36 \end{bmatrix} \begin{bmatrix} 1 & 2 & 4 \\ 1 & 3 & 9 \\ 1 & 5 & 25 \\ 1 & 6 & 36 \end{bmatrix}$$

The $3 \times 4$ matrix multiplied by the $4 \times 3$ matrix yields a $3 \times 3$ matrix:

$$A^T A = \begin{bmatrix} 4 & 16 & 74 \\ 16 & 74 & 376 \\ 74 & 376 & 2018 \end{bmatrix}$$ $$A^T b = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 2 & 3 & 5 & 6 \\ 4 & 9 & 25 & 36 \end{bmatrix} \begin{bmatrix} 3 \\ 5 \\ 12 \\ 15 \end{bmatrix} = \begin{bmatrix} 35 \\ 171 \\ 879 \end{bmatrix}$$

The normal equations:

$$\begin{bmatrix} 4 & 16 & 74 \\ 16 & 74 & 376 \\ 74 & 376 & 2018 \end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \\ a_2 \end{bmatrix} = \begin{bmatrix} 35 \\ 171 \\ 879 \end{bmatrix}$$

Step 3 — Apply Gaussian elimination

Write the augmented matrix:

$$\left[\begin{array}{ccc|c} 4 & 16 & 74 & 35 \\ 16 & 74 & 376 & 171 \\ 74 & 376 & 2018 & 879 \end{array}\right]$$

Apply $R_2 \leftarrow R_2 - \dfrac{16}{4}\,R_1$ and $R_3 \leftarrow R_3 - \dfrac{74}{4}\,R_1$:

$$\left[\begin{array}{ccc|c} 4 & 16 & 74 & 35 \\ 0 & 10 & 80 & 31 \\ 0 & 80 & 649 & 231.5 \end{array}\right]$$

Apply $R_3 \leftarrow R_3 - \dfrac{80}{10}\,R_2$:

$$\left[\begin{array}{ccc|c} 4 & 16 & 74 & 35 \\ 0 & 10 & 80 & 31 \\ 0 & 0 & 9 & -16.5 \end{array}\right]$$

Step 4 — Back substitution

From row 3:

$$9a_2 = -16.5 \implies a_2 = -\frac{16.5}{9} \approx -1.833$$

From row 2:

$$\begin{aligned} 10a_1 + 80a_2 & = 31 \\ 10a_1 & = 31 - 80(-1.833) \\ & = 31 + 146.67 \\ & = 177.67 \\ a_1 & \approx 17.767 \end{aligned}$$

From row 1:

$$\begin{aligned} 4a_0 + 16a_1 + 74a_2 & = 35 \\ 4a_0 & = 35 - 16(17.767) - 74(-1.833) \\ & = 35 - 284.27 + 135.67 \\ & = -113.6 \\ a_0 & \approx -28.4 \end{aligned}$$ $$a_0 \approx -28.4$$

Step 5 — Solution

$$\boxed{a_0 \approx -28.4, \qquad a_1 \approx 17.77, \qquad a_2 \approx -1.83}$$