TABLE OF CONTENTS Given an m-by- n matrix A and an m-by-1 vector b, the linear least squares problem is to find an n-by-1 vector x minimizing Ax ? b 2. If m = n and A is nonsingular, the answer is simply x = A ?1 b. But if m > n so that we have more equations than unknowns, the problem is called overdetermined, and generally no x satisfies Ax = b exactly. One occasionally encounters the underdetermined problem, where m < n, but we will concentrate on the more common overdetermined case.
This chapter is organized as follows. The rest of this introduction describes three applications of least squares problems, to curve fitting, to statistical modeling of noisy data, and to geodetic modeling. Section 3.2 discusses three standard ways to solve the least squares problem: the normal equations, the QR decomposition, and the singular value decomposition (SVD). We will frequently use the SVD as a tool in later chapters, so we derive several of its properties (although algorithms for the SVD are left to Chapter 5). Section 3.3 discusses perturbation theory for least squares problems, and section 3.4 discusses the implementation details and roundoff error analysis of our main method, QR decomposition. The roundoff analysis applies to many algorithms using orthogonal matrices, including many algorithms for eigenvalues...
