\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*{Test 1 -- due Tuesday 10/4/2005}

\textbf{I hereby
  certify that I have prepared my answers alone and
  without help by others:\\[18pt]
  \hspace*{.3\textwidth}\hrulefill\hspace*{.3\textwidth}\\
  \hspace*{.3\textwidth}\hfill(signature of student)\hfill\hspace*{.3\textwidth}\\
  The usual rules of academic intregrity apply. In
particular, the Aggie Honor Code ``An Aggie does not lie, cheat or steal, or
tolerate those who do'' should be selfevident, see\\
\hspace*{1cm}
  \texttt{http://www.tamu.edu/aggiehonor.html}}\\[18pt]


\paragraph{Problem 1 (Taylor series expansion of $x^{-1}$.)} Derive the
(infinite, without remainder term) Taylor series of
\begin{align*}
  f(x) = x^{-1},
\end{align*}
when expanded around $x_0=1$.  Determine for which values in the range $0\le
x\le \infty$ this series actually converges, i.e. for which the Taylor series
up to term $k$ converges against $f(x)$ as $k\rightarrow \infty$. Does it
converge for negative values $x<0$?

\points{3}


\paragraph{Problem 2 (Taylor series expansion of $A^{-1}$).} For real $x$ with
$|1-x|<1$, the following formula is true:
\begin{align*}
  \frac 1x = \sum_{k=0}^\infty (1-x)^k.
\end{align*}
One could suspect that the same holds for invertible matrices $X\in\R^{n\times
  n}$, so that
\begin{align*}
  X^{-1} = \sum_{k=0}^\infty (I-X)^k,
\end{align*}
at least if $\|I-X\| < 1$ for some matrix norm. 

If $D$ is the diagonal of a matrix $A$, then we have shown in connection with
Jacobi iteration that $\|I-D^{-1}A\|_\infty < 1$ if $A$ is a strongly
diagonally dominant matrix. Let us therefore consider $X=D^{-1}A$. We then
have
\begin{align*}
  (D^{-1}A)^{-1} = \sum_{k=0}^\infty (I-D^{-1}A)^k,
\end{align*}
or
\begin{align*}
  A^{-1} = \sum_{k=0}^\infty (I-D^{-1}A)^k D^{-1},
\end{align*}

Let $A,b$ be the $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*}
Obviously this matrix is strongly diagonally dominant. Compute
approximations to $x=A^{-1}b$ by
\begin{align}
  \label{eq:defxn}
  x_N = \sum_{k=0}^N (I-D^{-1}A)^k D^{-1} b,
\end{align}
for $N=0,2,5,10,20,50,100,200$. Do they converge? Plot $\|x_N-x_{200}\|$ for
these vectors, and graph $(x_N)_i$ against $i$ as in Problem 3 of Homework 4.

Using equation \eqref{eq:defxn}, find a recursion formula that expresses $x_N$
in terms of $x_{N-1}$ for $N>0$, and state the initial vector $x_0$. Compare
the recursion formula with that of the Jacobi iteration.

\points{6}


\paragraph{Problem 3 (Matrix norms).} Just as for vector norms, all possible
norms for matrices are equivalent up to a constant.
\begin{itemize}
\item[a)] Consider the $2\times 2$ matrices
  \begin{align*}
    A = 
    \begin{pmatrix}
      a & b \\ c & d
    \end{pmatrix}
  \end{align*}
  for which all entries are positive, i.e. $a,b,c,d\ge 0$. State under which
  conditions $\|A\|_1 = 1$. Among the matrices with all positive entries and
  with $\|A\|_1=1$, which matrix has the largest infinity norm,
  $\|A\|_\infty$?

\item[b)]
  If you know that the inequalities 
  \begin{align*}
    c\|v\|_q \le  \|v\|_p \le C \|v\|_q  
  \end{align*}
  hold for two vector norms $\|\cdot\|_p, \|\cdot\|_q$ with $1\le
  p,q\le\infty$, can you infer that a similar relationship
  \begin{align*}
    c'\|A\|_q \le  \|A\|_p \le C' \|A\|_q  
  \end{align*}
  with different constants $c',C'$ holds for the corresponding matrix norm
  \begin{align*}
    \|A\|_p = \max_v \frac {\|Av\|_p}{\|v\|_p}
  \end{align*}
  (and the corresponding definition of the $q$-matrix norm)?
\end{itemize}
\points{4}


\paragraph{Problem 4 (Newton's method in 2d).} Consider the function 
\begin{align*}
  g(x,y) = (x^2-1)^2 + y^2.
\end{align*}
Its two minima obviously lie at $x=\pm 1, y=0$. 

\begin{itemize}
\item[a)] Use a program for a two-dimensional Newton method to find the minima
  of $g(x,y)$ and demonstrate convergence of iterates $X_k$ towards one of
  these minima when started from $X_0=(x_0,y_0)=(2,1)$ and when started from
  $X_0=(x_0,y_0)=(-2,1)$.

\item[b)] Using only paper and pencil, show what happens if one starts from 
  $X_0=(x_0,y_0)=(0,2)$. Is the point to which the algorithm converges a
  minimum of $g(x,y)$? If not, what is happening? Is the Newton method for
  finding minima broken? (Hint: You should feel free
  to help your imagination by letting the program from part a) run for this
  choice of initial values $X_0$ and seeing where it converges. It is also
  always helpful to visualize functions for which you are looking for a
  minimum.) 
\end{itemize}
\points{5}

\end{document}

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