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

\newcommand{\x}{\boldsymbol{x}}
\renewcommand{\v}{\boldsymbol{v}}
\newcommand{\w}{\boldsymbol{w}}
\renewcommand{\a}{\boldsymbol{a}}
\renewcommand{\b}{\boldsymbol{b}}
\renewcommand{\r}{\boldsymbol{r}}
\newcommand{\e}{\boldsymbol{e}}
\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}}


\begin{document}

\title{Numerical Methods I -- Problem Set 5}
\author{Fall Semester 2005}
\date{Due October 14}
\maketitle


\begin{enumerate}

\item Consider the following class of iterative methods for solving
$A\x=\b$, called \emph{stationary Richardson methods}:
\begin{gather*}
  \x_{k+1} = \x_k + \alpha \, P^{-1} \r_k
\end{gather*}
where $\r_k=\b-A\x_k$ is the residual in the $k$th step.  Assume that
all eigenvalues of $P^{-1}A$ are real and positive, and let
$\lambda_{\min}$ and $\lambda_{\max}$ denote the minimum and maximum
eigenvalue, respectively.
\begin{enumerate}
\item Show that the method converges if and only if $\alpha <
2/\lambda_{\max}$.

\item Show that the method converges fastest if
\[
  \alpha = \frac2{\lambda_{\min}+\lambda_{\max}} \,.
\]
\end{enumerate}

\item Given any iterative method for solving $A\x=\b$ of the form 
\begin{gather*}
  \x_{k+1} = \x_k + B \r_k 
\end{gather*}
where, again, $\r_k=\b-A\x_k$.  Show that the method is consistent for
any nonsingular $B$.

(Recall: a method is consistent if any fixed point of the method is a
solution to $A\x=\b$.)

\item A matrix $A$ is called \emph{strictly diagonally dominant by
rows} if
\[
  |a_{ii}| > \sum_{\substack{j=1\\j\neq i}}^n |a_{ij}|
\]
for every $i=1,\dots,n$.

Show that if $A$ has this property, then the Jacobi method converges.

\item \textbf{Project:} Write an \textsf{Octave} code
to solve $A\x=\b$ by each of the the following methods:
\begin{enumerate}
\item Jacobi method
\item Gradient method
\end{enumerate}
Plot the $2$-norm of the residual on a logarithmic scale vs.\ the
number of iterations for the following $n\times n$ test problem for
$n=10$:

\[
  A =
  \begin{pmatrix}
  2 & -1 & 0 & & \cdots & & 0 & -\tfrac12 \\
  -1 & 2 & \ddots & \ddots & & & & 0 \\
  0 & \ddots & \ddots \\
  & \ddots& & & & & &\vdots \\
  \vdots & &&& & & \ddots \\
  & & & && \ddots & \ddots & 0 \\
  0 & & && \ddots & \ddots & 2 & -1 \\
  -\tfrac12 & 0 & &\cdots& & 0 & -1 & 2 
  \end{pmatrix} \,, \qquad
  \b =
  \begin{pmatrix}
  1 \\ 1 \\ \vdots \\ 1
  \end{pmatrix} \,.
\]

Which method works best?

\end{enumerate}
\end{document}
