Least Squares

When a system of equations has more equations than unknowns, no exact solution typically exists. The least squares method finds the best approximate solution by minimizing the total squared error between the left and right-hand sides. This chapter covers two complementary approaches: the normal equations (derived by multiplying both sides by $A^T$) and QR decomposition (which uses an orthonormal factorization to solve the same problem with better numerical properties).

---

Learning Objectives

By the end of this chapter you should be able to:

1. Recognize an overdetermined system and explain why a direct solution is generally not possible.
2. Define the residual $r_i = b_i - (Ax)_i$ and state what quantity the least squares method minimizes.
3. Derive the normal equations $A^T A x = A^T b$ by multiplying both sides of $Ax = b$ by $A^T$.
4. Set up and solve the normal equations for a polynomial fitting problem using either an inverse matrix or Gaussian elimination.
5. Define orthogonality ($x^T y = 0$) and normality ($x^T x = 1$) and verify that a given set of vectors is orthonormal.
6. State the Kronecker delta and use it to express orthonormality compactly.
7. Describe the QR decomposition $A = QR$ and explain the role of $Q$ and $R$.
8. Apply the Gram-Schmidt process to compute $Q$ from the columns of $A$.
9. Derive the reduced system $Rx = Q^T b$ and solve it by back substitution.
10. Prove that $Q^T Q = I$ and that the Gram-Schmidt process produces $A = QR$.

---

Chapter Sections

#	Section	Key Concepts
1	Why Least Squares	Overdetermined systems, residuals, minimizing squared error, best-fit line
2	Normal Equations	Deriving $A^T A x = A^T b$, polynomial fitting examples, Gaussian elimination
3	Orthonormality	Orthogonality, normality, Kronecker delta, verification
4	QR Decomposition	$A = QR$, Gram-Schmidt process, derivation of $Rx = Q^T b$, proofs
5	QR Decomposition: Worked Example	Full step-by-step QR solution of a polynomial fitting problem