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