\magnification=\magstep1
\centerline{Mathematics 371 -- Numerical Analysis}
\centerline{Discussion 3 -- Numerical Differentiation and Extrapolation}
\centerline{October 24-26, 2001}
\bigskip
\noindent
{\it  Background}
\bigskip
On Monday, we introduced some basic techniques for numerical approximation
of derivatives and derived the following error terms:
$$f'(x_0) = 
\cases{{f(x_0+h)-f(x_0)\over h} - {f''(\xi_f)\over 2}h& (2 point forward difference)\cr
\cr
       {-3f(x_0+2h) + 4f(x_0+h) - f(x_0) \over 2h} + {f'''(\xi_f)\over 3} h^2&(3 point forward difference)\cr
       \cr
       {f(x_0+h)-f(x_0-h)\over 2h} - {f'''(\xi_c)\over 6}h^2& (3 point centered difference)\cr}$$
where $\xi_f \in [x_0,x_0+h]$ for the 2-point formula, 
$\xi_f \in [x_0,x_0+2h]$ for the 3-point forward difference formula,
and $\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 a way to get more accurate approximations, 
without causing roundoff error problems by trying to use very small $h$
values.  
The error for both the 2 point forward difference approximation
above is $O(h)$.  The errors for 3 point forward difference and
centered difference approximations are $O(h^2)$.

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)$.  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
\noindent
{\it Discussion Questions}
\bigskip
\item{A)}  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 to derive an approximation to $f'(x_0)$ with
error $O(h^3)$ or better.  
\item{B)}  Apply your method from part A to
the 3-point {\it centered difference formula} to produce an approximation
method for $f'(x_0)$ with error $O(h^3)$ or better.  It can be
shown, using Taylor series, that the error term for
the centered difference approximation actually has the form
$c_2h^2 + c_4h^4 + \cdots $ (only even powers of $h$).  What
does that say about the actual order of the error?
\item{C)}  Generalizing part A, suppose the error term for the 
``$N$-method'' was $O(h^k)$
instead of $O(h)$.  How could you combine $N(h)$ and $N(h/2)$ to get
an error term that is $O(h^{k+1})$ or better?  
\item{D)}  Use a degree 2 interpolating polynomial for $f$ to 
derive a forward difference approximation to $f''(x_0)$.  What
is the error of your approximation?  For which $k$ is the error
$O(h^k)$?
\item{E)}  Use your answer from C and Richardson extrapolation
to derive an approximation method for $f''(x_0)$ with error 
$O(h^2)$ or better.
\item{F)}  There's nothing magic about $h$ and $h/2$ in 
Richardson Extrapolation.  Do Exercise 9 from Section 4.2 in
the text to see how the same sort of improvement of the 
order of the error could be done with $h$, $h/3$, $h/9$, etc.
\bigskip
\noindent
{\it Assignment}
\bigskip
Write-ups due in class Wednesday, October 31.
\bye