\magnification=\magstep1
\centerline{Mathematics 171 -- Numerical Analysis 1}
\centerline{Discussion 4 -- Numerical Differentiation and Extrapolation}
\centerline{November 12, 1998}
\bigskip
\noindent
{\bf Background}
\bigskip
On Tuesday, we introduced some basic techniques for numerical approximation
of derivatives and derived the following error terms ($h > 0$):
$$f'(x_0) = 
\cases{{f(x_0+h)-f(x_0)\over h} - {f''(\xi_f)\over 2}h& (forward difference)\cr
       {f(x_0)-f(x_0-h)\over h} - {f''(\xi_b)\over 2}h& (backward difference)\cr
       {f(x_0+h)-f(x_0-h)\over 2h} - {f'''(\xi_c)\over 6}h^2& (centered difference)\cr}$$
where $\xi_f \in [x_0,x_0+h]$, $\xi_b \in [x_0-h,x_0]$, and
$\xi_c \in [x_0-h,x_0+h]$.
Because the error term for the centered difference approximation goes to
zero faster as $h \to 0$, to get a desired accuracy, we will not need
to take $h$ as small, and round-off problems will be correspondingly smaller!

Today, we want to think about two general ways to derive other numerical
derivative methods of this type and analyze their error terms.  To help 
us talk about the error terms, we will use the following terminology:

\bigskip
\noindent
{\bf Definition.}  Let $F$ be a function of $h$ and $k > 0$.
We say $F$ is $O(h^k)$
as $h\to 0$ (in words: ``F is big-Oh of $h$ to the $k$th power as $h$ goes 
to zero'') if there is a constant $M$ such that $|F(h)| \le M |h|^k$
for all sufficiently small $h$.
\bigskip
\noindent 
Bigger powers $k$ correspond to faster rates of convergence to zero, since
for example $\ell > m$ implies
$$\lim_{h\to 0} {h^\ell \over h^m} = \lim_{h\to 0} h^{\ell - m} = 0,$$
so $h^\ell$ goes to zero faster than $h^m$.  

The error for both the forward and backward difference approximations
above is $O(h)$.  The error for the centered difference is $O(h^2)$.
\bigskip
\noindent
{\bf Discussion Questions}
\bigskip
\item{A)}  As we saw on Monday in the derivation of the centered difference
formula, one way to try to derive this sort of approximation is to take
several equations from Taylor approximations at different points
and form a {\it linear combination to cancel terms ``behind'' the first derivative
terms\/}.  For example, find such a combination using the Taylor approximations:
$$\cases{f(x_0) & \cr
           f(x_0+h) = f(x_0) + f'(x_0) h + {f''(x_0)\over 2!}h^2 + 
                   {f'''(\xi_1)\over 3!} h^3&\cr
           f(x_0+2h) = f(x_0) + f'(x_0) (2h) + {f''(x_0)\over 2!} (2h)^2 + 
                   {f'''(\xi_2)\over 3!} (2h)^3&\cr}$$
and use it to derive a ``three-point'' forward difference formula.  What
is the error term?    Show that the error can be written as
${f'''(\xi)\over 3}h^2$ for some $\xi \in [x_0,x_0+2h]$, so it is 
$O(h^2)$ as $h \to 0$.  {\it Ceteris paribus}, which method is preferable:
this 3-point formula or the centered difference approximation?
\bigskip
\item{B)}  The same idea can also be used to derive formulas for
approximating second and higher derivatives.  For example, use
$$\cases{
           f(x_0-h) = f(x_0) - f'(x_0) h + {f''(x_0)\over 2!}h^2 + 
                   {f'''(\xi_1)\over 3!} h^3&\cr
           f(x_0) & \cr
           f(x_0+h) = f(x_0) + f'(x_0) h + {f''(x_0)\over 2!} h^2 - 
                   {f'''(\xi_2)\over 3!} h^3 & \cr}$$
to derive an approximation formula for $f''(x_0)$.  What is the error
term for this approximation?  (Be careful: what happens if you 
use additional terms in the Taylor approximations?)
 Would you want to use this one with
really small $h$'s?  Why or why not? 
\bigskip
\noindent
There is a general way to combine several approximations
derived from a particular method with a known error term that
yields an {\it improved error term}.  The name for the method in 
general is {\it Richardson extrapolation}.  The idea is reminiscent of
Aitken acceleration in some ways, but it is different.  Here is 
the basic idea, in general terms.  Suppose we have some way to 
produce approximations $N(h)$ to some quantity $M$ using different
values of $h$, and suppose, for 
instance, that the error is $O(h)$.  In particular, suppose
we can expand the error in a {\it power series} in $h$ as follows:
$$M = N(h) + c_1 h + c_2 h^2 + c_3 h^3 + \cdots$$
Then if we combine the two approximations:
$$M = \cases{N(h) + c_1 h + c_2 h^2 + \cdots & \cr
             N({h\over 2}) + c_1 {h\over 2} + c_2 
               \left({h\over 2}\right)^2 + \cdots & \cr}$$
by taking 
$$\eqalign{M &= 2M - M \cr
             &= 2\left(N\left({h\over 2}\right) + c_1 {h\over 2} + c_2 
               \left({h\over 2}\right)^2 + \cdots\right)- (N(h) + c_1 h + c_2 h^2 + \cdots)\cr
             &= \left(2N\left({h\over 2}\right) - N(h)\right) + c_2' h^2 + \cdots \cr}$$
then the $h$ terms {\it cancel\/}!
That is, using $M \doteq (2N\left({h\over 2}\right) - N(h))$, we
get an error term that is $O(h^2)$ rather than $O(h)$!
\bigskip
\item{C)}  Use this extrapolation idea to derive a better approximation
formula for second derivatives (one with error that is $O(h^4)$ as $h \to 0$).
\bigskip
\item{D)}  Suppose the error term for the ``$N$-method'' was $O(h^2)$
instead of $O(h)$.  How could you combine $N(h)$ and $N(h/2)$ to get
an error term that is $O(h^3)$ or better?  Apply this to the three-point
forward difference formula from question A.
\bigskip
\noindent
{\bf Assignment}
\bigskip
Group write-ups due in class Tuesday, November 17.  (I will have them 
graded by Wednesday so you can pick them up before the exam on 
Thursday.)


\bye