\documentclass[twoside]{article}

\usepackage{palatino}
\usepackage{camnum}

%\textheight=23.5cm
\textheight=25.0cm
\textwidth=15cm
\topmargin=-2cm
\oddsidemargin=0.5cm
\evensidemargin=0.5cm
\parindent=0pt
\parskip=6pt

\setcounter{section}{3}
\setcounter{subsection}{2}
\setcounter{equation}{5}

\begin{document}

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

  {\Large \textbf{Numerical Analysis -- Lecture
      4\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}


\subsection{Spectral radius and Gershgorin theorem}

How can one compute the spectral radius of a matrix?
The simplest tool for estimating the position of the eigenvalues is
the following theorem. 
%We employ the notation $\sigma(A)$ for 
%the set of all eigenvalues (the {\em spectrum}) of $A$.

{\bf Theorem [Gerschgorin].} Let $A$ be a $n\times n$ matrix 
(with real or complex coefficients).
Then all of its eigenvalues are contained in the union 
$\cup_{i=1}^n \Gamma_i$ where $\Gamma_i$'s are the circles in the complex plane
\begin{equation} \label{3.6}
\textstyle
%  \sigma(A) \subset \cup_{i=1}^n \Gamma_i, \qquad
    \Gamma_i 
= \{z \in \BB{C}: |z - a_{ii}| \le r_i\}, \quad
   r_i := \sum_{j=1,j\ne i}^n |a_{ij}|,
  \qquad i=1,\ldots,n.
\end{equation}

\hspace*{8pt}{\bf Proof.} Let $\lambda \in \BB{C}$ be an eigenvalue
of $A$, and let $\MM{w}$ be the corresponding eigenvector.
Let  $\MM{w}_i$ be the largest component in absolute value.
Consider the $i$-th equation of the relation $A\MM{w}=\lambda\MM{w}$:
$$
\textstyle
   a_{ii}\MM{w}_i + \sum_{j=1,j\ne i}^n a_{ij} \MM{w}_j = \lambda\MM{w}_i.
$$     
This implies the inequality
$$
\textstyle
  |\lambda - a_{ii}|\cdot|\MM{w}_i|
\le \sum_{j=1,j\ne i}^n |a_{ij}| |\MM{w}_j|
\le |\MM{w}_i| \sum_{j=1,j\ne i}^n |a_{ij}| =: |\MM{w}_i| r_i
$$
which, after dividing by $|\MM{w}_i|$, gives \R{3.6}. \QED

A matrix $A$ is said to be {\em strictly diagonal dominant} 
if $|a_{ii}| > r_i$ for all $i$. From Gerschgorin theorem,
it follows that a strictly diagonal dominant matrix is nonsingular.


{\bf Theorem.} Let $A$ be strictly diagonal dominant. Then the Jacobi
iteration converges.\\
\hspace*{8pt}{\bf Proof.} We prove that the spectral radius of
the Jacobi iteration matrix $H = - A_\CC{D}^{-1}(A_\CC{L} +A_\CC{U})$
satisfies $\rho(H) < 1$. One computes
$h_{ii} = 0$, $h_{ij} = - a_{ij}/a_{ii}$,
and if $A$ is strictly diagonal dominant, 
then $r_i = \sum_{i\ne j} |h_{ij}| < 1$.
By Gerschgorin theorem, the eigenvalues of $H$ lie
in the union of the discs $\Gamma_i := \{z \in \BB{C}: |z| < 1\}$,
i.e. $\rho(H) < 1$ \QED



%{\bf Corollary.} Let $A$ be a $n\times n$ real symmetric matrix.
%If $a_{ii} > \sum_{j=1,j\ne i}^n |a_{ij}|$ for all $i$, 
%then $A$ is positive definite.


\section{QR factorization of matrices}

\subsection{Scalar products, norms and orthogonality}

We first revise a few definitions. In what follows, 
$\BB{R}^n$ is the linear space of all real $n$-tuples.
\vspace{-1ex}
\begin{itemize}
\vspace{-1ex}
\item For all $\MM{u},\MM{v}\in\BB{R}^n$ we define the {\em scalar
    product\/}
  \begin{displaymath}
    \textstyle
    \langle \MM{u},\MM{v}\rangle=\langle \MM{v},\MM{u}\rangle=
    \sum_{j=1}^n u_j v_j=\MM{u}^{\CC{T}}\MM{v}=\MM{v}^{\CC{T}}\MM{u}\,.
  \end{displaymath}

\vspace{-1ex}
\item If $\MM{u}, \MM{v}, \MM{w} \in\BB{R}^n$ and $\alpha, \beta \in \BB{R}$
  then $\langle \alpha \MM{u} + \beta \MM{w},\MM{v}\rangle =\alpha
  \langle \MM{u},\MM{v}\rangle + \beta \langle \MM{w},\MM{v}\rangle$.
\vspace{-1ex}
\item The {\em norm\/} (a.k.a.\ the {\em Euclidean length\/}) of
  $\MM{u}\in\BB{R}^n$ is $\|\MM{u}\|=\left(\sum_{j=1}^n
    u_j^2\right)^{1/2}\!=\langle \MM{u},\MM{u}\rangle^{1/2} \ge 0$.
\vspace{-1ex}
\item For $\MM{u}\in\BB{R}^n$, $\|\MM{u}\|=0$ iff $\MM{u}=\MM{0}$.
\vspace{-1ex}
\item We say that $\MM{u}\in\BB{R}^n$ and $\MM{v}\in\BB{R}^n$ are {\em
    orthogonal\/} to each other if $\langle\MM{u},\MM{v}\rangle=0$.
\vspace{-1ex}
\item The vectors $\MM{q}_1,\MM{q}_2,\ldots,\MM{q}_m\in\BB{R}^n$ are {\em
    orthonormal\/} if
  \begin{displaymath}
    \langle \MM{q}_k,\MM{q}_\ell\rangle=
    \begin{case}
      1, &k=\ell,\\
      0, &k\neq\ell,
    \end{case}
    \qquad k,\ell=1,2,\ldots,m.
  \end{displaymath}

\vspace{-1ex}
\item An $n\times n$ real matrix $Q$ is {\em orthogonal\/} if all its
  columns are orthonormal. Since $(Q^{\CC{T}}Q)_{k,\ell}=\langle
  \MM{q}_k,\MM{q}_\ell \rangle$, this implies that $Q^{\CC{T}}Q=I$ ($I$ is the
  {\em unit matrix\/}). Hence $Q^{-1}=Q^{\CC{T}}$ and
  $QQ^{\CC{T}}=QQ^{-1}=I$. 
  We conclude that the rows of an orthogonal matrix are also
  orthonormal, and that $Q^{\CC{T}}$ is an orthogonal matrix. Further,
  $1=\det I=\det(QQ^{\CC{T}})=\det Q\det Q^{\CC{T}}=(\det Q)^2$,
  and thus we deduce that $\det Q=\pm1$, and that an orthogonal matrix is
  nonsingular.
\end{itemize}

{\bf Proposition} If $P,Q$ are orthogonal then so is $PQ$.\\
\hspace*{8pt}{\bf Proof.} Since $P^{\CC{T}}P=Q^{\CC{T}}Q=I$, we have
$(PQ)^{\CC{T}}(PQ)=(Q^{\CC{T}}P^{\CC{T}})(PQ)=Q^{\CC{T}}(P^{\CC{T}}P)Q=Q^{\CC{T}}Q=I$,
hence $PQ$ is orthogonal. 
\QED

{\bf Proposition} Let $\MM{q}_1,\MM{q}_2,\ldots,\MM{q}_m\in\BB{R}^n$
be orthonormal. Then $m\leq n$.\\
\hspace*{8pt}{\bf Proof.} We argue by contradiction. Suppose that
$m\geq n+1$ and let $Q$ be the orthogonal matrix whose columns are
$\MM{q}_1,\MM{q}_2,\ldots,\MM{q}_n$. Since $Q$ is nonsingular and
$\MM{q}_m\neq\MM{0}$, there 
exists a nonzero solution to the linear system $Q\MM{a}=\MM{q}_m$,
hence $\MM{q}_m=\sum_{j=1}^n a_j\MM{q}_j$. But
\begin{displaymath}
  0=\langle\MM{q}_\ell,\MM{q}_m\rangle
  =\left\langle\MM{q}_\ell,\sum_{j=1}^n a_j \MM{q}_j\right\rangle
  =\sum_{j=1}^n 
  a_j\langle \MM{q}_\ell,\MM{q}_j\rangle=a_\ell,\qquad
  \ell=1,2,\ldots,n,
\end{displaymath}
hence $\MM{a}=\MM{0}$, a contradiction. We deduce that $m\leq n$.
\QED

{\bf Lemma} Let $\MM{q}_1,\MM{q}_2,\ldots,\MM{q}_m\in\BB{R}^n$ be
orthonormal and $m\leq n-1$. Then there exists $\MM{q}_{m+1}\in\BB{R}^n$
such that $\MM{q}_1,\MM{q}_2,\ldots,\MM{q}_{m+1}$ are orthonormal.\\
\hspace*{8pt}{\bf Proof.} We construct $\MM{q}_{m+1}$. Let $Q$ be the
$n\times m$ matrix whose columns are $\MM{q}_1,\ldots,\MM{q}_m$. Since
\begin{displaymath}
  \sum_{k=1}^n\sum_{j=1}^m Q_{k,j}^2=\sum_{j=1}^m\|\MM{q}_j\|^2=m<n,
\end{displaymath}
it follows that $\exists$ $\ell\in\{1,2,\ldots,n\}$ such that
$\sum_{j=1}^m Q_{\ell,j}^2<1$. We let
$\MM{w}=\MM{e}_\ell-\sum_{j=1}^m \langle \MM{q}_j,\MM{e}_\ell\rangle
\MM{q}_j$. Then for $i=1,2,\ldots,m$
\begin{displaymath}
  \langle \MM{q}_i,\MM{w}\rangle = \langle
  \MM{q}_i,\MM{e}_\ell\rangle - \sum_{j=1}^m \langle
  \MM{q}_j,\MM{e}_\ell\rangle \langle \MM{q}_i, \MM{q}_j\rangle = 0,
\end{displaymath}
i.e.\ by design $\MM{w}$ is orthogonal to
$\MM{q}_1,\ldots,\MM{q}_m$. Further, since $Q_{\ell,j}=\langle
\MM{q}_j,\MM{e}_\ell\rangle$, we have 
\begin{displaymath}
  \|\MM{w}\|^2=\langle\MM{w},\MM{w}\rangle=
  \langle \MM{e}_\ell, \MM{e}_\ell\rangle
  -2\sum_{j=1}^m\langle\MM{q}_j,\MM{e}_\ell\rangle
  \langle \MM{e}_\ell ,\MM{q}_j \rangle
  + \sum_{j=1}^m\langle\MM{q}_j,\MM{e}_\ell\rangle
  \sum_{k=1}^m\langle\MM{q}_k,\MM{e}_\ell\rangle \langle \MM{q}_j,\MM{q}_k\rangle
  = 1-\sum_{j=1}^m Q_{\ell,j}^2>0.
\end{displaymath}
Thus we define $\MM{q}_{m+1}=\MM{w}/\|\MM{w}\|$. \QED

\subsection{The QR factorization}

The QR factorization of an $m\times n$ matrix $A$ has the form
$A=QR$, where $Q$ is an $m\times m$ {\em orthogonal\/} matrix and $R$
is an $m\times n$ {\em upper triangular\/} matrix (i.e., $R_{i,j}=0$
for $i>j$). We will demonstrate in the sequel that every matrix has a
(non-unique) QR factorization.

{\bf An application} Let $m=n$ and $A$ be nonsingular. We can solve
$A\MM{x}=\MM{b}$ by calculating the QR factorization of $A$ and
solving first $Q\MM{y}=\MM{b}$ (hence $\MM{y}=Q^{\CC{T}}\MM{b}$) and then
$R\MM{x}=\MM{y}$ (a triangular system!).

{\bf Interpretation of the QR factorization} Let $m\geq n$ and denote
the columns of $A$ and $Q$ by $\MM{a}_1,\MM{a}_2,\ldots,\MM{a}_n$
and $\MM{q}_1,\MM{q}_2,\ldots,\MM{q}_m$ respectively. Since
\begin{displaymath}
  [\begin{array}{cccc}\MM{a}_1&\MM{a}_2&\cdots&\MM{a}_n\end{array}]
  =[ \begin{array}{cccc}\MM{q}_1&\MM{q}_2&\cdots&\MM{q}_m\end{array}]
  \left[\begin{array}{cccc}
      R_{1,1} & R_{1,2} & \cdots & R_{1,n}\\
      0 & R_{2,2} & & \vdots\\
      \vdots & \ddots & \ddots \\
      & & 0 & R_{n,n}\\
      \vdots & & & \vdots\\
      0 & \cdots & \cdots & 0
    \end{array}\right],
\end{displaymath}
we have $\MM{a}_k=\sum_{j=1}^k R_{j,k}\MM{q}_j$,
$k=1,2,\ldots,n$. In other words, $Q$ has the property that each $k$th
column of $A$ can be expressed as a linear combination of the first
$k$ columns of $Q$.

\end{document}