## Monday, February 25, 2013

### Improved Finite Difference Formula: Regular Grid

I am came across this excellent paper "Calculation of Weights in Finite Difference Formulas" by Bengt Fornberg, for deriving numerical differentiation formulae quickly.

Here, I will consider a very special case considered above.

Problem: Say you have a regular grid of equispaced points $x_0, x_1, ..., x_n$ of $n+1$ points, such that $x_j = x_0 + j h$. Let $f_j$ denote the function value at node $x_j$. Let us say, we want to find the best approximation to the m-th derivative at a point $x = x_0 + s h$, $f^{(m)(x)}$, where $x_0 \leq x \leq x_n$.

In the figure above, for example, n = 4 (5 points), m =2 (we are interested in an approximation to the second derivative) at x defined by s = 1.5.

We want to find the set of n+1 coefficients $c_i$s so that the explicit approximation is as good as possible
$f^{(m)}(x_0 + sh) = \sum_{i=0}^n c_i f_i$
Solution: The solution is a one-liner in Mathematica:

CoefficientList[Normal[Series[(x^s*Log[x]^m),{x,1,n}]/h^m],x]

Why does this work?

Set $f(x) = e^{i \omega x}$ in the approximate formula above. Note that $f^{(m)}(x_0 + sh) = (i \omega)^m e^{i \omega x_0} e^{i \omega s h}$, and $f_j = e^{i \omega x_0} e^{i \omega j h}$.
$(i \omega)^m e^{i \omega x_0} e^{i \omega s h} = \sum c_j e^{i \omega x_0} e^{i \omega j h}$
Using the substitution $e^{i \omega h} = \zeta$, which implies $\ln \zeta = i \omega h$, we get
$\left( \frac{\ln \zeta}{h} \right)^m \zeta^s = \sum c_j \zeta^j$
We want the approximation above to be as accurate as possible at small "h" or when $\zeta = 1$. Pulling the "h" term aside, and recognizing that the RHS looks like a truncated Taylor series, the coefficients $c_j$ can be obtained.

We can post facto throw in the factor of $h^m$ in the denominator to fix things up.