Bsrgvty

I need to solve $Ax=b$ in lots of ways using QR decomposition.

$$A = beginbmatrix
1 & 1 \
-1 & 1 \
1 & 2
endbmatrix, b = beginbmatrix
1 \
0 \
1
endbmatrix$$

This is an overdetermined system. That is, it has more equations than needed for a unique solution.

I need to find $min ||Ax-b||$. How should I solve it using QR?

I know that QR can be used to reduce the problem to
$$Vert Ax - b Vert = Vert QRx - b Vert = Vert Rx - Q^-1b Vert.$$

but what do I do after this?

The most straightforward way I know is to pass through the normal equations:

$$A^T A x = A^T b$$

and substitute in the $QR$ decomposition of $A$ (with the convention $Q in mathbbR^m times n,R in mathbbR^n times n$). Thus you get

$$R^T Q^T Q R x = R^T Q^T b.$$

But $Q^T Q=I_n$. (Note that in this convention $Q$ isn't an orthogonal matrix, so $Q Q^T neq I_m$, but this doesn't matter here.) Thus:

$$R^T R x = R^T Q^T b.$$

If $A$ has linearly independent columns (as is usually the case with overdetermined systems), then $R^T$ is injective, so by multiplying both sides by the left inverse of $R^T$ you get

$$Rx=Q^T b.$$

This system is now easy to solve numerically.

For numerical purposes it's important that the removal of $Q^T Q$ and $R^T$ from the problem is done analytically, and in particular $A^T A$ is never constructed numerically.

Note that $Rx$ has the form
$$Rx = beginbmatrix y_1 \ y_2 \ 0endbmatrix $$
, so if $$ Q^-1b = beginbmatrix z_1 \ z_2 \ z_3endbmatrix$$
then $|| Rx - Q^-1b||$ will be minimal for $y_1 = z_1$, $y_2=z_2$. This set of equation is no longer overdetermined.

Using matrix notation, if tou write $R = beginbmatrix R_1 \ 0endbmatrix$ and intoduce $P=beginbmatrix1 & 0 & 0 \ 0 & 1& 0endbmatrix$, then you have
$$ R_1x = PQ^-1b$$
$$ x = (R_1)^-1PQ^-1b$$