\input na.format
\def\formeq{\the\equationno}
\def\vspace{\vskip 2 truecm}
\def\hspace{\hskip.5truecm}
\def\marginal#1{{\vskip0pt\noindent\llap{#1\ }
 \vskip-\baselineskip\noindent}}
\newcount\problemno \problemno=1
\def\prob{{\marginal{\bf\the\problemno.}}\global\advance\problemno by 1}
\outer\def\problem #1\par{
  \goodbreak\noindent{\marginal{\bf\the\problemno.\enspace}}\nobreak{\rm#1}\par
  \bigskip
  \global\advance\problemno by 1
  \ifdim\lastskip<\medskipamount \removelastskip\penalty55\bigskip\fi}
\def\pts#1{(#1 points)}            % The score of a problem
\advance\hoffset by .7truecm
\advance\hsize by -.7truecm

\centerline{\bf Numerical Analysis}
\bigskip
A student taking the exam for ``breadth'' must answer three (3) questions.
A student taking the exam for ``depth'' must answer six (6) questions, with
at least three (3) chosen from problems 6--10. In either case,
the answers to three questions must be turned in after 2 hours and these
will be the only questions looked at for the ``breadth'' grade.
\bigskip

\problem In all calculations in this question you may use only the four
basic arithmetic operations.  You are asked to compute the number
$$a=\sqrt{5-\root 3 \of 2}\,.$$
\item{(a)} Suggest an iterative  method that computes $a$ with as few iterations
as possible.
\medskip
\item{(b)} Estimate the number of iterations required to obtain $a$ within an 
error not exceeding $10^{-6}$, using the initial value $a_0\approx 1.9$.
\medskip
\item{(c)} How sensitive is your method to the choice of $a_0$?
\medskip

\problem
\item{(a)} Describe the composite Simpson's rule for numerical integration. What
is the relation between this rule and polynomial interpolation?
\medskip
\item{(b)} Analyze the error of the (non-composite) Simpson's rule.
\medskip
\item{(c)} Derive a new integration rule by applying one step of Richardson's
extrapolation to Simpson's rule.
\medskip

\problem
\item{(a)} Discuss a constructive approach for the proof of the following statement:
\item{}{\sl
Every real square symmetric matrix $A$ is {\it orthogonally similar}
to a diagonal matrix.}
\medskip
\item{(b)} Does the statement remain true upon replacing 
``similar'' by ``congruent''?
\medskip
\item{(c)} Find the condition number of
$$\pmatrix{1&0&0\cr 0&-1.2&2.4\cr0& 2.4&.2\cr}$$
in the $L_2$-norm.
\medskip

\problem Let $A = (a_{ij})$ be a real $N\times N$ matrix which satisfies
$$a_{ii} \geq \sum_{j\not=i}|{a_{ij}}| + 2\equation$$
and
$$5\leq a_{ii}\leq 7\equation$$
\item{(a)} Prove that $\inv A$ exists.
\medskip
\item{(b)} Find a numerical bound for $\norm{\inv A}_{\infty}$.
\medskip
\item{(c)} Assume $A=A^T$. Find numerical bounds on
$\norm{A}_{2}$ and $\norm{\inv A}_{2}.$
\medskip


% This is problem 5.
\problem In this question $\Pi_n$ denotes the space of all polynomials of degree
$\le n$. Further, given a function $f$ defined on $[-1,1]$ we denote
$$\dist(f,\Pi_n)=\inf_{p\in\Pi_n}\norm{f-p},$$
with
$$\norm{f-p}=\sup_{x\in [-1,1]}|f(x)-p(x)|.$$
\item{(a)} Given $f(x)=x^{n+1}$, find $p\in\Pi_n$ such that
$$\norm{f-p}=\dist(f,\Pi_n).\equation$$
Prove that your $p$ indeed satisfies (\lastequation). 
\medskip
\item{(b)} For the same $f$, compute $\dist(f,\Pi_n)$.
\medskip
\item{(c)} With $f$ and $p$ as above, discuss briefly the use of the error function
$f-p$ in polynomial interpolation.
\medskip



\problem Consider the Initial-Value Problem
$$y' = f(y),\qquad y(0) = y_0.\equation$$
Consider the linear multistep method
$$Y_n + 2Y_{n-1} -3Y_{n-2} = 2h\left[ f(Y_{n-1})+f(Y_{n-2})\right]\equation$$
Discuss the consistency and stability of the method.

\problem Consider a Predictor-Corrector Method for the numerical solution of
$$\eqalign{
  y' &= f(y),\qquad 0\leq t \leq T\cr
  y(0) &= 0.\cr
}$$
{\bf Predictor} (explicit)
$$a_0Y_n = -\sum_{j=1}^k a_j Y_{n-j} + h \sum_{j=1}^k b_jf(Y_{n-j})\equation$$
\remember\pred
{\bf Corrector}
$$\tilde\ga_0Y_n = - \sum_{j=1}^L \tilde\ga_j Y_{n-j} + h \sum_{j=0}^L
  \tilde\gb_jf(Y_{n-j})\equation$$
\remember\corr
{\bf Predictor-Corrector Method}
$$\eqalign{
  Y_n^* &= -\frac{1}{a_0}\sum_{j=1}^k a_jY_{n-j}+h\frac{1}{a_0}\sum_{j=1}^k
           b_jf(Y_{n-j}) \cr
  Y_n   &= \frac{1}{\tilde\ga_0}\left[
           -\sum_{j=1}^L\tilde\ga_jY_{n-j}+h\tilde\gb_0f(Y_n^*)
           +h\sum_{j=1}^L\tilde\gb_jf(Y_{n-j}) \right]\cr
}$$
\item{(a)} Consider the predictor equation and the corrector equation as 
separate {\bf Linear Multistep Methods} to solve this problem.
{\bf Define} {\it ``order of consistency''} of these methods.
\medskip
\item{(b)} Consider the Predictor-Corrector Method. Suppose method \pred\
has order of consistency $R$. Suppose method \corr\ has order of consistency
$P$.
What is the order of consistency of the Predictor-Corrector Method?
\medskip
\item{(c)} State a theorem giving necessary and sufficient conditions for the
Predictor-Corrector Method to be {\it ``stable''}. Sketch the proof.
\medskip


\problem Consider the finite difference scheme
$$v_m^{n+1}=e^{-2b\mu}v_m^n + \frac{1-e^{-2b\mu}}{2}(v_{m+1}^n+v_{m-1}^n)$$
as an approximation to the heat equation $u_t = b\,u_{xx}$ with
$\mu=\Delta t/(\Delta x)^2.$ Discuss the stability, consistency, and 
accuracy of the scheme for solving the initial value problem.



\problem Consider the boundary value problem
\def\del{\partial}
$$-\Delta u = -\frac{\del^2u}{\del x^2}-\frac{\del^2u}{\del y^2}
               = -u^3+1\qquad\hbox{in}\quad\Omega$$
$$u=0\qquad\hbox{on}\quad\del\Omega$$
where $\Omega$ is the unit square.
\item{(a)} Describe a finite-difference scheme to solve this problem. This
scheme must produce a unique solution.
\medskip
\item{(b)} Prove that your scheme has a unique solution.
\medskip


\problem
\item{(a)} Let $\gl$ be a nontrivial linear functional on some linear space $X$.
Prove: For all $x\in X$ and all $y\in X\backslash\ker\gl$, the modified element
$x-(\gl x/\gl y)y$ is in $\ker\gl$.
\medskip
\item{(b)} Relate the abstract construction in (a) to Gauss elimination.
\medskip
\item{(c)} Relate the abstract construction in (a) to Gram-Schmidt
orthogonalization.
\medskip
\item{(d)} Describe in some detail how Gauss elimination would look if it
were carried out in the same order as Gram-Schmidt orthogonalization.
\medskip

         


\bye
