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

\newcommand{\x}{\boldsymbol{x}}
\renewcommand{\v}{\boldsymbol{v}}
\newcommand{\w}{\boldsymbol{w}}
\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}}
\renewcommand{\dim}{\operatorname{dim}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}


\begin{document}

\title{Numerical Methods I -- Problem Set 2}
\author{Homework due in class, September 19, 2003}
\date{Projects due September 22, 2003}
\maketitle

\noindent

\begin{enumerate}

\item Let $g\colon [a,b] \to \R$ be a contraction, i.e.
\[
  |g(x) - g(y)| \leq L \, |x-y|
\]
for some $0<L<1$ and for all $x,y \in [a,b]$.  Let $\xi$ denote the
fixed point of $g$.  Give an estimate on how many iterations you need
to guarantee, for given $\varepsilon>0$, that
\[
  |g(x) - \xi| \leq \varepsilon \,.
\]

\item As a rule of thumb, quadratic convergence doubles the number of
accurate digits each iteration.  However, this is not always true.
Give an estimate on the number of accurate digits you gain each Newton
iteration in terms of $f'$ and $f''$.

\item Work out either (a) or (b).
\begin{enumerate}
\item Prove that the secant method converges with order $q = \tfrac12
(1+\sqrt5)$.  Detailed hints are available from SM, Exercise~1.10.

\item Estimate, by performing an appropriate log-log plot in
\textsf{Octave}, the rate of convergence of the secant method.
\end{enumerate}

\item \textbf{Project:} Write three \textsf{Octave} routines to find a
zero of a function $f(x)$ by using
\begin{enumerate}
\item Newton's method with starting value $x_0$,
\item the secant method with two starting values $x_0$ and $x_1$,
\item the bisection method on an initial interval bounded by $a$ and
$b$. 
\end{enumerate}

\item \textbf{Project:} (Example from QS.)  Test your root finding
routines on each of the functions
\begin{enumerate}
\item $f(x)= \cosh x + \cos x - 3$
\item $g(x)= \cosh x + \cos x - 2$
\end{enumerate}
and compare convergence and accuracy.

\end{enumerate}
\end{document}
