While the normal equation approach (\( A^T A \hat{x} = A^T B \)) provides a direct way to solve least squares problems, computing the matrix product \( A^T A \) can sometimes worsen numerical stability and round-off errors. To bypass this, linear algebra relies on QR Decomposition as a more stable, orthogonal alternative.
By factoring matrix \( A \) into an orthogonal matrix \( Q \) and an upper triangular matrix \( R \) (such that \( A = QR \)), the least squares problem simplifies significantly. As shown in Linear Algebra and its Applications, the approximate solution \( \hat{x} \) can be found directly from the equation:
where \( Q^T \) is the transpose of matrix \( Q \) and \( R \) is an upper triangular matrix. Because \( R \) is upper triangular, this system can be solved very efficiently using back-substitution without ever needing to compute \( A^T A \).
Use the QR decomposition to solve the least squares problem related to the inconsistent system \( Ax = B \) with:
$$ A = \begin{bmatrix} 2 & 0 \\ 0 & 1 \\ 1 & 2 \end{bmatrix} \quad \text{and} \quad B = \begin{bmatrix} 1 \\ 0 \\ 3 \end{bmatrix} $$Step 1: Find the Orthogonal Matrix Q
Use the Gram-Schmidt process to find the orthogonal matrix \( Q \) and decompose matrix \( A \) into \( A = QR \).
$$ Q = \begin{bmatrix} \frac{2\sqrt{5}}{5} & \frac{-4\sqrt{105}}{105} \\ 0 & \frac{\sqrt{105}}{21} \\ \frac{\sqrt{5}}{5} & \frac{8\sqrt{105}}{105} \end{bmatrix} $$Step 2: Calculate Matrix R
Multiply both sides of \( A = QR \) by \( Q^T \) (the transpose of \( Q \)). Since \( Q \) is orthogonal, \( Q^T Q = I \), which simplifies the equation to \( R = Q^T A \).
First, write the transpose of \( Q \):
$$ Q^T = \begin{bmatrix} \frac{2\sqrt{5}}{5} & 0 & \frac{\sqrt{5}}{5} \\ \frac{-4\sqrt{105}}{105} & \frac{\sqrt{105}}{21} & \frac{8\sqrt{105}}{105} \end{bmatrix} $$Now calculate \( R \):
$$ R = Q^T A = \begin{bmatrix} \frac{2\sqrt{5}}{5} & 0 & \frac{\sqrt{5}}{5} \\ \frac{-4\sqrt{105}}{105} & \frac{\sqrt{105}}{21} & \frac{8\sqrt{105}}{105} \end{bmatrix} \begin{bmatrix} 2 & 0 \\ 0 & 1 \\ 1 & 2 \end{bmatrix} = \begin{bmatrix} \sqrt{5} & \frac{2}{\sqrt{5}} \\ 0 & \sqrt{\frac{21}{5}} \end{bmatrix} $$Step 3: Calculate \( Q^T B \)
$$ Q^T B = \begin{bmatrix} \frac{2\sqrt{5}}{5} & 0 & \frac{\sqrt{5}}{5} \\ \frac{-4\sqrt{105}}{105} & \frac{\sqrt{105}}{21} & \frac{8\sqrt{105}}{105} \end{bmatrix} \begin{bmatrix} 1 \\ 0 \\ 3 \end{bmatrix} = \begin{bmatrix} \sqrt{5} \\ \frac{4\sqrt{5}}{\sqrt{21}} \end{bmatrix} $$Step 4: Solve \( R \hat{x} = Q^T B \)
Substitute \( R \) and \( Q^T B \) into the system:
$$ \begin{bmatrix} \sqrt{5} & \frac{2}{\sqrt{5}} \\ 0 & \sqrt{\frac{21}{5}} \end{bmatrix} \hat{x} = \begin{bmatrix} \sqrt{5} \\ \frac{4\sqrt{5}}{\sqrt{21}} \end{bmatrix} $$Because \( R \) is an upper triangular matrix, we can quickly solve this using back-substitution to obtain the final approximate solution:
$$ \hat{x} = \begin{bmatrix} \frac{13}{21} \\ \frac{20}{21} \end{bmatrix} $$Use the QR decomposition to solve the least squares problem related to the inconsistent system \( Ax = B \) with:
$$ A = \begin{bmatrix} 1 & 0 & 1 \\ 2 & 0 & 0 \\ 0 & -1 & 1 \\ 0 & -2 & 0 \end{bmatrix} \quad \text{and} \quad B = \begin{bmatrix} 2 \\ 3 \\ 4 \\ 7 \end{bmatrix} $$Step 1: Find the Orthogonal Matrix Q
Use the Gram-Schmidt process on matrix \( A \) to find the orthogonal matrix \( Q \).
$$ Q = \begin{bmatrix} \frac{\sqrt{5}}{5} & 0 & \frac{\sqrt{10}}{5} \\ \frac{2\sqrt{5}}{5} & 0 & -\frac{\sqrt{10}}{10} \\ 0 & -\frac{\sqrt{5}}{5} & \frac{\sqrt{10}}{5} \\ 0 & -\frac{2\sqrt{5}}{5} & -\frac{\sqrt{10}}{10} \end{bmatrix} $$Step 2: Calculate Matrix R
Using the property \( R = Q^T A \), we first determine the transpose \( Q^T \):
$$ Q^T = \begin{bmatrix} \frac{\sqrt{5}}{5} & \frac{2\sqrt{5}}{5} & 0 & 0 \\ 0 & 0 & -\frac{\sqrt{5}}{5} & -\frac{2\sqrt{5}}{5} \\ \frac{\sqrt{10}}{5} & -\frac{\sqrt{10}}{10} & \frac{\sqrt{10}}{5} & -\frac{\sqrt{10}}{10} \end{bmatrix} $$Now calculate \( R \):
$$ R = Q^T A = \begin{bmatrix} \frac{\sqrt{5}}{5} & \frac{2\sqrt{5}}{5} & 0 & 0 \\ 0 & 0 & -\frac{\sqrt{5}}{5} & -\frac{2\sqrt{5}}{5} \\ \frac{\sqrt{10}}{5} & -\frac{\sqrt{10}}{10} & \frac{\sqrt{10}}{5} & -\frac{\sqrt{10}}{10} \end{bmatrix} \begin{bmatrix} 1 & 0 & 1 \\ 2 & 0 & 0 \\ 0 & -1 & 1 \\ 0 & -2 & 0 \end{bmatrix} = \begin{bmatrix} \sqrt{5} & 0 & \frac{1}{\sqrt{5}} \\ 0 & \sqrt{5} & -\frac{1}{\sqrt{5}} \\ 0 & 0 & \frac{2\sqrt{2}}{\sqrt{5}} \end{bmatrix} $$Step 3: Calculate \( Q^T B \)
$$ Q^T B = \begin{bmatrix} \frac{\sqrt{5}}{5} & \frac{2\sqrt{5}}{5} & 0 & 0 \\ 0 & 0 & -\frac{\sqrt{5}}{5} & -\frac{2\sqrt{5}}{5} \\ \frac{\sqrt{10}}{5} & -\frac{\sqrt{10}}{10} & \frac{\sqrt{10}}{5} & -\frac{\sqrt{10}}{10} \end{bmatrix} \begin{bmatrix} 2 \\ 3 \\ 4 \\ 7 \end{bmatrix} = \begin{bmatrix} \frac{8}{\sqrt{5}} \\ -\frac{18}{\sqrt{5}} \\ \sqrt{\frac{2}{5}} \end{bmatrix} $$Step 4: Solve \( R \hat{x} = Q^T B \)
Set up the system of equations by substituting the calculated values:
$$ \begin{bmatrix} \sqrt{5} & 0 & \frac{1}{\sqrt{5}} \\ 0 & \sqrt{5} & -\frac{1}{\sqrt{5}} \\ 0 & 0 & \frac{2\sqrt{2}}{\sqrt{5}} \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} \frac{8}{\sqrt{5}} \\ -\frac{18}{\sqrt{5}} \\ \sqrt{\frac{2}{5}} \end{bmatrix} $$Solving this triangular system gives us:
\( x_1 = \frac{3}{2} \), \( x_2 = -\frac{7}{2} \), \( x_3 = \frac{1}{2} \)
The final approximate solution is:
$$ \hat{x} = \begin{bmatrix} \frac{3}{2} \\ -\frac{7}{2} \\ \frac{1}{2} \end{bmatrix} $$