\documentclass[twoside]{article}

\usepackage{palatino}
\usepackage{camnum}

\def\va {\MM{a}}  
\def\vu {\MM{u}}  
\def\vv {\MM{v}}  
\def\vw {\MM{w}}  
\def\vx {\MM{x}}  

\def\gO {\Omega}

\def\T {\CC{T}}

\def\R {\BB{R}}
\def\V {\BB{V}}

\textheight=21.5cm
\textwidth=15cm
\topmargin=0cm
\oddsidemargin=0.5cm
\evensidemargin=0.5cm
\parindent=0pt
\parskip=6pt

\setcounter{section}{4}
\setcounter{subsection}{5}
\setcounter{equation}{0}

\begin{document}
\begin{center}
  {\large \textbf{Mathematical Tripos Part IB: Easter 2001}}

  {\Large \textbf{Numerical Analysis -- Lecture
      6\footnote{Corrections and suggestions to these notes should
        be emailed to \texttt{a.shadrin@damtp.cam.ac.uk}. All handouts
        are available on the WWW at the URL 
        \texttt{http://www.damtp.cam.ac.uk/user/na/PartIB/Handouts.html}.}}}
\end{center}

{\bf The Givens algorithm.} Given an $m\times n$ matrix $A$,
one uses the Givens rotations, 
$$
    \gO^{[1,2]},\ldots,\gO^{[1,m]}, \qquad 
    \gO^{[2,3]},\ldots,\gO^{[2,m]}, \qquad 
    \gO^{[3,4]},\ldots,\gO^{[3,m]}, \qquad \ldots
$$
and so on, to annihilate the subdiagonal elements of the resulting
matrices in each column successively.  
The final matrix is upper triangular, i.e., the required matrix $R$.

{\bf The cost.} There are less than $mn$ rotations and each rotation
replaces two rows by their linear combinations, hence the total cost
is $\O{mn^2}$.

If we wish to obtain explicitly an orthogonal $Q$ s.t.\ $A=QR$ then we
commence by letting $\Omega$ be the $m\times m$ unit matrix and, each
time $A$ is premultiplied by $\Omega^{[p,q]}$, we also premultiply
$\Omega$ by the same rotation. Hence the final $\Omega$ is the product
of all the rotations, in correct order, and we let $Q=\Omega^{\CC{T}}$. The
extra cost is $\O{m^2n}$. However, in most applications we don't need
$Q$ but, instead, just the action of $Q^{\CC{T}}$ on a given vector
(recall: solution of linear systems!). This can be accomplished by
multiplying the vector by successive rotations, the cost being $\O{mn}$.

\subsection{Householder transformations}

Let $\MM{u}\in\BB{R}^m\setminus\{\MM{0}\}$. The $m\times m$ matrix
$$
   H = I-2\frac{\MM{u}\MM{u}^{\CC{T}}}{\|\MM{u}\|^2}
$$
is called a {\em Householder transformation\/} 
or a {\em Householder reflection\/}. 
Since 
$$
   H\vu = -\vu, \qquad H\vv = \vv \quad \mbox{if}\quad \vu^\T\vv = 0,
$$
this transformation reflects any vector $\vx\in\R^n$ in
the $(n-1)$-dimensional hyperplane spanned by the vectors orthogonal to
$\vu$.

Each such matrix $H$ is symmetric and orthogonal.
The latter follows because reflection leaves the Eucleadian distance 
invariant, or by direct calculation
$$
\left(I-2\frac{\MM{u}\MM{u}^{\CC{T}}}{\|\MM{u}\|^2}\right)^{\CC{T}}
\left(I-2\frac{\MM{u}\MM{u}^{\CC{T}}}{\|\MM{u}\|^2}\right)=
\left(I-2\frac{\MM{u}\MM{u}^{\CC{T}}}{\|\MM{u}\|^2}\right)^2=I
  -4\frac{\MM{u}\MM{u}^{\CC{T}}}{\|\MM{u}\|^2}
  +4\frac{\MM{u}(\MM{u}^{\CC{T}}\MM{u})\MM{u}^{\CC{T}}}{\|\MM{u}\|^4}=I.
$$
Householder transformations offer an alternative to Given rotations in the
calculation of a QR factorization.

{\bf Deriving the first column of $\MM{R}$.} Our goal is to multiply an
$m\times n$ matrix $A$ by a sequence of Householder transformations so that
each product induces zeros under the diagonal in an entire
successive column. To start with, we seek a reflection that transforms
the first nonzero column of $A$ to a multiple of $\MM{e}_1$.

Let $\MM{a}\in\BB{R}^m$ be the first nonzero column of $A$. We wish to
choose $\MM{u}\in\BB{R}^m$ s.t.\ the bottom $m-1$ entries of
$$\left(I-2\frac{\MM{u}\MM{u}^{\CC{T}}}{\|\MM{u}\|^2}\right)\MM{a}=\MM{a}
-2\frac{\MM{u}^{\CC{T}}\MM{a}}{\|\MM{u}\|^2}\MM{u}$$
vanish and, in  addition, we normalise $\MM{u}$ so that
$2\MM{u}^{\CC{T}}\MM{a}=\|\MM{u}\|^2$ (recall that
$\MM{a}\neq\MM{0}$). Therefore $u_i=a_i$, $i=2,\ldots,m$ and the
normalisation implies that 
$$2u_1a_1+2\sum_{i=2}^m a_i^2=u_1^2+\sum_{i=2}^m a_i^2 \quad
\Rightarrow \quad u_1^2-2u_1a_1+a_1^2-\sum_{i=1}^m a_i^2=0
\quad\Rightarrow\quad u_1=a_1\pm\|\MM{a}\|.$$
It is usual to let the sign be the same as the sign of $a_1$, since
$\|\MM{u}\|\ll1$ might lead to a division by a tiny number, hence to
numerical difficulties. 

For large $m$ we do not execute explicit matrix multiplication.
Instead, to calculate 
$$\left(I-2\frac{\MM{u}\MM{u}^{\CC{T}}}{\|\MM{u}\|^2}
\right)A=A-2\frac{\MM{u}(\MM{u}^{\CC{T}}A)}{\|\MM{u}\|^2},$$
we first
evaluate $\MM{w}^{\CC{T}}:=\MM{u}^{\CC{T}}A$, subsequently forming
$A-\frac{2}{\|\MM{u}\|^2} \MM{u}\MM{w}^{\CC{T}}$.

{\bf Subsequent columns of $\MM{R}$.} 
Suppose that the Householder transformation has been 
applied $k-1$ times, so that the first $k-1$ columns of the
resulting matrix $\tilde A$ have an upper triangular
form. Let $\va$ be the $k$-th column of $\tilde A$.
By the next reflection we want annihilate
the $k+1,\ldots,m$ components $\va$, however,
leaving the previous columns as they are.
So, we define the next $\vu$ as
$$
\textstyle
   u_i = 0, \quad i < k, \qquad
   u_k=a_k\pm \left(\sum_{i=k}^m a_i^2\right)^{1/2}, \qquad 
   u_i = a_i, \quad i > k.
$$
Due to its zero components, such a $\vu$ is orthogonal
to the previous $k-1$ columns of $\tilde A$, hence they remain invariant
under reflection (as well as the first $k-1$ rows of $\tilde A$).
The bottom $m-k$ component of $H\va$ will vanish
due to the computations given above 

{\bf The Householder method.} We process columns of $A$ in sequence, in
each stage premultiplying a current $A$ by the requisite Householder
transformation. The end result is an upper triangular matrix $R$.


{\bf Example}
$$A=\left[\begin{array}{rrr}2&4&7\\0&3&-1\\0&0&2\\0&0&1\\0&0&-2
\end{array}\right]\quad\Rightarrow\quad \MM{u}=\left[\begin{array}{r}
0\\0\\5\\1\\-2 \end{array}\right] \quad\Rightarrow\quad
\left(I-2\frac{\MM{u}\MM{u}^{\CC{T}}}{\|\MM{u}\|^2}\right)A =\left[
\begin{array}{rrr}2&4&7\\0&3&-1\\0&0&-3\\0&0&0\\0&0&0\end{array}
\right].$$

{\bf Calculation of $Q$.} If the matrix $Q$ is required in an explicit
form, set $\Omega=I$ initially and, for each successive reflection,
replace $\Omega$ by
$$\left(I-2\frac{\MM{u}\MM{u}^{\CC{T}}}{\|\MM{u}\|^2}\right)\Omega
=\Omega-\frac{2}{\|\MM{u}\|^2} \MM{u}(\MM{u}^{\CC{T}}\Omega).$$
As in the case of Givens rotations, by the end of the computation,
$Q=\Omega^{\CC{T}}$. However, if we require just the vector
$\MM{c}=Q^{\CC{T}}\MM{b}$, say, rather than the matrix $Q$, then we set
initially $\MM{c}=\MM{b}$ and in each stage replace $\MM{c}$ by
$$\left(I-2\frac{\MM{u}\MM{u}^{\CC{T}}}{\|\MM{u}\|^2}\right)\MM{c}=\MM{c}
-2\frac{\MM{u}^{\CC{T}}\MM{c}}{\|\MM{u}\|^2}\MM{u}.$$ 

{\bf Deciding between Givens and Householder transformations} If $A$ is
dense, it is in general more convenient to use Householder reflections.
Givens rotations come into their own, however, when $A$ has many
leading zeros in its rows. In an extreme case, if an $n\times n$
matrix $A$ consists of zeros underneath the first subdiagonal, they
can be `rotated  away' in just $n-1$ Givens rotations, at the cost of 
$\O{n^2}$ operations!

\end{document}