% Typeset with pdflatex
\documentclass[12pt]{amsart}
\usepackage{graphicx}
\usepackage[plain]{algorithm}
\textheight=9in
\textwidth=6.5in
\calclayout
\pagestyle{plain}
\thispagestyle{empty}
\parindent=0pt
\parskip=10pt plus3pt minus2pt
\newcommand\norm[1]{\lVert#1\rVert}
\newcommand\C{\mathbb C}
\newcommand\R{\mathbb R}
\renewcommand\P{\mathcal P}
\renewcommand\r{\sqrt{a/b}}
\begin{document}
\hbox to\hsize{\rlap{MATH 8445, Fall '17}\hfil Homework 2 \hfil\llap{Arnold}}
\bigskip
\parskip=10pt plus 2pt minus 2pt
\renewcommand{\theenumi}{\alph{enumi}}


\bigskip

 1. Consider three different ways to express a classical iterative method:
$$
u_{i+1} = u_i + B(f - Au_i),\quad
u_{i+1}= P^{-1}(f - Qu_i), \quad
u_{i+1} = G u_i + B f,
$$
in terms of the approximate inverse $B$, the splitting matrix $P$, or the iteration matrix $G$.
Make a table with four columns, one for the method and one each for $B$, $P$, and $G$.
In the first column put the following five methods:
{\it Richardson, Jacobi, Gauss--Seidel, damped Jacobi, SOR},
and then, in the remaining columns put in the formulas for the corresponding matrices.
For example, in the row for Jacobi and the column for the iteration matrix $G$
you should put $-D^{-1}(U+L)$, using the notations $D$, $L$, and $U$ for the diagonal,
strictly lower triangular, and strictly upper triangular parts of $A$.

2. Show that the following matrix is SPD, but that the Jacobi iteration does not converge for
it (unlike Gauss--Seidel, which converges for all SPD matrices).
$$
\begin{pmatrix}
 3&2&1\\2&3&2\\1&2&3
\end{pmatrix}
$$

3. Consider the solution of $Ax=b$ for an SPD matrix $A$ using the damped Jacobi iteration
with damping parameter $\alpha\in[0,1]$.  Let $G_\alpha$ denote the corresponding iteration matrix.
\begin{enumerate}
 \item Give the formula for $G_\alpha$ in terms of $\alpha$, $D$  and $L$ (where $A=L + D + L^T$).
 Write out in particular the formula for $G_1$ and check
 that it is the iteration matrix for the (undamped) Jacobi method.
 \item Prove that $G_\alpha$ has only real eigenvalues.
 \item Suppose that the minimum and maximum eigenvalues of $G_1$ (the iteration
 matrix for undamped Jacobi) are $-2$ and $0.5$, respectively.  What are the minimum
 and maximum values of the eigenvalues of $G_\alpha$?
 \item For which values of $\alpha\in[0,1]$ does the
 the damped Jacobi iteration converge?
 \item Which value of $\alpha$ optimizes the rate of convergence in this case, and
 what is the optimal rate?
\end{enumerate}


\end{document}

