An Introduction to Optimization, 4th Edition

CHAPTER 12

SOLVING LINEAR EQUATIONS

12.1 Least-Squares Analysis

Consider a system of linear equations

where A ^m×n, b ^m, m ≥ n, and rank A = n. Note that the number of unknowns, n, is no larger than the number of equations, m. If b does not belong to the range of A, that is, if b ∉ (A), then this system of equations is said to be inconsistent or overdetermined. In this case there is no solution to the above set of equations. Our goal then is to find the vector (or vectors) x minimizing ||Ax − b||². This problem is a special case of the nonlinear least-squares problem discussed in Section 9.4.

Let x* be a vector that minimizes ||Ax − b||²; that is, for all x ⁿ,

We refer to the vector x* as ...