\input format.tex
\centerline{Numerical Analysis}
\bigskip
A student taking the exam for ``breadth'' must answer three (3) questions and
these must be handed in after two hours. A student taking the exam for
``depth'' must answer six (6) questions, with at least three (3) chosen from
problems 6-10.
\newcount\problemno\problemno=0
\def\nextproblem{\advance\problemno by
1\bigskip\bigskip{\bf\the\problemno.}\hskip2em}
\def\equation#1{\eqno{(\the\problemno.#1)}}

%\magnification=1200
\nextproblem  
\item{(a)} Describe the Gau\ss-Seidel iteration for the linear system
$$\eqalign{x+.1y&=5\cr 8x+y&=2\cr}$$
and analyze its convergence.
\item{(b)} How can the $\infty$-norm of the iteration matrix
be used, in this case, to determine the convergence/divergence of the method?
\item{(c)} Would the Jacobi iteration converge for the above system?





\bigskip
\nextproblem  Consider the following $n\times n$ tridiagonal matrix:
$$A=\pmatrix{7&2&0&0&.&.&.& &&0\cr
			 2&7&2&0&0&.&.&.&&0\cr
             0&2&7&2&0&.&.&.&&0\cr
			 .&.&.&.&.&.&.&.&&.\cr
			 0&.&.&.&&&0&2&7&2\cr
			 0&.&.&.&&&&0&2&7\cr}$$
Provide bounds for the $\infty$-condition number and the 2-condition number of
this matrix $A$.

\noindent{\bf Hint:} Recall that
$$\eqalign{\|x\|_\infty&=\max\{|x_k|:\ k=1,...,n\},\cr
		   \|x\|_2&=\sqrt{\sum_{k=1}^n |x_k|^2},\cr}$$
and the condition number of $A$ is $\|A\| \|A^{-1}\|$, with e.g.,
$\|A\|=\sup {\|Ax\|\over \|x\|}$


\bigskip
\nextproblem 
\item{(a)} Give an example of a real invertible
symmetric matrix $A$ and an initial guess
$x_0\ne 0$, for which the following version 
$${\widetilde x_{k+1}}=Ax_k,\quad x_{k+1}={{\widetilde 
x_{k+1}}\over\|{\widetilde x_{k+1}}\|}$$
of the power method does not converge.
\item{(b)} State and prove a necessary and sufficient condition on the real
invertible symmetric matrix $A$ for the power method to converge,
{\sl regardless of the initial guess $x_0\ne 0$}.



\nextproblem The following is an algorithm for the evaluation of the cubic
polynomial $$p(x)=ax^3+bx^2+cx+d$$ at the infinite sequence of points
$$a_j=a+jh,\ j=0,1,2,...$$
(where $a$ and $h$ are some fixed numbers):



\smallskip
{\narrower\obeylines
{\bf Step 1:} Precompute (in any possible way) the numbers
			  $\alp=p(a_3)$
			  $\bet=h\  p[a_2,a_3]$
			  $\gam=2h^2\ p[a_1,a_2,a_3]$
			  $\del=6h^3\ p[a_0,a_1,a_2,a_3]$.
(This requires the values $p(a_0)$, $p(a_1)$, $p(a_2)$ and  $p(a_3)$.)
{\bf Step 2:} For $j=4,5,6,...$ do:
			  $\gam\longleftarrow \gam+\del$
			  $\bet\longleftarrow \bet+\gam$
			  $\alp\longleftarrow \alp+\bet$
			  $p(a_j)\longleftarrow \alp$
}

\medskip 
Show that the numbers $p(a_4),p(a_5),...$ obtained in this way are indeed the
required values of $p$. ({\bf Hint:}  show that the number $\bet$ and $\gam$
obtained in each iteration of {\bf Step 2} are $h\ p[a_{j-1},a_j]$ and
$2h^2\ p[a_{j-2},a_{j-1},a_j]$ resp.)

\bigskip
\nextproblem 
In order to find a solution for
$$x^2=1+\ln x,$$
we use the fixed-point iteration
$$x_{k+1}={1+\ln x_k\over x_k},$$
with $x_0=1.5$.
\item{(a)} Prove that $\lim_{k\to\infty}x_k=1$.
\item{(b)} Prove that the convergence is faster than that of the bisection
method.
\item{(c)} Is $x_0=.6$ a better initial guess?

\bigskip
\nextproblem 
Show that the composite trapezoid rule 
$$T_Nf\approx\int_a^b f(x)\;dx,$$
with $N$ equally spaced points on $[a,b]$, converges for any function $f$
continuous on $[a,b]$.


\nextproblem 
Consider the boundary value problem
$${\partial^2u\over\partial x^2}+{\partial^2u\over\partial 
y^2}-(1+{1\over2}\sin x)u= 1+x^2\qquad\hbox{\rm in\ } \Omega\equation{1}$$
$$u=0\qquad\hbox{\rm on\ }\partial\Omega\equation{2}$$
Let $\Omega$ be the unit square, i.e., $0<x,y<1$. Consider the finite
difference equation
$$U_{k+1,j}+U_{k-1,j}+U_{k,j+1}+U_{k,j-1}-[4+h^2(1+{1\over2}\sin 
kh)]U_{kj}=(1+(kh)^2)h^2$$
for $1\le k,j\le N$, and
$$U_{k,0}=U_{k,N+1}=U_{0,j}=U_{N+1,j}=0,$$
with $h:=1/(N+1)$.

(a) Discuss the convergence of $U_{kj}$ to $u(x,y)$.

(b) Obtain a good bound for the finite difference solution, i.e., an $M$ for
which
$$|U_{kj}|\le M\qquad \hbox{\rm for\ all\ } k,j,h.$$

\nextproblem Consider the boundary value problem
$$y''-100y=1,$$
$$y(0)=0,\ y(1)=1.$$
Describe in detail how you would solve this problem numerically using
the ``shooting method".

\noindent Your discussion should include some discussion of the reasons
why (or why not) you might use ``parallel shooting".



\bigskip
\nextproblem Consider, for the initial value problem
$$y'=-y,\ y(0)=1,\equation{1}$$
each of the following two multistep methods:
$$ Y_{k+1}-{3\over 2}Y_k+{1\over 2} Y_{k-1}=-{1\over 2}h Y_k,\leqno{(a)}$$
$$Y_0=1, \ Y_1=1-h.$$
\smallskip
$$Y_{k+1}+Y_k-2Y_{k-1}=-3h Y_k,\leqno{(b)}$$
$$Y_0=1,\ Y_1=1-h.$$
Discuss the consistency, stability, numerical stability and convergence of these
methods.

If you had to solve this problem {\sl numerically} using one of these
methods, which would you choose?

\nextproblem Show that the finite difference scheme
$$\eqalign{w^n_m&=v^n_m+{1\over 8}\Delta t\;b\;\delta^2v^n_m\cr 
v^{n+1}_m&=v^n_m+\Delta t\;b\;\delta^2w^n_m\cr}$$
for the heat equation $u_t=b u_{xx}$ (with $b>0$) is stable for 
$b\Delta t\le 2(\Delta x)^2$.


\bye