1.3a Difference Quotients
- Differentiate the NGF, NGB, or ST polynomials, arriving at
$F'(x)$ and $F''(x)$ etc.
- Insert $x=x_{k}$ to obtain approximations to the derivatives at
$x_{k}$.
For the first step we need to know how to differentiate the
generalized binomial coefficients with respect to $u$:
$
\frac{\textstyle d}{\textstyle du} {\textstyle u \choose l}
= {\textstyle u \choose l} \sum \limits_{i=0}^{l-1} \frac{\textstyle 1}{\textstyle u-i}
$
and
$
\frac{\textstyle d^{2}}{\textstyle du^{2}} {\textstyle u \choose l}
= \left\{
\begin{array}{ll}
0 & {\rm for \;\; l=1} \\
{\textstyle u \choose l} \sum \limits_{i=0}^{l-1} \sum \limits_{j=0 \atop j \neq i}^{l-1}
\frac{\textstyle 1}{\textstyle (u-i)(u-j)}
& {\rm for \;\; l \geq 2}
\end{array}
\right .
$
Differentiating the NGF polynomial we find for the first two derivatives
in a small region - preferably towards the right - around $x_{k}$:
$
\begin{eqnarray}
{F_{m}}'(x) & = & \frac{\textstyle 1}{\textstyle \Delta x}
\sum \limits_{l=1}^{m} \Delta^{l} f_{k} {\textstyle u \choose l}
\sum \limits_{i=0}^{l-1} \frac{\textstyle 1}{\textstyle u-i} + O[(\Delta x)^{m}]
\\
\\
{F_{m}}''(x) & = & \frac{\textstyle 1}{\textstyle (\Delta x)^{2}}
\sum_{l=2}^{m} \Delta^{l} f_{k} {\textstyle u \choose l}
\sum \limits_{i=0}^{l-1} \sum \limits_{j=0 \atop j \neq i}^{l-1}
\frac{\textstyle 1}{\textstyle (u-i)(u-j)}
+ O[(\Delta x)^{m-1}]
\end{eqnarray}
$
We will be content to know $F'(x)$ and $F''(x)$ at the supporting
points of the grid, in particular at the point $x=x_{k}$,
i.e. for $u=0$:
DNGF:
$
\begin{eqnarray}
{F_{m}}'(x_{k}) & = & \frac{\textstyle 1}{\textstyle \Delta x} \left[
\Delta f_{k}
- \frac{\textstyle \Delta^{2} f_{k}}{\textstyle 2}
+ \frac{\textstyle \Delta^{3} f_{k}}{\textstyle 3}
- \frac{\textstyle \Delta^{4} f_{k}}{\textstyle 4}
+ \dots \right] \\
& = & \frac{\textstyle 1}{\textstyle \Delta x}
\sum \limits_{l=1}^{m} (-1)^{l-1}
\frac{\textstyle \Delta^{l} f_{k}}{\textstyle l}
+ O[(\Delta x)^{m}]
\end{eqnarray}
$
DNGF:
$
\begin{eqnarray}
{F_{m}}''(x_{k}) & = & \frac{\textstyle 1}{\textstyle (\Delta x)^{2}} \left[
\Delta^{2} f_{k}
- \Delta^{3} f_{k} + \frac{\textstyle 11}{\textstyle 12}
\Delta^{4} f_{k} - \dots \right]
\\
& = & \frac{\textstyle 2}{\textstyle (\Delta x)^{2}}
\sum \limits_{l=2}^{m} (-1)^{l}
\frac{\textstyle \Delta^{l} f_{k}}{\textstyle l}
\sum \limits_{i=1}^{l-1} \frac{\textstyle 1}{\textstyle i}
+ O[(\Delta x)^{m-1}]
\end{eqnarray}
$
1.3.1 First Derivatives
Replacing $dx$ by $\Delta x$ and $df$ by
$\Delta f_{k}$, $\nabla f_{k}$, or $\delta f_{k}$
we arrive at various approximations to the
first derivative of $f$ at $x_{k}$:
-
DNGF (Differentiated Newton-Gregory Forward):
$
{F_{k}}' \approx \frac{\textstyle 1}{\textstyle \Delta x}
\left[ \Delta f_{k} - \frac{\textstyle \Delta^{2} f_{k}}{\textstyle2}
+ \frac{\textstyle \Delta^{3} f_{k}}{\textstyle 3}
- \dots \right]
$
Example:
$
\begin{eqnarray}
{F_{k}}' & = & \frac{\textstyle 1}{\textstyle \Delta x}
\left[ \Delta f_{k}-\frac{\textstyle \Delta^{2}f_{k}}{\textstyle 2} \right]
+O[(\Delta x)^{2}] \\
&& \\
& = & \frac{\textstyle 1}{\textstyle \Delta x}
\left[ -\frac{1}{2}f_{k+2}+2f_{k+1}-\frac{3}{2}f_{k}
\right]+ O[(\Delta x)^{2}]
\end{eqnarray}
$
-
DNGB (Differentiated Newton-Gregory Backward):
$
\begin{eqnarray}
{F_{k}}' & \approx & \frac{\textstyle 1}{\textstyle \Delta x}
\left[ \nabla f_{k}
+ \frac{\textstyle \nabla^{2} f_{k}}{\textstyle 2}
+ \frac{\textstyle \nabla^{3} f_{k}}{\textstyle 3}
+ \dots \right]
\end{eqnarray}
$
Example:
$ \begin{eqnarray}
{F_{k}}' & = & \frac{\textstyle 1}{\textstyle \Delta x}
\left[ \nabla f_{k}+\frac{\textstyle \nabla^{2}f_{k}}{\textstyle 2} \right]
+ O[(\Delta x)^{2}] \\
&& \\
& = & \frac{\textstyle 1}{\textstyle \Delta x}
\left[ \frac{3}{2}f_{k}-2f_{k-1}+\frac{1}{2}f_{k-2}
\right]+ O[(\Delta x)^{2}]
\end{eqnarray}
$
-
DST (Differentiated Stirling):
$
\begin{eqnarray}
{F_{k}}' & \approx &
\frac{\textstyle 1}{\textstyle \Delta x}
\left[ \mu \delta f_{k}- \frac{1}{6} \mu \delta^{3} f_{k}
+ \frac{1}{30} \mu \delta^{5} f_{k}
+ \dots \right]
\end{eqnarray}
$
Example:
$
\begin{eqnarray}
{F_{k}}' & = &
\frac{\textstyle 1}{\textstyle \Delta x}
\left[\mu \delta f_{k} \right]+ O[(\Delta x)^{2}]
\\
&& \\
& = & \frac{\textstyle 1}{\textstyle 2 \Delta x}
\left[f_{k+1}-f_{k-1} \right]+ O[(\Delta x)^{2}]
\end{eqnarray}
$
Figure: Comparison of various simple approximations to the
first differential quotient:
$
\begin{eqnarray}
DNGF: \;\; F_{k}' & = & \frac{\textstyle \Delta f_{k}}{\textstyle \Delta x}
+ O[\Delta x]
= \frac{\textstyle 1}{\textstyle \Delta x}
\left[ f_{k+1}-f_{k} \right] + O[\Delta x]
\\ && \\
DNGB: \;\; F_{k}' & = & \frac{\textstyle \nabla f_{k}}{\textstyle \Delta x}
+ O[\Delta x]
= \frac{\textstyle 1}{\textstyle \Delta x}
\left[ f_{k}-f_{k-1} \right] + O[\Delta x]
\\ && \\
DST: \;\;\; F_{k}' & = & \frac{\textstyle \mu \delta f_{k}}{\textstyle \Delta x}
+ O[(\Delta x)^{2}]
= \frac{\textstyle 1}{\textstyle 2\Delta x}
\left[ f_{k+1}-f_{k-1} \right] + O[(\Delta x)^{2}]
\end{eqnarray}
$
1.3.2 Second Derivatives
The same procedure as before yields
-
DDNGF:
$
\begin{eqnarray}
{F_{k}}'' & \approx & \frac{\textstyle 1}{\textstyle (\Delta x)^{2}}
\left[ \Delta^{2} f_{k} - \Delta^{3} f_{k}
+ \frac{11}{12} \Delta^{4} f_{k}- \dots \right]
\end{eqnarray}
$
Example:
$
\begin{eqnarray}
{F_{k}}'' & = & \frac{\textstyle 1}{\textstyle (\Delta x)^{2}} \Delta^{2} f_{k}
+ O(\Delta x)
\\ && \\
& = & \frac{\textstyle 1}{(\textstyle \Delta x)^{2}}
\left[ f_{k+2}-2f_{k+1}+f_{k}\right]+ O(\Delta x)
\\ && \\
&&\;\;{\rm \;\;\;\;\;\;(pretty \;\; bad!)}
\end{eqnarray}
$
Let's try again....
-
DDNGB:
$
\begin{eqnarray}
{F_{k}}'' & \approx & \frac{\textstyle 1}{\textstyle (\Delta x)^{2}}
\left[ \nabla^{2} f_{k} + \nabla^{3} f_{k}+ \frac{11}{12} \nabla^{4} f_{k}
+ \dots \right]
\end{eqnarray}
$
Example:
$
\begin{eqnarray}
{F_{k}}'' & = & \frac{\textstyle 1}{\textstyle (\Delta x)^{2}} \nabla^{2} f_{k}
+ O(\Delta x)
\\ && \\
& = & \frac{\textstyle 1}{\textstyle (\Delta x)^{2}}
\left[ f_{k}-2f_{k-1}+f_{k-2}\right] + O(\Delta x)
\\ && \\
&&\;\;{\rm \;\;\;(pretty \;\; bad,\;\; too!)}
\end{eqnarray}
$
And the winner is...
-
DDST:
$
\begin{eqnarray}
{F_{k}}'' & \approx & \frac{\textstyle 1}{\textstyle (\Delta x)^{2}}
\left[ \delta^{2} f_{k}- \frac{1}{12} \delta^{4} f_{k}
+ \frac{1}{90} \delta^{6} f_{k}- \dots \right]
\end{eqnarray}
$
Example:
$
\begin{eqnarray}
{F_{k}}'' & = & \frac{\textstyle 1}{\textstyle (\Delta x)^{2}} \delta^{2} f_{k}
+ O\left[(\Delta x)^{2}\right]
\\ && \\
& = & \frac{\textstyle 1}{\textstyle (\Delta x)^{2}}
\left[ f_{k+1}-2f_{k}+f_{k-1}\right]+ O\left[(\Delta x)^{2}\right]
\\ && \\
&&\;\;{\rm \;\;\;\;\;\;(much \;\; better!)}
\end{eqnarray}
$
Figure: Interpolation, including first and second derivatives as
approximated by backward (blue), forward (green) and
Stirling (red) differencing. In the neighborhood of
$x_{k}$ (black dot) the tabulated function is best represented by Stirling.
The interpolation curves are actually parabolas, but as only their
values at $x_{k \pm l}$ are of interest they are drawn as broken lines.
vesely
2005-10-10