\documentclass[12pt,letterpaper]{article}
\usepackage{amsmath,amssymb,verbatim}
\usepackage{epsfig}

\def\ds{\displaystyle}
\def\d{\partial}
\newcommand{\dspace}{\vskip 24pt}
\newcommand{\sspace}{\vskip 12pt}
\newcommand{\hfspace}{\vskip 6pt}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{0.0in}
\setlength{\textheight}{9in}
\setlength{\topmargin}{-0.5in}
\DeclareMathOperator{\diag}{diag} 


\begin{document}

\pagestyle{empty}
\raggedright

\begin{center}
  {\Huge MTH 654\\[2.0ex]
    Numerical Methods for Inverse Problems\\[2.0ex]
   \LARGE HW 2
  }
\dspace

\end{center}

\dspace
The objective of this project is to help students familiarize
themselves with the theoretical and computational concepts of
optimization. In addition, students will gain experience using
standard implementations of basic algorithms.


\begin{enumerate}
\item Apply Newton's method to find a minimum of $f(x)=\sin^2(x)$
  using
\begin{enumerate}
\item analytic first and second derivatives
\item analytic first and forward difference second derivatives
\item forward difference first and second derivatives
\end{enumerate}

Use an initial guess of your choice.  
For each case above, graph the iteration history of
$f(x)$ using finite difference step sizes of
$h=10^{-1},10^{-2},10^{-4},10^{-8}$ on the same plot.
Repeat for $f'(x)$.  It may also help to make a table similar to:

\begin{tabular}{|c|c|c|c|c|c|c|c|} \hline
h &$D(f)$ &$D_2(f)$ & x & f(x) & fp(x) & fpp(x)\\ \hline
0 &0 &0 &  &  &  &\\
\hline
0.1 &0 &1 &  & & &\\
0.01 &0 &1 &  &  & & \\
0.0001 &0 &1 & & &  & \\
1e-08 &0 &1 &  &  &  & \\
\hline 
0.1 &1 &1 & & &  & \\
0.01 &1 &1 & & &  & \\
0.0001 &1 &1 & & &  & \\
1e-08 &1 &1 & &  & & \\
\hline
\end{tabular}

Comment on what you observe.

\item Repeat the previous problem with $f(x)=\sin^2(x)+10^{-4}rand$
where $rand$ denotes a random number (e.g, {\tt randn(1)}).

\item      Show that if $b \in \mathbb{R}^N$ and the $N \times N$ matrix $A$ is
      symmetric and has a negative eigenvalue, then the quadratic
      functional
      \begin{equation*}
	m(x) = x^T A x + x^T b
      \end{equation*}
      does not have a minimizer.  Show that if $u$ is an eigenvector
      corresponding to a negative eigenvalue of the Hessian, then $u$ is a
      direction of negative curvature.

\item Suppose $\epsilon(x_c)$ and $\Delta(x_c)$ are errors in the
  computation of the gradient and the Hessian, respectively, at the
  Newton iterate $x_c$.  Let the Standard Assumptions hold.  Prove
  that there are constants $K$,$\delta>0$ such that if $x_c \in
  B_{\delta}(x_c)$ and 
\begin{equation}
\|\Delta(x_c)\|<\|(\nabla^2f(x^*))^{-1}\|^{-1}/4
\end{equation}
then 
\begin{equation}
\|e_+\| \leq K \left( \|e_c\|^2 + \|\Delta(x_c)\| \|e_c\| +
\|\epsilon(x_c)\| \right).
\end{equation}


\end{enumerate}


\end{document}

