\documentclass[12pt]{article}
\usepackage{fullpage,amsmath,amsfonts}

\newcommand{\x}{\boldsymbol{x}}
\newcommand{\y}{\boldsymbol{y}}
\newcommand{\f}{\boldsymbol{f}}
\renewcommand{\v}{\boldsymbol{v}}
\newcommand{\w}{\boldsymbol{w}}
\renewcommand{\r}{\boldsymbol{r}}
\renewcommand{\a}{\boldsymbol{a}}
\renewcommand{\b}{\boldsymbol{b}}
\renewcommand{\c}{\boldsymbol{c}}
\renewcommand{\k}{\boldsymbol{k}}
\newcommand{\z}{\boldsymbol{z}}
\newcommand{\e}{\mathrm{e}}
\renewcommand{\i}{\mathrm{i}}
\renewcommand{\d}{\mathrm{d}}
\renewcommand{\Re}{\operatorname{Re}}
\renewcommand{\Im}{\operatorname{Im}}
\newcommand{\Range}{\operatorname{Range}}
\newcommand{\Ker}{\operatorname{Ker}}
\newcommand{\Span}{\operatorname{Span}}
\renewcommand{\dim}{\operatorname{dim}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}

\def\nl{\vphantom\vdots\\}

\begin{document}

\title{Numerical Methods II}
\author{Problem Set 4}
\date{due in class, March 10, 2004}
\maketitle

\noindent (From SM, Chapter 5)

\begin{enumerate}
  
\item Show that if $H_k$ is a $k\times k$ Householder matrix, i.e.
\[
  H_k = I - 2 \, \frac{\v_k \v_k^T}{\v_k^T \v_k} \,,
\]
then
\[
  H = \begin{pmatrix}
        I_{n-k} & 0 \\ 0 & H_k
      \end{pmatrix}
\]
is an $n \times n$ Householder matrix.

\item Use Householder matrices to transform the matrix
\[
  A =
  \begin{pmatrix}
    2 & 1 & 2 & 2 \\
    1 & -7 & 6 & 5 \\
    2 & 6 & 2 & -5 \\
    2 & 5 & -5 & 1
  \end{pmatrix}
\]
into tridiagonal form.

\item Let $A^{(0)}$ be a diagonal $n\times n$ matrix with distinct
  diagonal elements, and $A^{(1)}$ be a symmetric $n\times n$ matrix.
  Assume that
\[
  A_\varepsilon \equiv A^{(0)}+\varepsilon \, A^{(1)}
\]
has an eigenvalue $\lambda_\varepsilon$ with corresponding eigenvector
$\x_\varepsilon$.  Show that
\begin{gather*}
  \lambda_\varepsilon = \lambda^{(0)} + \varepsilon \, \lambda^{(1)}
    + O(\varepsilon^2) \,, \\
  \x_\varepsilon = \x^{(0)} + \varepsilon \, \x^{(1)}
    + O(\varepsilon^2) \,,
\end{gather*}
where $\lambda^{(0)}=a_{jj}^{(0)}$ for some $j=1,\dots,n$,
$\lambda^{(1)}=a_{jj}^{(1)}$,  $\x^{(0)}=\boldsymbol{e}_j$, and
\[
  x^{(1)}_i = \frac{a_{ij}^{(1)}}{a_{jj}^{(0)} - a_{ii}^{(0)}}
\]
for $i\neq j$.  Explain why normalizability of the eigenvector
requires that we choose $x^{(1)}_j=0$.

\item \emph{(QR iteration.)} Let $A$ be a symmetric, tridiagonal
  $n\times n$ matrix, and assume that $A-\mu I = QR$ where $Q$ is a
  product of plane rotations and $R$ is upper triangular and also
  tridiagonal.  Show that
\begin{enumerate}
  \item $B=RQ+\mu I$ is symmetric;
  \item $B$ has the same eigenvalues as $A$;
  \item $B$ is tridiagonal.
\end{enumerate}
\end{enumerate}


\end{document}
