\magnification=\magstep1
\centerline{Mathematics 371 -- Numerical Analysis}
\centerline{Discussion 1 -- Rates of Convergence}
\centerline{\it September 5, 2001}
\bigskip
\noindent
{\it Background}
\bigskip
Many numerical algorithms are {\it iterative} -- that is, they involve
executing some sequence of computations repeatedly using the results of the 
previous stage to derive the result of the current stage in the 
process.  In the $n$th stage, we usually have a current approximation to 
the quantity we are trying to compute.
If we call that current approximation $x_n$ and the desired quantity
$x^\star$, then in principle (i.e. if we never stopped the process), 
we would generate a {\it sequence of approximations} $x_n$ converging 
to $x^\star$ as $n \to \infty$.  In this situation, there is a notion of 
{\it rate of convergence} that can be used
to describe {\it how fast $x_n$ approaches $x^\star$}:
\bigskip
\noindent
{\it We say $x_n = x^\star + O(n^{-p})$, or 
$x_n \to x^\star$ with rate of convergence $O(n^{-p})$,
if there is a positive constant $K$ and $n_0\ge 1$ such that 
$|x_n - x^\star| \le K\cdot {1\over n^p}$ for all $n \ge n_0$.}
\bigskip
\noindent
{\it Discussion Questions}
\bigskip
\item{A)}  
\itemitem{1)} The two sequences
$$ x_n = 1 + {1\over 10n} \qquad y_n = 1 + {(-1)^n\over n^2}$$
both
approach $x^\star = 1$ as $n\to \infty$.  Intuitively,
which approaches its limit {\it faster}?  Explain by analyzing
$|x_n - 1|$ and $|y_n - 1|$.
\itemitem{2)} What is the {\it largest} power $p$ such that 
$x_n = 1 + O(n^{-p})$?  Same question for $y_n$?  How does this relate
to your answer to part 1?
\bigskip
\item{B)} (One not-so-intuitive feature of our definition)  
Let $0 < q < p$ and assume that $x_n = x^\star + O(n^{-p})$.
Then show that $x_n = x^\star + O(n^{-q})$ as well.
\bigskip
\item{C)}  Suppose $x_n = f({1\over n})$ is produced by evaluating some 
differentiable function $f$.  How could you use properties of that function
to analyze the rate of convergence of $x_n$?
Use your idea to determine the rate of convergence of each of the following
sequences.
\medskip
\itemitem{1)}  $\lim_{n\to\infty} \sin\left({1\over n}\right) = 0$
\itemitem{2)}  $\lim_{n\to\infty} n\sin\left({1\over n}\right) = 1$ 
(first show that this sequence does tend to $1$ as $n \to \infty$)
\itemitem{3)}  $\lim_{n\to\infty} (\ln(n+1) - \ln(n)) = 0$ (first show that
this sequence does tend to $0$ as $n \to \infty$)
\itemitem{4)}  $\lim_{n\to\infty} n(1 - e^{1/n})$ (what is the limit?)
\bigskip
\item{D)}  In some very good cases, we will be able to produce 
numerical algorithms that converge to their results with a 
rate that is $O(n^{-p})$ for {\it all}  $p \ge 1$ (no matter how large).
This means we have a {\it very fast} rate of convergence.
\medskip
\itemitem{1)}  For instance show that $x_n = 10^{-2^n} \to 0$ has this 
property:   $10^{-2^n} = O(n^{-p})$ for all $p\ge 1$.
\itemitem{2)}  A sequence $x_n\to x^\star$ is said to 
{\it converge quadratically (respectively cubically)}
to its limit if there exists a positive constant $K$ such that
$$\lim_{n\to \infty} {|x_{n+1} - x^\star| \over |x_n - x^\star|^2} = K,$$
respectively
$$\lim_{n\to \infty} {|x_{n+1} - x^\star| \over |x_n - x^\star|^3} = K.$$
(In intuitive terms, quadratic convergence, for instance, means that for 
large $n$,
$$|x_{n+1} - x^\star| \doteq K|x_n - x^\star|^2.$$
Show that $x_n = 10^{-2^n} \to 0$ has quadratic convergence.
\itemitem{3)}  Construct a sequence that converges to 0 cubically.
\bigskip
\noindent
{\it Assignment}
\bigskip
Write-ups due Monday, September 10.
\bye