\documentclass[twoside]{article}

\usepackage{palatino}
\usepackage{camnum}

\def \X {\BB{X}}
\def \PP {\BB{P}}
\def \C {\CC{C}}
\def \l {\ell}

\textheight=25cm
\textwidth=15cm
\topmargin=-2cm
\oddsidemargin=0.5cm
\evensidemargin=0.5cm
\parindent=0pt
\parskip=6pt

\setcounter{section}{8}
\setcounter{subsection}{2}
\setcounter{equation}{1}

\begin{document}
\begin{center}
  {\large \textbf{Mathematical Tripos Part IB: Easter 2001}}

  {\Large \textbf{Numerical Analysis -- Lecture
      12\footnote{Corrections and suggestions to these notes should
        be emailed to \texttt{a.shadrin@damtp.cam.ac.uk}. All handouts
        are available on the WWW at the URL 
        \texttt{http://www.damtp.cam.ac.uk/user/na/PartIB/Handouts.html}.}}}
\end{center}

\subsection{Numerical differentiation}

Consider the interpolating formulae for numerical differentiation
$$
\textstyle
   \l(f)= f^{(k)}(x) \approx \sum_{i=0}^{n} a_i f(x_i), \qquad
   a_i = \l(L_i) = L_i^{(k)}(x),
$$
which are exact on the polynomials of degree $n$. The simplest
ones are with $n=k$, i.e., $f^{(k)}(x) \approx p^{(k)}(x)$ where
$p$ is the interpolating polynomial of degree $k$.
But $p^{(k)}(x)$ is $k!$ times the leading coefficient of $p$, i.e.,  
$k!f[x_0,\ldots,x_{k}]$, and we obtain the simplest rules
$f^{(k)}(x) \approx k!f[x_0,\ldots,x_k]$.\\[1ex]
%
{\small
{\bf Examples.}

\centerline{
\begin{tabular}{rcl}
 the forward difference:
   & \fbox{$f'(x) \approx  f[x,x+h] = 
        \frac{f(x+h)-f(x)}{h}$}
   & \small \begin{tabular}{l} 2-point, \\ 
                               exact on linear f-ns
            \end{tabular} \\[2ex]
 the central difference:
   & \fbox{$f'(x) \approx  f[x-h,x+h] =  
          \frac{f(x+h)-f(x-h)}{2h}$}
   & \small \begin{tabular}{l} 2-point, \\
                         of higher accuracy,\\
                         exact on quadratics 
            \end{tabular} \\[3ex]
the 2-nd central difference:
   & \fbox{$f''(x) \approx  2f[x-h,x,x+h] = 
              \frac{f(x-h)-2f(x)+f(x-h)}{h^2}$}
   & \small \begin{tabular}{l} 3-point,\\
                               of higher accuracy,\\
                               exact on cubics 
            \end{tabular}
\end{tabular}
}
%
{\bf Example.} $2 = n > k = 1$, $[a,b]=[-1,1]$.
(Of course, one can transform any formula to any interval.)
%
\begin{equation}
    f'(0) \approx -\Frac{3}{2}f(0) + 2f(1) - \Frac{1}{2}f(2)
\end{equation}
%
{\bf Example.} 
A general formula has the form
$\ell(f) \approx \sum_{i=0}^n a_i \ell_i(f)$, where $\ell_i$
can be any fixed functionals, e.g.,
$$
  f(x+2h) 
  \approx  f(x+h) + h[\Frac{3}{2}f'(x+h)-\Frac{1}{2}f'(x)]
$$
}
\vspace*{-7ex}
\section{Error of approximation}
\setcounter{equation}{0}

Given an approximation 
$\l(f) \approx \sum_{i=0}^n a_i f(x_i)$, we are interested of course
in its error
$$
\textstyle
   e(f) := \l(f) - \sum_{i=0}^n a_i f(x_i).
$$
If $\l$ acts on $\C^{n+1}$, then it is natural to seek an estimate 
in terms of $f^{(n+1)}$. For the interpolating formulae we obtain
$$
\textstyle
   e(f) := \l(f) - \l(p) = \l(f-p), \qquad e(f)=0 \quad \forall f\in\PP_n.
$$
%{\small
%We may use the estimate
%$$
%   f(x) - p(x) = \frac{1}{(n+1)!} \omega(x) f^{(n+1)}(\xi),
%$$
%however, we cannot act with $\l$ on the right-hand side immediately,
%because $\xi$ also depends on $x$. One can get rid of this dependance
%rewriting the formula as
%$$
%\textstyle
%    |f(x) - p(x)| 
%\le \frac{1}{(n+1)!} |\omega(x)|\cdot \|f^{(n+1)}\|_\infty, \qquad
%\|f^{(n+1)}\|_\infty := \max\limits_{\xi\in[a,b]} |f(\xi)|.
%$$
%This estimate can be used in bounding the error of numerical quadrature:
%$$
%\begin{array}{rcl}
%     e(f) 
%&:=& I(f-p) = \int_a^b [f(x)-p(x)] \D x
% \le \int_a^b |f(x)-p(x)| \D x \\[2ex]
%&\le& \left\{\frac{1}{(n+1)!}
%     \int_a^b |\omega(x)|\D x\right\} \cdot \|f^{(n+1)}\|_\infty
%\end{array}
%$$
%but it looses in accuracy.
%}


\subsection{The Peano kernel theorem}

Our point of departure is the {\em Taylor formula with an integral
remainder term},
%
\begin{equation}\label{9.1}
\textstyle
   f(x)
 = \sum_{j=0}^n \frac{(x-a)^j}{j!} f^{(j)}(a)
   + \frac{1}{n!} \int_a^x (x-\theta)^k f^{(n+1)}(\theta)\D\theta,
\end{equation}
where the sum
is the {\em Taylor polynomial} to $f$ (at the point $a$).
One can can verify \R{9.1} by integration by parts.
It is standard to write the remainder in the slightly different form,
$$
\textstyle
   r(x) 
 = \frac{1}{n!} \int_a^b (x-\theta)_+^k f^{(n+1)}(\theta)\D\theta, 
   \quad \mbox{where}\; (x-\theta)_+^k = [\max(x-\theta,0)]^k,
$$
which makes the range of integration independent of $x$. 
Let $L$ be a linear functional on $\C^{n+1}$ which vanishes on $\PP_n$.
Then 
$
  L(f) = L(r) = \frac{1}{n!} L\left(
  \int_a^b (x-\theta)_+^k f^{(n+1)}(\theta)\D\theta 
  \right).
$
Set $g_\theta(x) := (x-\theta)_+^k$, and 
$K(\theta) := L[g_\theta] := L[(x-\theta)_+^k]$.
The function $K$ is called the {\em Peano kernel} of $L$. 
%(Note: $K$ is {\em independent} of $f$.) 


{\bf The Peano kernel theorem.} {\em 
With $L$ and $K$ as above,
%
\begin{equation}
\textstyle
  L(f) = \frac{1}{n!} \int_a^b K(\theta)f^{(n+1)}(\theta)\D\theta 
\end{equation}
%
provided that the exchange of $L$ with the integration sign is valid. \QED
}

{\bf Remark.} Typically, forming $L$ involves
differentiation, integration and linear combination of function
values. In these cases the exchange is justified.


{\small
{\bf Example 1} ({\em Formula $(8.2)$}).
The error  can be expressed as
$$
\textstyle
   e(f) = f'(0)- [-\frac{3}{2}f(0)+2f(1)-\frac{1}{2}f(2)]
        = \frac{1}{2!} \int_0^2 K(\theta)f'''(\theta)\D\theta 
$$
where with $g_\theta(x):=(x-\theta)_+^2$
%
\begin{equation}
    K(\theta) = e(g_\theta) 
  = 2(0-\theta)_+ 
    -\big[-\Frac32 (0-\theta)_+^2
    +2(1-\theta)_+^2
    -\Frac12(2-\theta)_+^2\big] %\\[1ex]
  = \left\{\begin{array}{ll}
    2\theta-\frac32\theta^2, & \theta\in[0,1],\\ 
        \frac12(2-\theta)^2, & \theta\in[1,2].
    \end{array}\right.
\end{equation}
%
{\bf Example 2} ({\em The midpoint rule}).
The error can be expressed as
$$
\textstyle
   e(f) = \int_{-1}^1 f(x)\D x - 2f(0) 
        = \int_{-1}^1 K(\theta)f''(\theta)\D\theta 
$$
where  with $g_\theta(x):=(x-\theta)_+^1$
%
\begin{equation}
\textstyle
    K(\theta) = e(g_\theta) 
  = \int_{-1}^1 (x-\theta)_+^1 \D x - 2(0-\theta)_+^1
  = \left\{\begin{array}{ll}
        \frac12(1+\theta)^2, &  \theta\in[-1,0],\\[1ex]
        \frac12(1-\theta)^2, &  \theta\in[0,1].
    \end{array}\right.
\end{equation}
}
{\bf Theorem.} {\em 
Suppose that $K$ doesn't change sign in $(a,b)$ and that
$f\in \CC{C}^{n+1}[a,b]$. Then
\begin{equation}
\textstyle
   L(f) = \left(\frac{1}{n!} \int_a^b K(\theta)\D\theta\right)
          f^{(n+1)}(\xi)\quad \mbox{for some}\quad \xi\in(a,b).
\end{equation}
}
%
\hspace*{8pt}{\bf Proof.} Let  $K\geq0$. Then, letting
$c(K) :=\frac{1}{n!} \int_a^b K(\theta)\D\theta$, we obtain
$$
\textstyle
   c(K) \min\limits_{x\in[a,b]} f^{(n+1)}(x)
\le
   \underbrace{\textstyle
   \frac{1}{n!} \int_a^b K(\theta)f^{(n+1)}(\theta)\D\theta}_{L(f)}
\le
   c(K) \max\limits_{x\in[a,b]} f^{(n+1)}(x),
$$
so that, by the intermediate value theorem, there is a $\xi\in[a,b]$
s.t.\ $c(K) f^{(n+1)}(\xi) = L(f)$. \QED

{\small
{\bf Examples 1-2} ({\em again}). In both cases $K \ge 0$, so that
calculating the integrals in $(9.3)$-$(9.4)$ we obtain 
$$
\mbox{
  1)\quad $e(f) 
= \frac{1}{2!} \cdot \frac23 \cdot f'''(\xi) = \frac13 f'''(\xi)$ $\;$ 
  for the formula $(8.2)$
\qquad
  2)\quad  $e(f) = \frac{1}{3} \cdot f''(\xi)$ $\;$ 
  for the midpoint rule.
}
$$
}

{\bf Corollary.} {\em
Let $\l(f) = f^{(k)}(x)$
and let a formula $f^{(k)}(x) \approx \sum_{i=0}^n a_i f(x_i)$
be exact on $\PP_n$. 
If the Peano kernel $K$ for the error functional $e(\cdot)$ 
does not change its sign, then, for some $\xi\in(a,b)$,
%
\begin{equation}
\textstyle
    e(f) = \frac{1}{(n+1)!} \omega^{(k)}(x)  f^{(n+1)}(\xi),  
%    \quad \mbox{for some}\quad \xi\in(a,b)
    \qquad \omega(x) = \prod_{i=0}^n(x-x_i)
\end{equation}
}
\hspace*{8pt}{\bf Proof.} We need to prove that 
$
   \int_a^b K(\theta)\D\theta 
 = \frac{1}{n+1}\omega^{(k)}(x)
$. 
Substitute $f(x) = \omega(x)$ into $(9.2)$.
Since $f(x_i)=0$, the left-hand side becomes
$e(f) = f^{(k)}(x) = \omega^{(k)}(x)$.
And because $f^{(n+1)}(x)\equiv (n+1)!$, the right-hand side will be
$
   \frac{1}{n!} \int_a^b K(\theta)f^{(n+1)}(\theta)\D\theta
 = (n+1)\int_a^b K(\theta)\D\theta
$. 
\QED

{\small
{\bf Example 1} ({\em again and again}). 
Since $K\ge 0$, and $\omega(x)=x(x-1)(x-2)$, it follows that 
$
  e(f) = \frac{1}{3!}\omega'(0)f'''(\xi) 
       = \frac{1}{3}f'''(\xi),
$
in accordance with previous calculations.
}

For any formula $f^{(k)}(x) \approx p^{(k)}(x) = \sum_{i=0}^n a_i f(x_i)$,
there is a complete description (in terms of $(x_i)$) 
of those points $x\in[a,b]$ for which the Peano kernel of the error
functional does not change its sign. In particular, these are the
end-points of $[a,b]$ (again in accordance with the Example). 

{\bf Function norms:} The value $f^{(n+1)}(\xi)$, say in 
$(9.5)$-$(9.6)$, with {\em some} $\xi\in[a,b]$ is useless. 
One uses instead the bounds for 
the so-called $L_p$-{\em norms} $\|g\|_p$ which for $p=1,2,\infty$ are
$$
\textstyle 
   \|g\|_1 =\int_a^b |f(x)|\D x, \qquad  
   \|g\|_2 =\{\int_a^b [g(x)]^2\D x\}^{1/2}, \qquad 
   \|g\|_\infty=\max_{x\in[a,b]} |g(x)|.
$$
The equality $e(f) = \frac13 f'''(\xi)$ is being rewritten then as
$|e(f)|\leq\frac13 \|f'''\|_\infty$.


Likewise we can easily deduce from 
$
     \big|\int_a^b f(x)g(x)\D x\big|
 \le \|g\|_\infty \|f\|_1
$ that
$$
\textstyle
     |L(f)|
\leq \frac{1}{n!}\|K\|_1 \|f^{(n+1)}\|_\infty
     \mbox{\qquad and \qquad} 
     |L(f)|
\leq \frac{1}{n!} \|K\|_\infty \|f^{(n+1)}\|_1,
$$
what is valid also when $K$ changes sign.\qquad
\begin{picture}(0,0)(10,10)
\thicklines
\put (10,10) {\circle{20}}
\put (10,6) {\oval(5,5)[b]}
\put (10,8) {\line(0,1){6}}
\put (7,13) {\circle*{2}}
\put (13,13) {\circle*{2}}
\end{picture}

\end{document}







--------------------------------------------


Given an interpolating formula 
$\l(f) \approx \l(p)$sum_{i=0}^n a_i f(x_i)$, we are interested of course
in the error of approximation
$$
   e(f) = \l(f) - \sum_{i=0}^n a_i f(x_i)
$$
For $\l$ acting on $f \in C^{n+1}[a,b]$ it is natural to seek
an estimate in terms of the $(n+1)$-st derivative of $f$.
Since $f^{(n+1)} \equiv 0$ on $\PP_n$, for such an estimate to exist
we must have $e(f) = 0$ on $\PP_n$, i.e., the formula must be 
exact on $\PP_n$, hence interpolating of degree $n$. Thus,
we consider again the interpolating formulae $\l(f) \approx \l(p)$, 
so that  
$$
   e(f) = \l(f) - \l(p) = \l(f-p).
$$

