\documentclass[twoside]{article}

\usepackage{palatino}
\usepackage{camnum}

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

\newcommand{\gap}{\hspace*{8pt}}

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

  {\Large \textbf{Numerical Analysis -- Exercise Sheet
        1\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}

1. \gap Calculate {\em all\/} LU factorizations of the matrix
$$A = \left[
  \begin{array}{rrrr} 
    10&6&-2&1\\
    10&10&-5&0\\
    -2&2&-2&1\\
    1&3&-2&3
  \end{array}\right],$$
where all diagonal elements of $L$ are one. By using one
of these factorizations, find {\em all\/} solutions of the equation
$A\MM{x} =\MM{b}$ \ where $\MM{b}^{\CC{T}}=[\begin{array}{cccc}-2 & 0 &
2 & 1 \end{array}] $.

2.  \gap Let $A$ be a real $n\times n$ matrix that has the 
factorization $A=LU$, where $L$ is lower triangular with ones on its 
diagonal and $U$ is upper triangular. Prove that, for every integer
$k\in\{1,2,\ldots,n\}$, the first $k$ rows of $U$ span the same 
space as the first  $k$ rows of $A$. Prove also that the first $k$
columns of $A$ are in the $k$-dimensional subspace that is
spanned by the first $k$ columns of  $L$. Hence deduce that no LU
factorization of the given form exists if we have ${\rm
rank}\,H_k<{\rm rank}\,B_k$, where $H_k$ is the leading $k\times k$
submatrix of $A$ and where $B_k$ is the $n\times k$ matrix whose
columns are the first $k$ columns of $A$.

3. \gap By using column pivoting if necessary to exchange rows of $A$, 
an LU factorization of a real $n\times n$ matrix $A$ is calculated,
where $L$ has ones on its diagonal, and where the moduli of the 
off-diagonal elements of $L$ do not exceed one. Let $\alpha$ be the 
largest of the moduli of the elements of $A$. Prove by induction on
$i$ that elements of $U$ satisfy the condition
$|U_{i,j}|\leq2^{i-1}\alpha$. Then construct $2\times2$ and $3\times3$
nonzero matrices $A$ that yield $|U_{2,2}|=2\alpha$ and
$|U_{3,3}|=4\alpha$ respectively.

4. \gap Calculate the Cholesky factorization of the matrix
$$\left[
  \begin{array}{cccccc}
    1&1&0&0&0&0\\
    1&2&1&0&0&0\\
    0&1&3&1&0&0\\
    0&0&1&4&1&0\\
    0&0&0&1&5&1\\
    0&0&0&0&1&\lambda 
  \end{array}\right].$$
Deduce from the factorization the value of $ \lambda $ that makes the matrix
singular. Also find this value of $ \lambda $ by seeking the vector in the
null-space of the matrix whose first component is one.

5. \gap Let $A$ be an $ n \times n $ nonsingular band
matrix that satisfies the condition $ A_{i,j} = 0$
if $ |i-j| > r $, where $ r $ is small, and let Gaussian
elimination {\em with column pivoting\/} be used to solve
$ A\MM{x} =\MM{b} $. Identify all the coefficients of the
intermediate equations that can become nonzero. Hence deduce that the
total number of additions and  multiplications of the complete
calculation can be bounded by a constant multiple of $ nr^2 $.

6. \gap The iteration $\MM{x}_{k+1} = H\MM{x}_k+\MM{b}$ is applied
for $ k=0,1,\dots $, where $ H $ is the real $2\times2$ matrix
$$H=\left[\begin{array}{cc}\alpha&\gamma\\0&\beta\end{array}\right],$$
with $\gamma$ large and $ |\alpha|<1$,  $ |\beta|<1 $. Calculate the elements 
of $ H^k $ and show that they tend to zero as $ k \rightarrow \infty $. 
Further, establish the equation $\MM{x}_k-\MM{x}^* =
H^k(\MM{x}_0-\MM{x}^*)$, where $\MM{x}^*$ is defined by
$\MM{x}^*=H\MM{x}^*+\MM{b}$. Thus deduce that the sequence
$\{\MM{x}_k\}_{k=0}^\infty$ converges to $\MM{x}^*$. 

7. \gap For some choice of $\MM{x}_0$ the iterative method
$$\left[
  \begin{array}{ccc}
    1&1&1\\
    0&1&1\\
    0&0&1\end{array}
\right] \MM{x}_{k+1}+\left[
  \begin{array}{ccc}
    0&0&0\\
    \xi&0&0\\
    \eta &\zeta&0
  \end{array}\right] \MM{x}_k=\MM{b}$$
is applied for $ k=0,1,\dots $, in order to solve the linear system
$$\left[
  \begin{array}{ccc}
    1&1&1\\
    \xi&1&1\\
    \eta&\zeta&1
  \end{array}\right]\MM{x}=\MM{b},$$
where $ \xi $, $\eta$ and $ \zeta$ are constants. Find all values of
the constants such that the sequence $\{\MM{x}_k\}_{k=0}^\infty$ converges
for every $\MM{x}_0 $ and $\MM{b}$. Give an example of
nonconvergence when $ \xi = \eta = \zeta = -1 $. Is the solution
always found in at most two iterations when $\xi=\zeta=0$?

8. \gap Let $\MM{a}_1$, $\MM{a}_2$ and $\MM{a}_3$ denote the
columns of the matrix
$$A=\left[
  \begin{array}{ccc}
    6&6&1\\
    3&6&1\\
    2&1&1
  \end{array}\right].$$
Apply the Gram--Schmidt procedure to $A$, which generates orthonormal
vectors $\MM{q}_1,\MM{q}_2$ and $\MM{q}_3$. Note that this calculation provides
real numbers $ R_{k,\ell} $ such that $\MM{a}_k=\sum_{\ell=1}^k R_{k,\ell} 
\MM{q}_\ell$, $k=1,2,3$. Hence express $A$ as the product $A=QR$, 
where $Q$ and $R$ are orthogonal and upper-triangular matrices
respectively.

9. \gap Calculate the QR factorization of the matrix of Exercise 8
by using three Givens rotations. Explain why the initial rotation can
be any one of the three types $ \Omega^{(1,2)},~\Omega^{(1,3)} $ and $
\Omega^{(2,3)} $. Prove that the final factorization is independent of
this initial choice in exact arithmetic, provided that we satisfy the
condition that in each row of $ R $ the leading nonzero element is
positive.

10. \gap Let $A$ be an $n\times n$ matrix, and for
$i=1,2,\ldots,n$ let $k(i)$ be the number of zero elements in the
$i$th row of $A$ that come before all nonzero elements in this
row and before the diagonal element $A_{i,i}$. Show that the QR
factorization of $A$ can be calculated by using at most
$\frac12 n(n-1)-\sum k(i)$ Givens rotations. Hence show that, if $A$
is an upper triangular matrix except that there are nonzero elements
in its first column, i.e.\ $A_{i,j}=0$ when $2\leq j<i\leq n$, then
its QR factorization can be calculated by using only $2n-3$
Givens rotations.

11. \gap Calculate the QR factorization of the matrix of Exercise 8
by using two Householder reflections. Show that, if this technique is
used to generate the  QR factorization of a general $n\times n$
matrix $A$, then the  computation can be organised so that the total
number of additions and  multiplications is bounded above by a
constant multiple of $n^3$.

12. \gap Let
$$A=\left[
  \begin{array}{rrrr}
    3&\ 4&7&-2\\
    5&\ 4&9&\ \,3\\
    1&-1&0&\ \,3\\
    1&-1&0&\ \,0
  \end{array}\right],\qquad\MM{b}=\left[ 
  \begin{array}{c}
    11\\29\\16\\10
  \end{array}\right].$$
Calculate the QR factorization of $A$ by using Householder reflections.
In this case $A$ is singular and you should choose $Q$ so that the
last row of $R$ is zero. Hence identify all the least squares
solutions of the inconsistent system $A\MM{x}=\MM{b}$, where we require
$\MM{x}$ to minimize  $\|A\MM{x}-\MM{b}\|_2$. Verify that all the
solutions give the same vector of residuals $A\MM{x}-\MM{b}$, and
that this vector is orthogonal to the columns of $A$. There is 
no need to calculate the elements of $Q$ explicitly.


\end{document}