\magnification\magstep 1
\headline={\rlap{\bf Numerical Analysis} \hfil {Fall, 1988}}
\newdimen\digitwidth \setbox0=\hbox{\rm 0}\digitwidth=\wd0
\parindent=5\digitwidth \parskip=\medskipamount
\everypar={\noindent\hangindent=5\digitwidth}
\def\section#1{\refcount=0\bigskip\noindent{\bf #1}\smallskip\ignorespaces}
\newcount\refcount
\def\problem{\global\advance\refcount by 1 \item{\bf \the\refcount.}}
\def\subproblem#1{\itemitem{#1}}


\section{\bf Instructions}

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 chosen from problems 6--10.
The answers to three of the questions must be handed in after two (2) hours.


\problem
Consider the function $f$ defined by
$$
f(x) := x^\alpha + x^{\alpha + 2}
$$
for $x \in [0,\infty)$;
here $0 < \alpha < 1$.

\subproblem{(a)}
Show that for each $y \in [0,\infty)$
there is a unique $x$ such that $y = f(x)$.

\subproblem{(b)}
Describe an algorithm, based on the secant method,
to obtain $x$ for any prescribed value~$y$.
This method requires two initial iterates for $x$;
be sure to explain how these iterates are chosen.
{\sl Hint\/}:  The choice of initial iterates depends on $y$.

\subproblem{(c)}
Prove that this method converges for all $y$.
{\sl Hint\/}:  Exploit the local convexity or concavity of $f$.

\subproblem{(d)}
Suggest a way to minimize the number of iterations required
by carefully choosing the initial approximations.
This is important especially when $y$ is nearly zero or $y$ is large.


\problem
Consider the two schemes
$$
y_{n+1} = y_{n-1} + 2 h f(x_n,y_n)
 \eqno (I)
$$
and
$$
y_{n+1} = y_n + {h \over 2} \left[ f(x_n,y_n) + f(x_{n+1},y_{n+1}) \right]
 \eqno (II)
$$
for approximating the solution of an initial-value problem
$y^\prime (x) = f(x,y(x))$ with $y(x_0) = y_0$.

\subproblem{(a)}
Show that the local discretization errors for schemes $(I)$ and $(II)$
are ${1 \over 3} h^3 y^{\prime\prime\prime}(\xi)$
and $- {1 \over 12} h^3 y^{\prime\prime\prime}(\xi)$, respectively.

\subproblem{(b)}
Describe the algorithm for a predictor-corrector
method based on schemes $(I)$ and $(II)$.

\subproblem{(c)}
Use the results of (a) to calculate an extra
correction that improves the method of part (b).
How else can the estimates of (a) be used in the algorithm?

\subproblem{(d)}
In place of scheme $(I)$ one might use the forward Euler scheme.
Why is part (c) impossible to carry through if Euler's scheme were used?

\subproblem{(e)}
What possible disadvantage is there in using $(I)$
for an initial-value problem?


\problem
Consider the linear system
$$
Ax = b \ ,
$$
where $A$ is a {\sl singular\/} $n \times n$ matrix;
suppose that this equation has a solution $x = x_*$.
Given a nonsingular matrix $M$,
write $A = M - N$ and consider the iteration scheme
$$
M x^{(k+1)} = N x^{(k)} + b \ , \quad k = 0, 1, \ldots \ ,
$$
with $x^{(0)} = 0$.

Give necessary and sufficient conditions on $K = M^{-1} N$
in order that $x^{(k)} \to x_*$ as $k \to \infty$.


\problem
For the initial-value problem
$$
\eqalign{
y' &= f(y) \cr
y(0) &= y_0 \cr
}
$$
consider the predictor-corrector method
$$
\eqalignno{
Y^*_{n+r} &= \sum_{j=0}^{r-1} a_j Y_{n+j}
 + h \sum_{j=0}^{r-1} b_j f(Y_{n+j}) &(I)\cr
Y_{n+r} &= \sum_{j=0}^{r-1} \alpha_j Y_{n+j}
 + h \sum_{j=0}^{r-1} \beta_j f(Y_{n+j})
 + h \beta_r f(Y^*_{n+r}) &(II)\cr
}
$$
with $\beta_r \ne 0$.
Assume:  (i) that the implicit multistep scheme
$$
Y_{n+r} = \sum_{j=0}^{r-1} \alpha_j Y_{n+j}
 + h \sum_{j=0}^r \beta_j f(Y_{n+j})
$$
is stable and accurate of order $q \ge 1$;
and (ii) that the explicit multistep scheme
$$
Y_{n+r} = \sum_{j=0}^{r-1} a_j Y_{n+j}
 + h \sum_{j=0}^{r-1} b_j f(Y_{n+j})
$$
is unstable and accurate of order $q - 1$.

Is the predictor-corrector method convergent
and accurate of order $q$?
Supply a proof of your answer.


\vfil
\eject

\problem
Consider the following problem in numerical differentiation:
You are given the value of a bivariate function $f$
at three distinct points $a$, $b$, and $c$ in the plane.
>From this information, you want to approximate,
in some reasonable way,
the value at 0 of the partial derivative $D_1 f$
({\sl i.e.}, the partial derivative of $f$
with respect to its first argument).

\subproblem{(a)}
Propose (and defend) a particular way of solving this problem.

\subproblem{(b)}
Give an estimate, in powers of $h$,
of the error in your approximation when $f$ is smooth
and $a$, $b$, and $c$ lie within a distance $h$ from 0.

\subproblem{(c)}
Could you improve the estimate in part (b)
by choosing $a$, $b$, and $c$ carefully?
If so, how?
What is the highest power of $h$ that you can hope for?

\problem
Let $X$ denote the Banach space
$C[0,1]$ equipped with the uniform norm $\|\cdot\|_\infty$.

\subproblem{(a)}
Describe Nystrom's method for solving the integral equation
$$
f - \int_0^1 k(\cdot,t) f(t) dt = g
$$
of the second kind for $f \in X$.
Here $g \in X$ 
and the kernel $k$ is continuous,
so that the linear map $K:X \to X$ defined by
$$
f \mapsto \int_0^1 k(\cdot,t) f(t) dt
$$
is continuous.

\subproblem{(b)}
Let $K_n$ denote the approximation to $K$
provided by Nystrom's method with $n$~quadrature points,
and assume that the method converges as $n \to \infty$.
Prove or disprove:  $\lim_{n \to \infty} \| K - K_n \| = 0$.


\problem
Let $(x_n,y_n)$, $n = 1, \ldots, N$, be a given set of data points.
Suppose that these data are to approximated,
in the sense of least squares,
by a function that is linear combination of the basis functions
$\phi_k$, $k = 1, \ldots, K$, where $K \le N$.

\subproblem{(a)}
Construct a matrix $A$ and a vector $b$ such that
the least squares problem reduces to the following
minimization problem:
$$
\hbox{
find $x$ for which $\| A x - b \|_2$ is minimized.
} \eqno (*)
$$

\subproblem{(b)}
Show that the problem $(*)$ always has a solution.

\subproblem{(c)}
Under what conditions does the minimization problem $(*)$
have a unique solution?

\subproblem{(d)}
Suppose that these conditions for uniqueness are not met.
Suggest a method for choosing an ``optimal'' solution.


\vfil
\eject

\problem
The elliptic partial differential equation
$$
{\partial^2 u \over \partial x^2}
 + {\partial^2 u \over \partial y^2} = -1 + u^2
$$
on the unit square ($0 \le x,y \le 1$),
with boundary conditions $u = 0$,
has the finite difference approximation
$$
{1 \over h^2} \left[
 U_{i+1,j} + U_{i-1,j} + U_{i,j+1} + U_{i,j-1} - 4 U_{i,j} \right]
  = -1 + (U_{i,j})^2 \ .
$$
Here $i,j = 1, \ldots, N$,
$h = \Delta x = \Delta y = 1/(N+1)$,
and, by convention, $U_{i,j} := 0$
when $i$ or $j$ is either 0 or $N+1$
({\sl i.e.}, on the boundary).

\subproblem{(a)}
Show that if we consider only solutions such that
$U_{i,j} \ge 0$ for all $i,j$,
then there exists a unique solution
and it satisfies $0 \le U_{i,j} < 1$.

\subproblem{(b)}
Show that the following iterative method converges
to the solution of part (a):
$$
U^{n+1}_{i,j}
 + {h^2 \over 4} \left(U^{n+1}_{i,j}\right)^2
= {h^2 \over 4} + {1 \over 4}
 \left[ U^n_{i+1,j} + U^n_{i-1,j} + U^n_{i,j+1} + U^n_{i,j-1} \right]
$$
for $i,j = 1, \ldots, N$, where $U^0_{i,j} = 0$.
{\sl Hint\/}:  Use the fact that the function $g$ defined
by $g(x) = x + h^2 x^2 / 4$ increases monotonically for $x \ge 0$.


\problem
Give a finite-difference scheme
for solving the partial differential equation
$$
u_t = u_{xxx} \, \quad \hbox{for} \  x \in {\bf R} \ , \ t \ge 0 \ .
$$
The scheme must be stable
and (at least) first-order accurate in time
and second-order accurate in space.
Justify your choice.


\problem
Consider the linear system
$$
Ax = b \ ,
 \eqno (*)
$$
where $A$ is an $m \times n$ matrix.
Recall that a matrix $B_L$ is a {\sl left inverse\/} for $A$
in case $B_L A = I_n$,
and similarly that $B_R$ is a {\sl right inverse\/} for $A$
if $A B_R = I_m$.

\subproblem{(a)}
Show that if $A$ has a right inverse,
then system $(*)$ has at least one solution
(although it may have more).
Show that if $A$ has a left inverse,
then system $(*)$ has at most one solution
(although it may have none).

\subproblem{(b)}
Define what one might mean by saying that $A$ is ``nonsingular.''
Prove that if $A$ is nonsingular,
then it has right and left inverses,
and that all its right and left inverses coincide.

\subproblem{(c)}
Assume that $A$ is nonsingular,
and let $C$ be an approximation to $A^{-1}$.
Why is it possible for $C$ to be a ``good'' left inverse for $A$
but a ``bad'' right inverse, and {\sl vice versa}.
(Your answer should specify what ``good'' and ``bad'' mean here.)

\subproblem{(d)}
Assume that $A$ is nonsingular,
and let $C$ be the approximation to $A^{-1}$
computed by Gaussian elimination (in finite-precision arithmentic).
Is $C$ a ``good'' left inverse or a ``good'' right inverse?
If you decide that it is one rather than the other,
how would you compute the other kind well?

\bye
