\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 In a graphics program destined for a very small machine, the 
distance 
$$d:=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$$
between two points $(x_1,y_1)$ and $(x_2,y_2)$ needs to be computed, but, for
reasons of speed and memory requirements, the direct use of the squareroot
function is not desirable.

How could you compute $d$ to `graphic accuracy', say within 1\%, using just 
arithmetic operations (and comparisons)? Could you do it in about 10 
floating point operations?

(Hint: Assuming $|x_1-x_2|\ge|y_1-y_2|$, one has $d=|x_1-x_2|\sqrt{1+r}$ with
$r\in[0,1]$.)
\bigskip
\nextproblem 
Consider the matrix
$$A:=\left[\matrix{
3&1&0&0&0\cr
-1&-7&0&1&0\cr
0&1&6&1&0\cr
{1\over2}&-1&0&11&0\cr
0&1&0&0&-3\cr}\right]$$
\item{(a)} Prove that all eigenvalues of $A$ are real and simple.
\item{(b)} Prove that $A$ is diagonalizable (under similarity).

\bigskip
\def\ga{\alpha}
\nextproblem 
We are given three points $(x_1,y_1,c_1)$, $(x_2,y_2,c_2)$, $(x_3,y_3,c_3)$ in 
3-space and wish to find a (bivariate) polynomial $p$ for which
$$p(x_j,y_j)=c_j, \qquad j=1,2,3.$$
\item {(a)} Explain why it is not always possible to solve this problem with a
{\it linear}
polynomial 
(i.e., $p(x,y)=\ga_0+\ga_1x+\ga_2y$ for some constants $\ga_0$,
$\ga_1$, $\ga_2$).
\item{(b)} Is it always possible to solve the problem with a quadratic
polynomial 
(i.e., $p(x,y)=\ga_0+\ga_1x+\ga_2y+ \ga_3x^2+\ga_4xy+\ga_5y^2$ for some 
constants $\ga_0$, $\ga_1$, $\ga_2$, $\ga_3$, $\ga_4$, $\ga_5$)?

\nextproblem 
Discuss a matrix bisection method for finding the eigenvalues of a real
symmetric matrix.

\nextproblem 
What is the best you can say about the number $\int_0^1 f(x)dx$ if all you 
know about $f$ is that (i) $f(0)=0$, (ii) $f(1)=1$, (iii) $\sup_{0\le
x\le1}|Df(x)|\le2$? (Here, $Df$ denotes the first derivative of $f$.)

\nextproblem 
\item{(a)} Prove that Simpson's rule is exact for cubic polynomials and
conclude from this that the error in the composite Simpson's rule is $O(h^4)$
when applied to any sufficiently smooth function.
\item{(b)} Prove that the composite Simpson's rule converges for all continuous
functions.

\vfill\eject
\nextproblem
\item{(a)} Define the term `approximate inverse' (of a bounded linear map).
\item{(b)} Give an instance in numerical calculations in which an
approximate inverse is essential.

\nextproblem Consider the boundary value problem
$$\Delta u={\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.$$

\def\gD{\Delta}
\def\gd{\delta}
\nextproblem 
Show that the finite difference approximation
$$\eqalign{
w_m^n &= v_m^n + {1\over8}\gD t\,b\,\gd^2v_m^n\cr
v_m^{n+1} &= v_m^n + \gD t\,b\,\gd^2w_m^n\cr}
$$
for the heat equation $u_t=bu_{xx}$ (with $b>0$) is stable for $b\gD \le
2(\gD x)^2$.

\nextproblem Consider the initial value problem
$$y'(t)=f(t,y(t)),\qquad y(0)=y_0.\equation{1}$$

Construct a two-step linear multistep method for its (approximate) solution
which is (i) 2nd order accurate, and (ii) unstable.

\bye
\nextproblem Show that the finite difference scheme
$$\eqalign{w^n_m&=v^n_m+{1\over 4}\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(\Delta x)^2$.


\bye