Conditioning of the normal equations

Conditioning is particularly important when the normal equations are used. For a full-column-rank overdetermined system, the least-squares solution can be obtained by solving

$$\mathbf{A}^{\top}\mathbf{A}\mathbf{x} = \mathbf{A}^{\top}\mathbf{b}.$$ (1.42)

If

$$\mathbf{A} = \mathbf{U}\mathbf{\Sigma}\mathbf{V}^{\top},$$ (1.43)

then

$$\mathbf{A}^{\top}\mathbf{A} = \mathbf{V}\mathbf{\Sigma}^{\top}\mathbf{\Sigma}\mathbf{V}^{\top}.$$ (1.44)

The singular values of $\mathbf{A}^{\top}\mathbf{A}$ are therefore the squares of the singular values of $\mathbf{A}$. It follows that

$$\boxed{ \kappa_2(\mathbf{A}^{\top}\mathbf{A}) = \kappa_2(\mathbf{A})^2 }.$$ (1.45)

Forming the normal equations can therefore significantly worsen the conditioning of the problem. For this reason, as discussed in section 1.1, methods based on QR or SVD factorization are often preferred in practice, since they avoid explicitly forming the matrix $\mathbf{A}^{\top}\mathbf{A}$.