Franz J. Vesely > CompPhys Tutorial > Finite Differences  
 
 





 
< >
Ch. 1 Sec. 2



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

< >