Question 1: Consider the least squares problem
\[
\min _{x}\|b-A x\|_{2}^{2}
\]
where
\[
A=\left(\begin{array}{cc}
1 & 1 \\
1 & 1 \\
1 & 1+\epsilon
\end{array}\right), \quad b=\left(\begin{array}{l}
2 \\
3 \\
2
\end{array}\right)
\]
where $\epsilon \in \mathbb{R}$.
(a) Find the normal equations and the exact least squares solution.
(b) Explain a good numerical algorithm to solve this problem. Explain why the suggested method is a good algorithm and give full details of each step of the algorithm.

Step 1 ：The least squares problem is given by \(\min _{x}\|b-A x\|_{2}^{2}\). The normal equations for this problem are given by \(A^{T}Ax = A^{T}b\).

Step 2 ：The matrix \(A\) is given by \(A=\left(\begin{array}{cc} 1 & 1 \ 1 & 1 \ 1 & 1+\epsilon \end{array}\right)\). So, \(A^{T}A = \left(\begin{array}{cc} 3 & 3+\epsilon \ 3+\epsilon & 3+2\epsilon+\epsilon^{2} \end{array}\right)\).

Step 3 ：The vector \(b\) is given by \(b=\left(\begin{array}{l} 2 \ 3 \ 2 \end{array}\right)\). So, \(A^{T}b = \left(\begin{array}{l} 7 \ 7+\epsilon \end{array}\right)\).

Step 4 ：Therefore, the normal equations are \(\left(\begin{array}{cc} 3 & 3+\epsilon \ 3+\epsilon & 3+2\epsilon+\epsilon^{2} \end{array}\right) x = \left(\begin{array}{l} 7 \ 7+\epsilon \end{array}\right)\).

Step 5 ：To solve this system of equations, we can use the method of substitution or elimination. However, due to the presence of \(\epsilon\), it is more convenient to use the method of substitution.

Step 6 ：From the first equation, we can express \(x_{1}\) in terms of \(x_{2}\) as \(x_{1} = \frac{7 - (3+\epsilon)x_{2}}{3}\).

Step 7 ：Substituting this into the second equation gives \((3+\epsilon)\left(\frac{7 - (3+\epsilon)x_{2}}{3}\right) + (3+2\epsilon+\epsilon^{2})x_{2} = 7+\epsilon\).

Step 8 ：Solving this equation for \(x_{2}\) gives \(x_{2} = \frac{21 - 9\epsilon - \epsilon^{2}}{9 + 6\epsilon + 2\epsilon^{2}}\).

Step 9 ：Substituting this back into the equation for \(x_{1}\) gives \(x_{1} = \frac{7 - (3+\epsilon)\left(\frac{21 - 9\epsilon - \epsilon^{2}}{9 + 6\epsilon + 2\epsilon^{2}}\right)}{3}\).

Step 10 ：Solving this equation for \(x_{1}\) gives \(x_{1} = \frac{21 - 9\epsilon - \epsilon^{2}}{9 + 6\epsilon + 2\epsilon^{2}}\).

Step 11 ：Therefore, the exact least squares solution is \(x = \left(\begin{array}{l} \frac{21 - 9\epsilon - \epsilon^{2}}{9 + 6\epsilon + 2\epsilon^{2}} \ \frac{21 - 9\epsilon - \epsilon^{2}}{9 + 6\epsilon + 2\epsilon^{2}} \end{array}\right)\).

Step 12 ：A good numerical algorithm to solve this problem is the QR decomposition. This method is good because it is numerically stable and efficient. The steps of the algorithm are as follows:

Step 13 ：1. Compute the QR decomposition of \(A\), i.e., express \(A\) as \(A = QR\), where \(Q\) is an orthogonal matrix and \(R\) is an upper triangular matrix.

Step 14 ：2. Solve the system \(Rx = Q^{T}b\) for \(x\). Since \(R\) is upper triangular, this can be done efficiently by back substitution.

Step 15 ：3. The solution \(x\) is the least squares solution to the problem.