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

\newcommand{\x}{\boldsymbol{x}}
\renewcommand{\v}{\boldsymbol{v}}
\newcommand{\w}{\boldsymbol{w}}
\renewcommand{\a}{\boldsymbol{a}}
\renewcommand{\b}{\boldsymbol{b}}
\renewcommand{\r}{\boldsymbol{r}}
\newcommand{\e}{\boldsymbol{e}}
\renewcommand{\Re}{\operatorname{Re}}
\renewcommand{\Im}{\operatorname{Im}}
\newcommand{\Range}{\operatorname{Range}}
\newcommand{\Ker}{\operatorname{Ker}}
\newcommand{\Span}{\operatorname{Span}}
\renewcommand{\dim}{\operatorname{dim}}
\newcommand{\R}{\mathbb{R}}

\begin{document}

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

% \newpage

\begin{enumerate}

\item The following graphs compare the performance of the bisection,
Newton, and secant root finding method for two different functions.

The first test is for finding the root at $x=0$ of the function
\begin{equation*}
  f(x) = x + x^2 \, \sin x \,.
\end{equation*}
\begin{center}
  \includegraphics[width=10cm]{history-f.eps}
\end{center}

The second test is for finding the root at $x=0$ of the function
\begin{equation*}
  g(x) = 
  \begin{cases}
    x + x^2 \, \sin \frac1x & \text{for } x \neq 0 \,,\\
    0 & \text{for } x = 0 \,.
  \end{cases} 
\end{equation*}
\begin{center}
  \includegraphics[width=10cm]{history-g.eps}
\end{center}

\begin{enumerate}
\item Identify methods A, B, and C.  (The labeling in the two graphs
is the same.)

Comment briefly on each match.

\item \textbf{Extra credit.}  Analyze why one of the methods fails so
badly for finding the root of $g$ while the others do just fine.

\end{enumerate}
\hfill(10\textit{+10})
%\newpage


\item The secant method, which can be written as
\begin{equation*}
  x_{k+1} 
  = x_k - \frac{x_k-x_{k-1}}{1 - \dfrac{f(x_{k-1})}{f(x_k)}} \,,
\end{equation*}
involves subtraction of almost equal numbers as the sequence
approaches a limit.  Yet, the method proves very robust in practice.
We shall thus analyze the propagation of rounding errors for the
secant method.

\begin{enumerate}
\item Assume that all operations are exact \emph{except} for the
evaluation of $f$.  Why can we expect that this simplified analysis
still captures the essential error behavior of the secant method?

\item Show that one step of the secant method in floating point is
approximately 
\begin{equation*}
  x_{k+1} \approx x_k - (x_k - \xi) \, 
  \frac1{1 - \delta \, \dfrac{x_{k-1}-\xi}{x_k - x_{k-1}}} \,,
  \tag{*}
\end{equation*}
where $\xi$ denotes a simple root of $f$, for some $\delta \ll 1$.

Hint: It is easiest to write
\begin{equation*}
  \operatorname{fl} \biggl( \dfrac{f(x_{k-1})}{f(x_k)} \biggr)
  = \dfrac{f(x_{k-1})}{f(x_k)} \, (1+\delta) \,,
\end{equation*}
then use truncated Taylor series to estimate the quotient.

\item How does (*) imply that the secant method is robust to rounding
errors?

\end{enumerate}
\hfill(5+10+5)
% \newpage
% \mbox{}
% \newpage

\item Compute the $LU$ factorization without pivoting of the matrix
\begin{equation*}
  A =
  \begin{pmatrix}
    1 & 2 & 3 \\
    2 & 5 & 8 \\
    3 & 8 & 14 \\
  \end{pmatrix} \,.
\end{equation*}
\hfill(15)
%\newpage


\item 
\begin{enumerate}
\item Prove that if $A \in M(n\times n)$ is positive definite, then
all diagonal entries must be positive.

\item Let $A \in M(n\times n)$ be symmetric and positive definite,
with $A=L+D+R$ denoting the splitting of $A$ into its lower left
triangular, diagonal, and upper right triangular parts (as in the
derivation of the Jacobi and Gauss--Seidel algorithms).

Show that the so-called \emph{symmetric Gauss--Seidel preconditioner}
\begin{equation*}
  B_{\text{SGS}} = (D+R) \, D^{-1} \, (D+L)
\end{equation*}
is indeed symmetric and positive definite.

\end{enumerate}
\hfill(10+10)
%\newpage

\item Let 
\begin{equation*}
  A =
  \begin{pmatrix}
    \varepsilon & 1 \\ 1 & \varepsilon
  \end{pmatrix}
\end{equation*}
with $\lvert \varepsilon \rvert < 1$.

\begin{enumerate}
\item Show that the Jacobi method for solving $A\x=\b$ does not
converge for any choice of right hand side $\b$ and starting vector
$\x_0$. 

\item Suggest a ``Jacobi method with pivoting'' so that the modified
Jacobi iteration converges for the given matrix $A$.
\end{enumerate}
\hfill(10+10)
%\newpage

\item 
\begin{enumerate}
\item State the definition of the norm of a matrix induced by a vector
norm; state the definition of the condition number of a matrix.

\item Let $A \in M(n \times n)$ be invertible and $\b \in \R^n$.  Let
$\x^*$ denote the exact solution to the linear system $A\x^* = \b$ and
let $\x$ denote an approximation to $\x^*$.  Show that
\begin{equation*}
  \frac{\lVert \x^* - \x \rVert}{\lVert \x^* \rVert}
  \leq \kappa(A) \, \frac{\lVert \b - A \x\rVert}{\lVert \b \rVert}
\end{equation*}
where the vector norm $\lVert \cdot \rVert$ is arbitrary, and the
condition number is defined with respect to the induced matrix norm.
\end{enumerate}
\hfill(5+10)

\end{enumerate}
% \newpage
% \mbox{}


\end{document}
