Linear Algebra with Applications, 10th Edition

7.7 Least Squares Problems

In this section, we study computational methods for finding least squares solutions of overdetermined systems. Let A be an $m\times n$ matrix with $m\ge n$ and let $\mathbf{b}\in {\mathbb{\text{R}}}^m$. We consider some methods for computing a vector x that minimizes ${\Vert \mathbf{b}-A\mathbf{x}\Vert }_2^2$.

Normal Equations

We saw in Chapter 5 that if $\hat{\mathbf{x}}$ satisfies the normal equations

$$A^{T}A\mathbf{x}=A^T\mathbf{b}$$

then $\hat{\mathbf{x}}$ is a solution to the least squares problem. If A is of full rank (rank n), then $A^{T}A$ is nonsingular and hence the system will have a unique solution. Thus, if $A^{T}A$ is invertible, one possible method for solving the least squares problem is to form the normal equations and then solve them by Gaussian elimination. An algorithm for doing this would have two main parts.

1. Compute $B=A^{T}A$ and $\mathbf{c}=A^T\mathbf{b}$