\documentclass[11pt,twoside]{article}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{url}

%\textheight      8.5in
%\textwidth       5.5in
%\topmargin      -0.0in
%\oddsidemargin   0.5in
%\evensidemargin  0.5in
%\pagestyle{myheadings}

\newcommand{\HW}{}
\newcommand{\HWnumb}{2}
\newcommand{\HWdate}{Monday April 29}
\input{hw0}
\input{../notes/macros.tex}

\thispagestyle{empty}

%\noindent
Suppose $A \in \Re^{n \times n}$ is symmetric and $b \in \Re^n$ ($b
\ne 0$).  Let the $k$th Krylov subspace be $\Kscr_k \equiv
\Span\{b,Ab,A^2b,\dots,A^{k-1}b\}$, and let $(T_k,H_k,V_k)$ denote the
matrices obtained by applying the Lanczos process to $(A,b)$ for $k$
steps, as defined in the notes.  Assume that we use exact arithmetic
and that the process terminates with $\beta_{k+1}=0$ for some $k=\ell
\le n$.

\subsection*{Exercise 1}
If $A$ has $m < n$ distinct eigenvalues, show that the Lanczos process for
$(A,b)$ terminates with $\ell \le m$.  (If you wish, you may prove
that the dimension of the Krylov subspaces $\Kscr_k(A,b)$ cannot exceed $m$.)

\subsection*{Exercise 2}
Show that if $A$ is changed to $A - \sigma I$ for some scalar shift
$\sigma$, $T_k$ becomes $T_k - \sigma I$ and $V_k$ is unaltered.

\subsection*{Exercise 3}
Using $AV_k = V_{k+1}H_k$ for $k < \ell$ and the definitions of
$\{\alpha_k, \beta_k, v_k\}$, show that the columns of $V_k$ are
orthonormal ($k \le \ell$).

\subsection*{Exercise 4}
Show that the following subproblems are equivalent for defining how CG
chooses $x_k$ when $A$ is positive definite:
\[
\begin{tabular}{ll}
   (1) & minimize $\half x_k^TAx_k - b^Tx_k$ such that $x_k \in \Kscr_k$
\\ (2) & minimize $\norm{r_k}_{A\inv}$       such that $x_k \in \Kscr_k$
\\ (3) & find     $x_k$                      such that $x_k \in \Kscr_k$ and $r_k \perp \Kscr_k$,
\end{tabular}
\]
where $r_k = b - Ax_k$ and $\|w\|_{A\inv} = \sqrt{w^T A\inv w}$ for all $w \in \Re^n$.

\subsection*{Exercise 5 \rm (extra credit)}
Prove that $T_\lscr$ is nonsingular if and only if $b \in \Range(A)$.

\noindent
Deduce that $\beta_{\ell+1} = 0$ is a ``lucky breakdown'' for \CG,
\MINRES,\ and \SYMMLQ{} if $b \in \Range(A)$.

% \subsection*{Exercise 6}
% Show that the following subproblems are equivalent for defining how SYMMLQ
% chooses $x_k$:
% \begin{align*}
%    \mbox{(1)} & \sgap \minim\ \twonorm{x_k} \words{such that} x_k \in \Kscr_k
%                \words{and} r_k \perp \Kscr_{k-1}
% \\ \mbox{(2)} & \sgap \minim\ \twonorm{x - x_k} \words{such that} x_k \in A\Kscr_{k-1},
% \end{align*}
% where %$r_k = b - Ax_k$, $\Kscr_k \equiv \Span\{b,Ab,A^2b,\dots,A^{k-1}b\}$,
% we assume that $Ax=b$ is consistent.

\end{document}