\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{Fall Semester 2005}
\date{Due September 23, 2005}
\maketitle

\noindent

\begin{enumerate}

\item (Convergence acceleration).  Many linearly convergent iteration
schemes admit an asymptotic representation of the form
\begin{equation*}
  x_n = \xi + c \, r^n + o(r^n)
\end{equation*}
as $n \to \infty$, where $\xi$ is the limit of the iteration, $\lvert
r \rvert < 1$ is the asymptotic contraction rate, and $c\neq 0$ some
constant.
\begin{enumerate}
\item Show that, for a certain value of $\alpha=\alpha(r)$, the
iteration
\begin{equation*}
  y_n = \alpha \, x_n + (1-\alpha) \, x_{n-1}
\end{equation*}
converges superlinearly.

\item Typically, the asymptotic contraction rate $r$ is not know
\emph{a priori}.  Suggest an approximation to $r$ based on the last
three available iterates $x_{n-2}$, $x_{n-1}$, and $x_n$.  Write out
the resulting iteration scheme.

\item \textbf{Project:} Test your scheme on the iteration
\begin{equation*}
  x_{n+1} = \cos(x_n) \,.
\end{equation*}
Use appropriate semi-logarithmic or doubly-logarithmic plots to
determine the rate of convergence with and without acceleration.

\end{enumerate}

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