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

\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}}


\begin{document}

\title{Numerical Methods I}
\author{Midterm Exam}
\date{October 17, 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}

%% \noindent
%% If $\|\x\|$ denotes some vector norm for $\x\in\R^n$, then the
%% associated norm for a matrix $A \in \R^{n\times n}$ is defined
%% \[
%%   \| A \| = \max_{\x \neq 0} \frac{\|A \x\|}{\|\x\|} \,.
%% \]
%% The condition number of a matrix is defined
%% \[
%%   \cond A = \| A \| \, \| A^{-1} \| \,.
%% \]
%% A general iterative method for solving $A\x=\b$, based on the
%% splitting $A=P+(A-P)$, is given by
%% \begin{gather*}
%%   \x_{k+1} = \x_k + P^{-1} \r_k \,,
%% \end{gather*}
%% where $\r_k=\b-A\x_k$ is the residual in the $k$th step.

%% \newpage

\begin{enumerate}

\item In the following transcript of an \textsf{Octave} session, all
output has been deleted.
\begin{verbatim}
octave:1> a=1e308; b=1.05e308; c=-1.5e308;
octave:2> a+(b+c)
ans = ..................
octave:3> (a+b)+c
ans = ..................
octave:4> a/((1+a)-a)
ans = ..................
octave:5> x=1e-15;
octave:6> 1-cos(x)
ans = ..................
octave:7> sin(x)^2/(1+cos(x))
ans = ..................
\end{verbatim}
Identify which of the following answers belongs to each of the dotted
lines.
\begin{enumerate}
\item \texttt{ans = 0}
\item \texttt{ans = Inf}
\item \texttt{ans =  5.0000e-31}
\item \texttt{ans =  5.5000e+307}
\item \texttt{warning: division by zero\\
ans = Inf}
\end{enumerate}
\hfill(10)



\item Suppose that a function has a zero in the interval $[0,1]$. Show
that the bisection method is guaranteed to approximate the zero within
a specified tolerance $\varepsilon$ after
\[
  k \geq \frac{\ln 1/\varepsilon}{\ln 2} - 1
\]
iterations.
\hfill(10)




\item Consider the matrix
\[
  A =
  \begin{pmatrix}
    1 & \varepsilon \\ \varepsilon & 1
  \end{pmatrix} \,.
\]
\begin{enumerate}
\item Compute the condition number of $A$ in a matrix norm of your
choice.  What happens if $\varepsilon$ is close to $1$?

\item Show that the Jacobi method for solving $A\x=\b$ converges when
$|\varepsilon| <1$. 

\item Show that the Gauss--Seidel method for solving $A\x=\b$
converges when $|\varepsilon| <1$.  Which method converges faster?

Hint: Recall that the Gauss--Seidel method is based on the splitting
$A=P + (A-P)$ where $P$ contains the right upper triangular entries of
$A$.  So
\[
  P =
  \begin{pmatrix}
    1 & \varepsilon \\ 0 & 1
  \end{pmatrix}
  \quad \text{and} \quad
  P^{-1} =
  \begin{pmatrix}
    1 & -\varepsilon \\ 0 & 1
  \end{pmatrix} \,.
\]
  
\end{enumerate}
\hfill(10+10+10)


\item Compute the $LU$ decomposition of the matrix
\[
  A =
  \begin{pmatrix}
  1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 
  \end{pmatrix} \,.
\]
\hfill(10)




\item Consider the sequence
\begin{gather*}
  I_0 = 1-e^{-1} \,, \\
  I_n = 1 - n \, I_{n-1} \,. 
\end{gather*}

\begin{enumerate}
\item What is the absolute condition number of computing $I_n$ in
terms of $I_{n-1}$?

What is the absolute condition number of recursively computing $I_n$
in terms of $I_0$?

\item Is this recursion a good method to compute $I_n$?  Explain!

Hint: $I_n \to 0$ as $n \to \infty$; see below.

\item \textbf{Extra credit:} Show that $I_n \to 0$ as $n \to \infty$.

Hint: Show that
\[
  I_n = \int_0^1 (1-x)^n \, e^{-x} \, dx \,.
\]


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




\item The following root finding method is a modification of the
bisection method.  It is called \emph{regula falsi}.
\begin{equation*}
  x_{k+1} = x_0 - \frac{x_k-x_0}{f(x_k)-f(x_0)} \, f(x_0) \,.
  \tag{*}
\end{equation*}
\begin{enumerate}
\item Show that the \emph{regula falsi} is consistent.

(Recall that a method is consistent if every fixed point $\xi$ of this
iteration solves the equation $f(\xi)=0$.)

\item Give an argument using Taylor expansion that the \emph{regula
falsi} is convergent with order $1$.

\item \textbf{Extra credit:} The \emph{regula falsi} is applied in the
following way.  Choose two starting values $x_0$ and $x_1$ so that
$f(x_0)\cdot f(x_1)<0$.  Compute the sequence of $x_k$ via (*).  If
$f(x_0)\cdot f(x_{k+1})>0$, re-initialize by setting $x_0:=x_k$.

Show that if $f$ is continuous, the sequence $x_k$ will always
converge to a root of $f$.

Hint: Notice that $x_{k+1}$ is the zero of the line joining the points
$(x_0,f(x_0))$ and $(x_k,f(x_k))$.  Then note that the sequence of
intervals that bracket the root has monotonic bounds.

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

\end{enumerate}
%% \newpage

%% \noindent\emph{Scratch paper}
\end{document}
