4.3-final-2011¶
Final Exam, 2011 · Section 4.3: Least Squares Approximations Source: finalexam_2.pdf, p. 47
Problem¶
7 (11 pts.) The general equation of a circle in the plane has the form \(x^2 + y^2 + Cx + Dy + E = 0\). Suppose you are trying to fit \(n \geq 3\) distinct points \((x_i, y_i)\), \(i = 1, \dots, n\) to obtain a "best" least squares circle. It is reasonable to write a generally unsolvable equation \(Ax = b\).
(a) (7 pts.) Describe \(A\) and \(b\) clearly, indicating the number of rows and columns of \(A\) and the number of elements in \(b\).
(b) (4 pts.) When \(n = 3\) it is possible to describe when the equation is and is not solvable. You can use your geometric intuition, or a determinant area formula to describe when \(A\) is singular. Give a simple geometrical description. (We are looking for a specific word — so only a short answer will be accepted.)
Solution
(a) Substituting each point into the circle equation gives the system \[ \begin{bmatrix} x_1 & y_1 & 1 \\ x_2 & y_2 & 1 \\ \vdots & \vdots & \vdots \\ x_n & y_n & 1 \end{bmatrix} \begin{bmatrix} C \\ D \\ E \end{bmatrix} = \begin{bmatrix} -x_1^2 - y_1^2 \\ -x_2^2 - y_2^2 \\ \vdots \\ -x_n^2 - y_n^2 \end{bmatrix}. \] The matrix \(A\) has \(n\) rows and 3 columns, while \(b\) has \(n\) elements. (b) When \(n = 3\), \(A\) is the area matrix of the triangle formed by the three points. The equation is solvable exactly when the three points are not collinear: the triangle does not collapse, the area is nonzero, and the matrix \(A\) is invertible. (A circle is determined by three points as long as they are not collinear.)Keywords: least squares, circle fit, normal equations, collinear