% FILE anton3QR.tex

\subsection*{The QR Decomposition}
The equation $A^T A\b x = A^T \b y$ associated with
the least-squares problem is almost always `ill-conditioned' -
meaning difficult to get good accuracy in SmallFloat calculation. This is dealt
with using $QR$-decomposition which says that any matrix $A$, not necessarily
square, can be factored $A=QR$ where $Q$ is orthogonal and $R$ is upper
triangular with nonnegative diagonal entries. 

%\begin{theorem} 
%\headq{THEOREM } 
\theoremNN{{\bf AR7 6.3.7} \it 
If $A$ is an $m\times n$ matrix with linearly independent
  columns, then $A$ can be decomposed into the product
    $$ A = QR $$
  of an $m\times n$ matrix $Q$ with orthonormal columns and a non-singular
  upper triangular matrix $R$.\par
  Hence, if $A$ is an invertible (square) matrix, then\quad $A=QR$\quad
  where $Q$ is orthogonal and $R$ is a non-singular upper triangular matrix.
} %\end{theorem}
\theoremNNEnd

[AR7] describes a  method of finding $QR$ factorisations
based on using Gram Schmidt.
(Code equivalent to that below, but in DERIVE,
is given in \cite{EJ}.)

\medskip
\begin{maple}
> with(linalg):
Warning: new definition for   norm
Warning: new definition for   trace
> qrfac:= proc(A,Q)
>     local n,Qcols,R,i;
>     n:= coldim(A);
>     Qcols:= GramSchmidt( [col(A,1..n)] );
>     Q:= transpose( matrix(Qcols) );
> #   Normalise Q by dividing each  col(Q,i)  by its norm.
>     for i from 1 to n do
>         Q:= mulcol( Q,i,1/norm(col(Q,i),2) )
>     od;
> #   Since  Q &* R = A  and  transpose(Q) &* Q = Id,
>     R:= evalm(transpose(Q)&*A);
> end:
> # AR7 Section 6.3 Example 8 p323 
> # Find the QR decomposition of the matrix
> A:= matrix([ [1,0,0],
>              [1,1,0],
>              [1,1,1] ]):
> R:= qrfac( A,'Q'):                                 print ( Q,R);

                  [      1/2         1/2  1/2             ]
                  [ 1/3 3     - 1/3 2    3          0     ]
                  [                                       ]
                  [      1/2        1/2  1/2          1/2 ]
                  [ 1/3 3      1/6 2    3      - 1/2 2    ],
                  [                                       ]
                  [      1/2        1/2  1/2         1/2  ]
                  [ 1/3 3      1/6 2    3       1/2 2     ]

                      [  1/2          1/2            1/2   ]
                      [ 3        2/3 3          1/3 3      ]
                      [                                    ]
                      [            1/2  1/2       1/2  1/2 ]
                      [   0   1/3 2    3     1/6 2    3    ]
                      [                                    ]
                      [                              1/2   ]
                      [   0         0           1/2 2      ]

> equal( A, evalm(Q&*R) );

                                      true

\end{maple}
\goodbreak

\noindent The $QR$ decomposition is important in least squares,
and in an algorithm -- the $QR$-algorithm -- for numerical approximation of
eigenvalues.
The connection with least squares is as follows.
\smallskip

\theoremNN{\it 
  Suppose $A$ is an $m\times n$ matrix with linearly independent columns.  Then
  the $QR$-decomposition $A=QR$ replaces the equation $A^T A\b x=A^T \b y$ by
    $$ R \b x = Q^T \b y$$
} %\end{theorem}
\theoremNNEnd

\medskip

We conclude this section with some remarks concerning
SmallFloat numerical calculation.
\begin{enumerate}
\item In finding the least squares solution of overdetermined
linear systems, the normal equations should not be formed
as correctly implemented use of the $QR$-factorisation is better.
\item In finding $QR$-factorisations in SmallFloat numeric
calculations one should not use the Gram Schmidt process
described above. In SmallFloat calculation,  a method based on
Householder transformations is much better.
See more advanced treatments of numerical linear algebra for
definitions and results.
\label{householder}
Code for the Householder transformation may be available
amongst the Worksheet supplements to these notes.
\end{enumerate}

%Algorithms for finding $QR$-factorisations are given in
%separate notes on Maple and numerical linear algebra.

\vfill
\eject
\endinput
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}
\end

