% This is a LaTex file.
% Homework for the course "Iterative Methods for Solving Linear Systems",
% Autumn quarter, 1998, Anne Greenbaum.
% A latex format for making homework assignments.
\documentstyle[12pt]{article}
% The page format, somewhat wider and taller page than in art12.sty.
\topmargin -0.1in \headsep 0in \textheight 8.9in \footskip 0.6in
\oddsidemargin 0in \evensidemargin 0in \textwidth 6.5in
\begin{document}
% Definitions of commonly used symbols.
% The title and header.
\noindent
{\scriptsize Math/AMath 594: Special Topics in Numerical Analysis, Autumn 1998} \hfill
\begin{center}
\large
Assignment 1.
\normalsize
\end{center}
\noindent
Due Mon., Oct. 12.
\vspace{.3in}
% The questions!
\noindent
{\bf Objectives:} To think about iterative methods for solving linear
systems; to discover some properties of simple iteration and ORTHOMIN(1).
\begin{description}
\item[(1)]
Suppose you wish to solve (or approximately solve) an $n$ by $n$
nonsingular system of linear equations $Ax=b$, but the matrix $A$
is not given to you directly. Instead you have a black box which
when given any vector $y$ produces the vector $Ay$. Try to devise
a method for solving the linear system (or generating a good approximate
solution) that is different from the methods covered so far in class.
Discuss properties of the matrix $A$ that will ensure that your method
converges to the true solution and try to say something about the rate
of convergence. [Of course, you could determine the entries of $A$
by applying $A$ to each of the standard basis
vectors $\xi_j$, $j=1, \ldots , n$, where $\xi_j$ has a $1$ in position $j$
and $0$'s elsewhere, but the purpose of this problem is to think about
methods that do {\em not} require this.]
\item[(2)]
Use the Jordan form of a matrix to show that for any fixed $k \geq 0$
\[
\lim_{j \rightarrow \infty} ( ||| e_{k+j} ||| / ||| e_k ||| )^{1/j} =
\rho (I - M^{-1} A) ,
\]
where $||| \cdot |||$ is any norm and $e_{k+j}$ is the error at step
$k+j$ of the simple iteration algorithm.
\item[(3)]
Write down a problem $Ax=b$ for which ORTHOMIN(1) converges to the
true solution but (unpreconditioned) simple iteration does not.
Write down a problem for which (unpreconditioned) simple iteration
converges to the
true solution but ORTHOMIN(1) does not. Can you find a problem for
which both methods converge but simple iteration converges faster
(i.e., reduces the 2-norm of the residual faster) than ORTHOMIN(1)?
Explain your answers.
\end{description}
\end{document}