\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 I}
\author{Final Exam}
\date{December 12, 2003}
\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 the composite trapezoidal rule to integrate various functions on
the interval $[0,2\pi]$.  The following graph is a log-log plot of the
error as a function of the number of partitions.
\begin{center}
  \includegraphics{loglog.eps}
\end{center}
Match the functions $f(x)$, $g(x)$, $h(x)$, and $j(x)$ to the
following expressions and \emph{justify your choice briefly}:
\begin{enumerate}
\item $\displaystyle \sqrt{x}$
\item $\displaystyle x^2$
\item $\displaystyle (\sin x)^2$
\item $\displaystyle 
\begin{cases}
1 & \text{for } x<1 \\
0 & \text{otherwise}
\end{cases}$

\end{enumerate}
\hfill(10)



\item
\begin{enumerate}
\item Compute the $QR$ decomposition of
\[
  A = 
  \begin{pmatrix}
  1 & 1 \\ -1 & 0 \\ 1 & 2 \\ 0 & 1
  \end{pmatrix} \,.
\]
\item Use the $QR$ decomposition to find the least square solution to
$A\x=\b$ where
\[
  \b = 
  \begin{pmatrix}
  2 \\ 1 \\ 2 \\ 3
  \end{pmatrix} \,.
\]
\end{enumerate}
\hfill(10+10)



\item 
\begin{enumerate}
\item Show that you do not need pivoting when computing the $LU$
decomposition of the matrix
\[
  A = 
  \begin{pmatrix}
  1 & 2 \varepsilon & 0 \\
  \varepsilon & 1 & \varepsilon \\
  0 & 2 \varepsilon & 1
  \end{pmatrix}
\]
whenever $|\varepsilon| < \tfrac12$.

\item \textbf{Extra credit:} Consider the tridiagonal matrix
\[
  \begin{pmatrix}
    1 & a_1 & & & \cdots & 0 \nl
    b_2 & 1 & a_2 & & & \vdots \nl
      & b_3 & 1 & a_3 \nl
      & & \ddots & \ddots & \ddots \nl
    \vdots & & & b_{n-1} & 1 & a_{n-1} \nl
    0 & \cdots & & & b_n & 1 \nl
  \end{pmatrix} \,.
\]
Based on your experience from part (a), conjecture and prove a
sufficient condition on $a_i$ and $b_i$ for being able to perform $LU$
decomposition without pivoting.

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

\item
\begin{enumerate}
\item Solve the logistic differential equation 
\begin{gather*}
  \dot y = \mu \, y + y^2 \,, \\
  y(0) = y_0  \,,
\end{gather*}
where $\mu \neq 0$.

\item Find the critical points, i.e.\ the zeros of the right hand side
of the logistic equation.

\item Determine the stability of the critical points.

(Note that for a scalar equation $\dot y=f(y)$, a critical point
$y_{\operatorname{crit}}$ is \emph{linearly stable} if
$f'(y_{\operatorname{crit}})<0$, \emph{linearly unstable} if
$f'(y_{\operatorname{crit}})>0$ and \emph{linearly neutrally stable}
if $f'(y_{\operatorname{crit}})=0$).
\end{enumerate}
\hfill(10+5+5)



\item The following method for solving the differential
equation
\[
  y' = f(y)
\]
is called the \emph{trapezoidal rule}:
\[
  y_{n+1} = y_n + h \, \frac{f(y_n)+f(y_{n+1})}2 \,.
\]
\begin{enumerate}
\item Classify the method (implicit or explicit, one-step or
multi-step, linear or nonlinear).

\item Show that you can derive the trapezoidal rule by writing the
differential equation in integral form
\[
  y(t_n+h) = y(t_n) + \int_{t_n}^{t_n+h} f(y(t)) \, \d t
\]
and approximating the integrand by an appropriate Lagrange
interpolating polynomial.

\item Show that the trapezoidal rule is of order $2$.

Hint: you may refer to your computation in part (b), or work out the
local truncation error.

\item Show that the region of absolute stability is the left half of
the complex $\lambda h$ plane.

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

\item Consider an implicit one-step method of the form
\[
  y_{n+1} = y_n + h \, \Phi (y_{n+1}) \,,
\]
where $\Phi$ satisfies a Lipshitz condition, i.e.
\[
  |\Phi(x)-\Phi(y)| \leq L \, |x-y|
\]
for all $x,y$ contained in some bounded set $D$.

\begin{enumerate}
\item Show that simple iteration
\begin{gather*}
  \eta_{k+1} = g(\eta_k) \,, \\
  \eta_0 = y_n
\end{gather*}
with $g(\eta) = y_n + h \, \Phi(\eta)$ will converge to $y_{n+1}$
whenever $hL<1$.

Note: you may assume without further analysis that the iterates never
leave $D$.

\item \textbf{Extra credit:} Would you use simple iteration when
applying an implicit method to a stiff system, i.e.\ to a differential
equation that has (in its linearization) a negative eigenvalue of much
larger magnitude than all the others?  Explain.
\end{enumerate}
\hfill(10\textit{+10})
\end{enumerate}
\end{document}
