# QR Factorization for Solving Least Squares

By solving Least Squares, we use $RX = Q^Tb$

What's the benefit for solving least squares using QR factorization instead of solving the normal equations? and Why?

QR factorization method is more stable because it avoids forming $A^TA$

Example: a ${3 \times 2}$ matrix with 'almost linearly dependent' columns

$A = \begin{bmatrix} 1 & -1 \\ 0 & 10^{-5} \\ 0 & 0 \\ \end{bmatrix}$ , $\,\,\,\,\,\,\,\,\,\,b = \begin{bmatrix} 0 \\ 10^{-5} \\ 1 \\ \end{bmatrix}$

round intermediate results to 8 significant decimal digits

Method 1: from $A^TA$ and solve normal equations

$A^TA = \begin{bmatrix} 1 & -1 \\ -1 & 1+10^{-10} \\ \end{bmatrix}\to \begin{bmatrix} 1 & -1 \\ -1 & 1 \\ \end{bmatrix}$, $\,\,\,\,\,\,\,\,\,\,A^Tb = \begin{bmatrix} 0 \\ 10^{-10} \\ \end{bmatrix}$

after rounding ,the $A^TA$ is singular ,hence method fails.

Method 2: QR factorization of A is

$Q = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 0 & 0 \\ \end{bmatrix}$ , $\,\,\,\,\,\,\,\,\,\,R= \begin{bmatrix} 1 & -1\\ 0 & 10^{-5} \\ \end{bmatrix}$

rounding does not change any values

Lest squares lecture