\documentclass[12pt]{article}
%\usepackage{pandora,euler}
\usepackage{fullpage,amsmath,amsfonts}
\usepackage{graphicx}

\newcommand{\x}{\boldsymbol{x}}
\renewcommand{\v}{\boldsymbol{v}}
\newcommand{\w}{\boldsymbol{w}}
\renewcommand{\r}{\boldsymbol{r}}
\renewcommand{\a}{\boldsymbol{a}}
\renewcommand{\b}{\boldsymbol{b}}
\renewcommand{\c}{\boldsymbol{c}}
\newcommand{\e}{\boldsymbol{e}}
\renewcommand{\Re}{\operatorname{Re}}
\renewcommand{\Im}{\operatorname{Im}}
\newcommand{\Range}{\operatorname{Range}}
\newcommand{\Ker}{\operatorname{Ker}}
\newcommand{\Span}{\operatorname{Span}}
\newcommand{\cond}{\operatorname{cond}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\renewcommand{\d}{\mathrm{d}}

\def\nl{\vphantom\vdots\\}

\begin{document}

\title{Numerical Methods II}
\author{Final Exam}
\date{May 21, 2004}
\maketitle


%% \vspace*{\fill}
%% {\baselineskip=40pt
%% \begin{tabbing}
%% Student ID Number: \= \kill
%% Last Name: \> \rule[-2pt]{10cm}{0.3pt} \\
%% First Name:  \> \rule[-2pt]{10cm}{0.3pt} \\
%% Signature: \> \rule[-2pt]{10cm}{0.3pt} \\
%% %% Code: \> \fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
%% %% \fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
%% %% \fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
%% %% \fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
%% \end{tabbing}}


%% \vspace*{\fill}
%% \vspace*{\fill}

%% \newpage

\begin{enumerate}

\item You use three different iterative methods to find the minimum of
  the function
\[
  f(x,y) = - \frac{1}{1+x^2+a \, y^2} \,,
\]
\begin{enumerate}
\item The gradient method;
\item The Fletcher--Reeves conjugate gradient method without restart;
\item The Fletcher--Reeves conjugate gradient method with restart
  every second iteration.
\end{enumerate}
The following two graphs show the decrease of the error with the
number of iterations for two different values of $a$.
\begin{center}
  \includegraphics{convergence1.eps}\\
  \includegraphics{convergence7.eps}
\end{center}
Match the method used to the graphs shown (the labeling is the same in
both plots!), and explain your choice.
\hfill (10)

\item Show that the stochastic differential equation
\begin{gather*}
  \d X = \tfrac13 \, X^{1/3} \, \d t
         + X^{2/3} \, \d W \,, \\
   X(0) =X_0 \,,
\end{gather*}
is solved by
\[
  X(t) = \bigl( X_0^{1/3} + \tfrac13 \, W(t) \bigr)^3 \,.
\]
\hfill (10)


\item Apply the Euler--Maruyama method
\[
  X_{j+1} = X_j + f(X_j) \, \Delta t + g(X_j) \, \Delta W_j
\]
to the stochastic differential equation
\[
  \d X = \mu \, X \, \d W \,.
\]
Show that
\[
  \mathbb{E} \bigl[|X_{j+1}|^2\bigr]
  = \bigl( 1 + \Delta t \, |\mu|^2 \bigr) \,
  \mathbb{E} \bigl[|X_{j}|^2\bigr] \,.
\]
\hfill (10)

\item On the interval $[0,2]$, consider the boundary value problem
\begin{gather*}
  -y''(x) = f(x) \,, \\
  y'(0) = y'(2) = 0 \,.
\end{gather*}
\begin{enumerate}
\item Away from the boundary, the solution is approximated by
\[
  -\frac{y_{j-1} -2 y_j + y_{j+1}}{h^2} = f_j \,.
\]
Show that the local truncation error of this method is of order $2$.

\item We approximate the boundary conditions by
\[
  \frac{y_1-y_0}h = 0 \,,
\]
with a corresponding expression for the second boundary condition.
Show that this approximation is accurate only to order $1$.

\item Suggest an improvement that ensures the method is of order $2$
  up to the boundary.

\item Write out the resulting system of linear equations of your
  method, or of the method given in (a) and (b), with only
  three nodes $x_0=0$, $x_1=1$, and $x_2=2$.  Is the resulting matrix
  invertible?

\item Do you expect the solution to the original problem to be unique?
Explain.

  (Think of what happens to constants\ldots)

\item \textbf{Extra credit:} Can you think of a reasonable condition
  that would make the solution unique?  Note that you must not add a
  third boundary condition, as it would generically overdetermine the
  system.
  
\end{enumerate}
\hfill(5+5+5+5+5\textit{+10})

\item
Recall that the Householder reflector about the hyperplane
  normal to $\v$ is the matrix
\[
  H = I - 2 \, \frac{\v \v^T}{\v^T \v} \,.
\]
\begin{enumerate}
\item What are the eigenvalues of $H$?

\emph{Hint:} What do you get by applying $H$ to $\v$, or to a vector
orthogonal to $\v$?

\item Find $\v$ and $\alpha$ such that
\[
  H \begin{pmatrix} 0 \\ 4 \\ 3 \\ 0 \end{pmatrix}
  = \begin{pmatrix} \alpha \\ 0 \\ 0 \\ 0 \end{pmatrix} \,.
\]
\end{enumerate}
\hfill(10+10)

\item You minimize the function
\[
  f (x,y) = x^2 - y^2
\]
where $x$ and $y$ are constrained to the unit circle, i.e.
\[
  h(x,y) = x^2 + y^2 -1 = 0 \,.
\]
\begin{enumerate}
\item State the exact solution to this problem.

(No computation required, the problem is simple enough to spot the
answer.)

\item Solve the problem using the quadratic penalty method, i.e.\
minimize
\[
  p_\alpha(x,y) = f(x,y) + \alpha \, h^2(x,y) \,.
\]
Compute the minimizer $(x_\alpha^*,y_\alpha^*)$ of the penalized
problem explicitly.

\item Show that $h(x_\alpha^*,y_\alpha^*) \to 0$ as $\alpha \to \infty$.
\end{enumerate}
\hfill(10+10+5)
\end{enumerate}
\end{document}
