\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 5}
\date{due in class, March 24, 2004}
\maketitle

\begin{enumerate}
\item (From SM, p.\ 177.) Perform one step of the $QR$ algorithm,
  using the shift $\mu=a_{nn}$, for the matrix
\[
  A = \begin{pmatrix}
    0 & 1 \\ 1 & 0
  \end{pmatrix}\,.
\]
Show that the $QR$ algorithm does not converge for this matrix.  (A
different shift must be used for this matrix.)
  
\item (From SM, p.\ 177.)  An eigenvalue and eigenvector of the $n
  \times n$ matrix $A$ may be evaluated by solving the system of
  nonlinear equations
\begin{gather*}
  (A - \lambda I) \, \x = 0 \,, \\
  \x^T\x = 1
\end{gather*}
for the $n+1$ unknowns $\lambda$ and $\x$.  Show that, when applying
Newton's method to this problem, you obtain the iteration
\begin{gather*}
  (A - \lambda_k I) \, \Delta \x_k - \Delta \lambda_k \, \x_k
  = -(A - \lambda_k I) \, \x_k \,, \\
  -\x_k^T \Delta \x_k = \tfrac12 \, (\x_k^T \x_k - 1) \,,
\end{gather*}
where
\begin{gather*}
  \x_{k+1} = \x_k + \Delta \x_k \,, \\
  \lambda_{k+1} = \lambda_k + \Delta \lambda_k \,.
\end{gather*}
Comment on the difference between this method and the method of
inverse iteration.

\item \textbf{Project:} Write a simple \textsf{Octave} function that
  performs the $QR$ algorithm with shift.  You may use the built-in
  function \texttt{qr} to perform the $QR$ decomposition.  Test your
  code on the matrices
 \[
  A = \begin{pmatrix}
    0 & 1 \\ 1 & 0
  \end{pmatrix}
  \qquad \text{and} \qquad
  A = \begin{pmatrix}
    5 & 1 \\ 1 & 7
  \end{pmatrix} \,.
\]
Experiment with the shifts and describe how different shifting
strategies affect the rate of convergence.

\item \textbf{Project:} The method of inverse iteration can approximate
  eigenvectors even when the corresponding eigenvalue is not
  accurately known.  Describe a method for finding the eigenvalue once
  the eigenvector is computed, and test your method with the matrices
  from the previous question.

\item Derive the update rule in Brent's method for finding the minimum
  of a scalar function: Given three evaluation points $x_0$, $x_1$,
  and $x_2$ with corresponding function values $y_0=f(x_0)$,
  $y_1=f(x_1)$, and $y_2=f(x_2)$ (usually taken from the bracket about
  the minimum), find the quadratic polynomial that interpolates
  between these points.  Hence, find the expression for the extremum
  of this polynomial, to be taken as the new evaluation point
  $x_{\operatorname{n}}$.

\end{enumerate}


\end{document}
