\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: