\documentclass{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\newcommand{\R}{{\mathbb R}}
\newcommand{\points}[1]{\phantom{.}\hfill \textbf{(#1 points)}}

\begin{document}

\begin{center}
  \begin{huge}
    MATH 609-602: Numerical Methods
  \end{huge}
\end{center}

\begin{tabular}{ll}
Lecturer: & Prof. Wolfgang Bangerth \\
& Blocker Bldg., Room 507D \\
& (979) 845 6393 \\
& \texttt{bangerth@math.tamu.edu}\\[5pt]
Teaching Assistant: & Seungil Kim \\
& Blocker Bldg., Room 507A \\
& (979) 862 3259 \\
& \texttt{sgkim@math.tamu.edu}
\end{tabular}

\section*{Homework assignment 5 -- due Tuesday 10/11/2005}


\paragraph{Problem 1 (Steepest descent iteration; since the prof's claim that
  the solution wiggles back and forth didn't seem to be too convincing and
  he didn't have much of a good explanation anyway :-).} 

The claim was that for badly conditioned matrices the solution vector $x_k$ of
iteration $k$ wiggles back and forth, rather than making one step towards the
main axis of the contour lines of the quadratic function $q(y)$ and then going
straight towards the minimum. Let us test this claim:

Take a matrix and right hand side for a two-dimensional problem as follows:
\begin{align*}
  A = 
  \begin{pmatrix}
    10 & 0 \\ 0 & 1
  \end{pmatrix},
  \qquad\qquad
  b = 
  \begin{pmatrix}
    10 & 0
  \end{pmatrix}.
\end{align*}
The solution of the linear system $Ax=b$ is $x=(1,0)$.
Generate graphs that show the surface and contours of the function
\begin{align*}
  q(y) = \frac 12 y^T A y - y^T b.
\end{align*}

Next consider the steepest descent iteration. Start from $\tilde
x=(2,10)$. Perform 100 iterations, where in each iteration you compute
\begin{align*}
  g &= A\tilde x - b,
&  \alpha &= \frac{g^Tg}{g^TAg},
\end{align*}
and then set $\tilde x := \tilde x - \alpha g$. Plot the iterates $\tilde
x=(\tilde x_1,\tilde x_2)$ in a 2-dimensional plot and connect them by lines
to see their convergence.

How many iterations do you need to achieve an accuracy of $\|\tilde x-x\|_2\le
10^4$? Repeat the experiment where $a_{11}$ and $b_1$ both have the values
1, 10, 100, 1000, 10000 (all other elements of $A$ and $b$ unchanged), and
starting from $\tilde x=(2,a_{11})$. Create a table with
the condition number of these matrices and how many iterations it takes to
achieve above accuracy.
\points{5}


\paragraph{Problem 2 (CG iteration).} Take the ever-same
$100\times 100$ matrix and $100$-dimensional vector defined by
\begin{align*}
  A_{ij} = \left\{
    \begin{array}{ll}
      2.01 & \text{if $i=j$}, \\
      -1 & \text{if $i=j\pm 1$}, \\
      0 & \text{otherwise},
    \end{array}
  \right.
  \qquad\qquad
  b_i = \frac 1{100} \sin\left(\frac{2\pi i}{50}\right).
\end{align*}
Implement the Conjugate Gradient algorithm as on page 238 of the book, just
above Theorem 3. 

Start with a vector $x_0$ with randomly chosen elements in the range $0\le
(x_0)_i \le 1$ (i.e. with elements generated from what the \texttt{rand()}
function or a similar replacement returns).  Run 100 iterations and plot
$\|x_N-x_{100}\|$ for these vectors, and graph $(x_N)_i$ against $i$ as in
Problem 3 of Homework 4 and as in the test.

If you run the algorithm for 200 iterations, does the solution still change
significantly? If not, why?
\points{6}


\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: