4.3-final-2012-strang¶
Final Exam, 2012 (strang) · Section 4.3: Least Squares Approximations Source: finalexam_2.pdf, pp. 82-83
Problem¶
6 (12 pts.)
(a) Find the closest straight line \(y = Ct + D\) to the 5 points:
\[
(t, y) = (-2, 0), (-1, 0), (0, 1), (1, 1), (2, 1).
\]
(b) The word "closest" means that you minimized which quantity to find your line?
(c) If \(A^T A\) is invertible, what do you know about its eigenvalues and eigenvectors? (Technical point: Assume that the eigenvalues are distinct — no eigenvalues are repeated.)
Solution
(a) Inserting all points into the equation \(y = Ct + D\): \[ -2C + D = 0, \quad -C + D = 0, \quad D = 1, \quad C + D = 1, \quad 2C + D = 1. \] Written as a matrix system, \[ Ax = \begin{bmatrix} -2 & 1 \\ -1 & 1 \\ 0 & 1 \\ 1 & 1 \\ 2 & 1 \end{bmatrix} \begin{bmatrix} C \\ D \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 1 \\ 1 \\ 1 \end{bmatrix} = b. \] We solve the normal equations \(A^T A \hat{x} = A^T b\). We compute \[ A^T A = \begin{bmatrix} 10 & 0 \\ 0 & 5 \end{bmatrix}, \qquad A^T b = \begin{bmatrix} 3 \\ 3 \end{bmatrix}, \qquad (A^T A)^{-1} = \begin{bmatrix} 1/10 & 0 \\ 0 & 1/5 \end{bmatrix}. \] Thus finally \[ \begin{bmatrix} C \\ D \end{bmatrix} = \hat{x} = (A^T A)^{-1} A^T b = \begin{bmatrix} 3/10 \\ 3/5 \end{bmatrix}. \] So the closest line to the five points is \[ y = \frac{3}{10}t + \frac{3}{5}. \] (b) It means that the sum of squares deviation \(\|Ax - b\|^2\) was minimized. (c) Since \(A^T A\) is symmetric and \(x^T (A^T A) x = \|Ax\|^2 \ge 0\) always, it is positive semidefinite. If \(A^T A\) is invertible then \(N(A^T A) = \{0\}\), so 0 is not an eigenvalue. Hence: The eigenvalues of \(A^T A\) are positive (it is positive definite, which happens exactly when \(A\) has independent columns). By symmetry, eigenvectors belonging to different eigenvalues are orthogonal.Keywords: least squares, straight line fit, normal equations, positive definite