\documentclass[11pt,reqno]{amsart}%
\usepackage{graphicx}
\usepackage{enumerate}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{vmargin}%
\setcounter{MaxMatrixCols}{30}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.00.0.2606}
%TCIDATA{LastRevised=Thursday, May 11, 2006 14:34:24}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%TCIDATA{Language=American English}
\pagestyle{plain} \setpapersize{USletter}
\setmarginsrb{1in}{0.75in}{1in}{0.6in}{0in}{0in}{11pt}{0.4in}
\renewcommand{\theequation}{\arabic{enumi}.\arabic{equation}}
\begin{document}
\title[CME 324 ASSIGNMENT 2]{CME 324: ITERATIVE METHODS\\SPRING 2005/06\\ASSIGNMENT 2}
\author{Gene~H.~Golub}
\thanks{This assignment is due in class on Wednesday, May 24.}
\date{\today, version 2.2}
\maketitle

\begin{enumerate}[\bfseries 1.] \setlength{\itemsep}{2ex}

\item Consider the matrix $A$ given in Problem \textbf{3} of Homework
\textbf{1}, and the equation given in part (g) of that problem. We want to
conduct a number of experiments with the CG method and make comparisons.

\begin{enumerate}
\item Solve the linear system with the two variants described in class, using
the preconditioner $M=I$. Compute the residual vector $\mathbf{r}%
_{k}=\mathbf{b}_{k}-A\mathbf{x}_{k}$ in one set of experiments, and then
repeat the experiments using the recursion for the residual vector. Graph the
behavior of $\lVert\mathbf{x}-\mathbf{x}_{k}\rVert_{2}$, $\lVert
\mathbf{x}-\mathbf{x}_{k}\rVert_{A}$, $\lVert\mathbf{r}_{k}\rVert_{2}$.
Described the termination rule for determining your approximate solution.
Which method seems to perform best in terms of computational efficiency and accuracy.

\item Repeat part (a) using the preconditioner $M=\operatorname*{blockdiag}%
(A)$. Compare the convergence properties with those given by the bound.
\end{enumerate}

\item Let $\sigma>0$. Consider the differential equation%
\begin{align*}
&  -u^{\prime\prime}+\sigma u^{\prime}=f,\qquad\qquad0<x<1.\\
&  u(0)=\alpha,\quad u(1)=\beta
\end{align*}
Consider the difference equation%
\[
\frac{-u_{i-1}+2u_{i}-u_{i+1}}{h^{2}}+\sigma\frac{u_{i+1}-u_{i}}{h}=f_{i}.
\]


\begin{enumerate}
\item Write down the matrix equation%
\[
A\mathbf{x}=\mathbf{f}.
\]


\item Since $A\neq A^{\top}$, develop an algorithm for computing a diagonal
matrix $D$ such that%
\[
\tilde{A}=DAD^{-1}=\tilde{A}^{\top}.
\]
Show that this can only be done when $\sigma h$ satisfies a special
relationship. Find a limit of $d_{n}/d_{1}$ as $h\rightarrow0$.

\item Consider the case where $\sigma=40$, $n=100$. Apply the CG method and
SOR method to this problem and compare the results.

\item Apply GMRES using the matrix $A$. Again, compare these results to those
obtained in (c). Also, consider the computational effieciency of each algorithm.
\end{enumerate}

\item As discussed in class, it is frequently desirable to obtain a
function of the solution. Suppose we are solving the equation
\[
 		A\mathbf{x} =\mathbf{b}.
\]
Now we want to estimate
\begin{equation}
\mathbf{e}^{\top}\mathbf{x} \label{sum}
\end{equation}
where $\mathbf{e} = (1,1,\dots,1)^{\top}$.

\begin{enumerate}
\item Using the elements of moment theory and the Lanczos algorithm, show 
how to give upper and lower bounds for \eqref{sum}.

\item Try the following example
\[
\begin{aligned}
 	a_{11} &= 1,
	&a_{ii} &=2 &\text{for }i &\ne 1,
	&a_{i,i\pm 1} &= -1,\\
 	b_1 &= 1,
	&b_i &=0  &\text{for } i &\ne 1.
 	&	&
\end{aligned}
\]
Apply your algorithm when $n=100$ (say). Here you may take the upper and
lower limits of the Stieltjes integral to be $a = 4$ and $b =
\lambda_{\operatorname*{min}}(A)$ (the smallest eigenvalue of $A$)
respectively.
\end{enumerate}
\end{enumerate}

\end{document}