Franz J. Vesely > CompPhys Tutorial > Finite Differences  
 
 





 
< >
Ch. 1 Sec. 1



1.2 Interpolation Formulae

 Threading a polynomial through several given points $x_{k}, f_{k}$ we arrive at a smooth function which we may then differentiate. In this manner we construct approximations to the derivatives of the tabulated function.

Given some arbitrary point on the $x$-axis, we define

$ u \equiv \frac{\textstyle x-x_{k}}{\textstyle \Delta x} $

as the normalized distance between $x$ and $x_{k}$.

Using the forward, backward, and central differences as defined above we arrive at different interpolation schemes.

1.2.1 Newton-Gregory Forward Interpolation



Let us first construct a polynomial of order $m$ by using only points to the right of $x_{k}$ (and $x_{k}$ itself). Written in terms of forward differences, we have

NGF interpolation:


$ \begin{eqnarray} F_{m}(x) & = & f_{k} + {u \choose 1} \Delta f_{k} + {u \choose 2} \Delta^{2} f_{k} + \dots \\ & = & f_{k} + \sum_{l=1}^{m} {u \choose l} \Delta^{l} f_{k} + O[(\Delta x)^{m+1}] \end{eqnarray} $

where

$ { \textstyle u \choose \textstyle l} \equiv \frac{\textstyle u (u-1) \dots (u-l+1)}{\textstyle l!} $

By $O[(\Delta x)^{m+1}]$ we denote the neglected remainder, stressing its gross dependence on the step size $\Delta x$. Close analysis would reveal that the remainder term is actually

$ R = O \left[ f^{(m+1)}(x') \frac{\textstyle (x-x')^{m+1}}{\textstyle (m+1)!} \right] $

where $x=x'$ is the position of the maximum of $\vert f^{(m+1)}(x)\vert$ in the interval $[x_{k}, x_{k+m}]$. Putting $ x - x' \equiv \xi \Delta x $ we have

$ R = O \left[ f^{(m+1)}(x') \frac{\textstyle \xi^{m+1}}{\textstyle (m+1)!} (\Delta x)^{m+1} \right] $



EXAMPLE: Taking $m=2$ in the general NGF formula we obtain the parabolic approximation

$ F_{2}(x) = f_{k}+ \frac{\textstyle \Delta f_{k}}{\textstyle \Delta x} (x-x_{k}) + \frac{\textstyle 1}{\textstyle 2} \frac{\textstyle \Delta^{2} f_{k}}{\textstyle (\Delta x)^{2}} (x-x_{k}) (x-x_{k+1}) + O[(\Delta x)^{3}] $




1.2.2 Newton-Gregory Backward Interpolation



Using only table values at $x_{k}, x_{k-1}, \dots$ we find

NGB interpolation:


$ \begin{eqnarray} F_{m}(x) & = & f_{k}+ \frac{\textstyle u}{\textstyle 1!} \nabla f_{k}+ \frac{\textstyle u(u+1)}{\textstyle 2!} {\nabla}^{2} f_{k}+ \dots \\ & = & f_{k}+ \sum_{l=1}^{m} {u+l-1 \choose l} \nabla^{l} f_{k}+ O[(\Delta x)^{m+1}] \end{eqnarray} $



EXAMPLE: With $m=2$ we arrive at the parabolic NGB approximation

$ F_{2}(x) = f_{k}+ \frac{\textstyle \nabla f_{k}}{\textstyle \Delta x} (x-x_{k}) + \frac{\textstyle 1}{\textstyle 2} \frac{\textstyle \nabla^{2} f_{k}}{\textstyle (\Delta x)^{2}} (x-x_{k}) (x-x_{k-1})+ O[(\Delta x)^{3}] $



1.2.3 Stirling Interpolation



Let us try to interpolate around $x_{k}$ employing the central differences $\delta f_{k}$, $\; \delta^{2} f_{k}$ etc.

Difficulty: Central differences of odd order cannot be evaluated using a given table of function values. $\Longrightarrow$ Replace each term of the form $\delta^{2l+1} f_{k}$ by its central mean. We find the even order polynomials

ST interpolation:


$ \begin{eqnarray} F_{2n}(x) & = & f_{k}+ u \mu \delta f_{k}+ \frac{\textstyle u^{2}}{\textstyle 2!} \delta^{2} f_{k} + \frac{\textstyle u^{3}-u}{\textstyle 3!} \mu \delta^{3} f_{k} + \frac{\textstyle u^{4}-u^{2}}{\textstyle 4!} \delta^{4} f_{k}+ \dots \\ & = & f_{k}+ \sum_{l=1}^{n} {u+l-1 \choose 2l-1} \left[\mu \delta^{2l-1} f_{k}+ \frac{\textstyle u}{\textstyle 2l} \delta^{2l} f_{k}\right] \\ & & \;\;\; \mbox{} + O[(\Delta x)^{2n+1}] \end{eqnarray} $



EXAMPLE: With $n=1$ (or $m=2$) we have

$ F_{2}(x) = f_{k}+ \frac{\textstyle \mu \delta f_{k}}{\textstyle \Delta x} (x-x_{k}) + \frac{\textstyle 1}{\textstyle 2} \frac{\textstyle \delta^{2} f_{k}}{\textstyle (\Delta x)^{2}} (x-x_{k})^{2} + O[(\Delta x)^{3}] $


In a region symmetric about $x_{k}$ the Stirling polynomial gives, for equal orders of error, the "best" approximation to the tabulated function.

vesely 2005-10-10

< >