\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 less than 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 Describe the Choleski factorization of a matrix and its uses. Is it possible
to obtain the advantage of the Choleski factorization without the use of
squareroots?

\bigskip
\nextproblem Discuss the uses (if any) of the determinant in numerical calculations.

\nextproblem Here is an algorithm:

\smallskip
{\narrower\obeylines
{\bf input:} the $n\times n$ matrix $A$ and the $n$-vector $x$.
{\bf do until satisfied:} compute $y:= Ax$, then set $x :=y/\|y\|$.
{\bf output:} the final $n$-vector $x$.
}
\smallskip 
(a) What is this algorithm used for?

(b) State and prove a sufficient condition for the convergence of the
algorithm.

(c) Explain why the algorithm might not converge for the particular input
$$A=\pmatrix{2&1&0\cr2&3&0\cr9&-7&-4\cr}$$

(d) Suggest another iterative method which would provide the desired answer for 
this particular $A$.

\nextproblem (a) State and prove a necessary and sufficient condition on the matrix $A$ 
for Gau\ss\ elimination without pivoting to achieve its goal in an 
infinite precision environment.

(b) Give a detailed example to show that the assumption of an infinite
precision environment is essential for your answer to (a).

\nextproblem Let $P$ be the $n$-dimensional space spanned by the monomials $x,
x^2,\ldots,x^n$, and let $x_1,\ldots,x_n$ be $n$ distinct points. 
For given data $y_1,\ldots, y_n$, we look for
$p\in P$ which matches these data at the $x_j$, i.e., satisfies
$$p(x_j)=y_j\qquad j=1,\ldots,n.$$

(a) Prove or disprove the statement ``A solution for all possible data 
$y_1,\ldots,y_n$ exists if and only if there is at most one solution for some
data''.

(b) Prove that there exists a unique solution to the above interpolation
problem in case none of the $x_j$ is zero.

In your proof, you may rely on known results concerning interpolation from
$\hbox{\rm span}\{1,x,\ldots,x^n\}$.


\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.$$

\nextproblem Consider the system
$$-x_{k-2}+x_{k-1}+7x_k-x_{k+1}+x_{k+2}=y_k,\qquad k=1,2,\ldots,N$$
$$x_{-2}=x_{-1}=x_{N+1}=x_{N+2}=0$$
of linear equations.

(a) Is the system solvable? (Explain your answer.)

(b) Give a good estimate for the constant $K_N$ (which may depend on
$N$) for which
$$\|x\|_\infty\le K_N\|y\|_\infty$$
for all $y$.

(c) Give a convergent iteration method for obtaining the solution $x$ and
discuss its convergence properties.

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

Discuss (a) the stability, and (b) the convergence of the two numerical schemes
$$\eqalignno{Y_N-{3\over2}Y_{N-1}+{1\over2}Y_{N-2}&=
{h\over2}f(Y_{N-1})&(\the\problemno.2)\cr
            Y_N-{3\over2}Y_{N-1}+{1\over2}Y_{N-2}&=
{h\over4}\big[f(Y_{N-1})+f(Y_{N-2})\big]&(\the\problemno.3)\cr}$$

\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


