\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{Midterm Exam}
\date{March 31, 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 solve the differential equation
\[
  y'(t) = A(t) \, y(t) \,.
\]

\begin{enumerate}

\item Your choice of $A(t)$ is a time-dependent $2\times 2$ matrix
with eigenvalues as shown below.  For which values of $t$ do you
consider the system ``stiff''?  Explain \emph{briefly}!

\begin{center}
  \includegraphics{eigenvalues.eps}
\end{center}


\item You try different solvers from your solver collection: RK4 and
BDF4 with constant stepsize, and RK54 and Nordsieck-BDF4 with adaptive
stepsize.  Match the solvers to the solution graphs below, stating
\emph{briefly} one characteristic feature for each.

\begin{center}
  \includegraphics{solution.eps}
\end{center}
(Note that the curves are vertically shifted for better legibility,
and only one of the components is shown.)

\end{enumerate}
\hfill(5+10)




\item For
\[
  A = 
  \begin{pmatrix}
  2 & 1 \\ 1 & 2 
  \end{pmatrix} \,,
\]
find a plane rotation matrix $R$ such that $R^TAR$ is diagonal.
\hfill (10)



\item Let $A$ be a real symmetric $n\times n$ matrix, and set
\[
  R(\x) = \frac{\x^T A \x}{\x^T \x} \,.
\]

\begin{enumerate}
\item If $\x$ is an eigenvector of $A$, show that $R(\x)$ is the
corresponding eigenvalue.

\item From now on, let $\x$ be an arbitrary unit vector, and write
\[
  \x = \sum_{i=1}^n \alpha_i \, \v_i \,,
\]
where $\v_i$ are the orthonormal eigenvectors of $A$ with
corresponding eigenvalues $\lambda_i$.

Show that
\[
  \lambda_{\operatorname{min}} \leq R(\x) \leq
  \lambda_{\operatorname{max}} \,,
\]
where $\lambda_{\operatorname{min}}$ and
$\lambda_{\operatorname{max}}$ denote the smallest and the largest
eigenvalue of $A$, respectively.


\item Show that
\[
  \alpha_j = 1- \frac12 \, \| \x - \v_j \|^2 \,.
\]

\item \textbf{Extra credit:} Finally conclude that
\[
  R(\x) = \lambda_k + O(\| \x - \v_k \|^2) \,.
\]
\end{enumerate}
\hfill (5+5+5\textit{+10})


\item
\begin{enumerate}
\item Let $Q=Q(t)$ be a time-dependent $n \times n$ matrix that satisfies
the differential equation
\begin{equation*}
   Q' = Q S \,, \qquad Q(0) = I \,,
  \tag{*}
\end{equation*}
where $S(t)$ is a skew-symmetric $n \times n$ matrix, i.e.\ $S^T=-S$.

Show that $Q(t)$ is orthogonal for every $t\geq 0$.

\emph{Hint:} You have to check that $QQ^T=I$.  Differentiate this
relation and use the differential equation (*).

\item \textbf{Extra credit:}  Let $A$ be a time dependent matrix that
satisfies the so-called isospectral flow equation
\[
  A' = AS - SA \,, \qquad A(0)=A_0 \,,
\]
where $S$ is skew symmetric.

Show that the eigenvalues of $A$ remain unchanged under the
evolution.

\emph{Hint:} Use part (a) to conclude that $A(t) = Q^T(t) \, A_0
\,Q(t)$.
\end{enumerate}
\hfill(10\textit{+10})


\item You solve the boundary value problem
\[
  - y''(x) = g(x)
\]
on a non-uniform grid.  I.e., the step size changes from one node to
the next, and we define
\begin{gather*}
  h_k^+ = x_{k+1}-x_k \,, \\
  h_k^- = x_k - x_{k-1} \,.
\end{gather*}

\begin{enumerate}
\item Show that the local truncation error for the method
\begin{equation*}
  -2 \, \biggl(
          \frac{y_{k-1}}{h_k^- \, (h_k^- + h_k^+)}
          - \frac{y_k}{h_k^- \, h_k^+}
          + \frac{y_{k+1}}{h_k^+ \, (h_k^- + h_k^+)}
        \biggr)
  = g_k \,
  \tag{*}
\end{equation*}
is given by
\[
  T_k = \tfrac13 \, y'''(x_k) \, (h_k^- - h_k^+)
        + O(h_k^-)^2 + O(h_k^+)^2 \,.
\]

\item What is the (local) order of the method?

\item \textbf{Extra credit:} Replace the right side of (*) by
\[
  \alpha \, g_{k-1} + (1-\alpha) \, g_{k+1} \,.
\]
Determine $\alpha$ so that the local order of the method is at least
$2$. 


\end{enumerate}
\hfill(15+5\textit{+10})


\end{enumerate}
\end{document}
