ChapterZero

How to easily find (forward) finite difference approximations to multiple derivatives with an arbitrary order of accuracy

Filed under: General — Alex @ 4:05 pm 3/28/2007

I decided to go ahead and attempt one of my problem sets early, and I found that in the process, I needed to come up with an order two FD approximation to $uu_x + u_{xxx}$ . Generally when I come across a question like this, it usually just asks for a 2nd order approximation to say the 1st derivative, and then I just mess around with various combinations of Taylor series expansions of the type u(x_0 + k h) , until I hit upon what I need.

Even for that relatively simple case, this procedure is a pain in the ass. I didn’t think I was up to it for the 3rd derivative, so I came up with a more systematic procedure, which can be used to get $u^{(r)}(x_0)$ with accuracy O(h^n) . It gives a forward finite differences scheme, but the idea should be adaptable to backward and central difference schemes also.

Here’s the idea: let w_i be a weight by which we will multiply u(x_0 + ih) . Then

$w_i u(x_0 + ih) = \sum_{k=0}^{r+n-1} w_i u^{(k)}(x_0) \frac{(ih)^k }{k!} + O(h^{n+r})$

$\sum_{i \in I} w_i u(x_0 + ih) = \sum_{k=0}^{r+n-1} \frac{h^k}{k!} u^{(k)}(x_0) \left( \sum_{i \in I} w_i i^k \right) + O(h^{n+r})$

Letting $p_k = \sum_{i \in I} w_i i^k$ , what we want is $p_0 = p_1 = \ldots = p_{r-1} = 0, \: p_r = 1, \: p_{r+1} = \ldots = p_{r+n-1} = 0$ , because if this holds true,

$\sum_{i \in I} w_i u(x_0 + ih) = \frac{h^r}{r!} u^{(r)}(x_0) + O(h^{n+r})$

which would imply

$\frac{r!}{h^r} \sum_{i \in I} w_i u(x_0 + ih) = u^{(r)}(x_0) + O(h^n)$

as desired.

So the question is how do we choose and $\{w_i\}$ such that we have the appropriate conditions on $\{p_k\}$ ? Well, note that if we write p = (p_k) and w = (w_i) as vectors, we have p = A w where $A_{ij} = j^{i-1}$ . Conveniently, when such an is square, it is full rank (prove it!), so we can invert to find the weights. Since varies between and r+n-1 , letting contain to r+n makes square.

Voila! (I’d like to say Q.E.D., but this was an algorithm, not a proof )

To recap, if you want to approximate $u^{(r)}(x_0)$ with accuracy O(h^n) using forward differences, use the r+n point approximation

$\frac{r!}{h^r} \sum_{i=1}^{r+n} w_i u(x_0 + ih) = u^{r}(x_0) + O(h^n)$

where the weight vector is chosen to satisfy

$A w = \begin{pmatrix} 0 \\ \vdots \\ 0 \\ 1 \\ 0 \\ \vdots \\ 0 \end{pmatrix}$

where $A_{ij} = j^{i-1}$ and the 1 is in the r+1 -th entry of the rhs vector.

Of course, you better check all my algebra if you intend to use this for anything important. I’m sure I messed up somewhere– I tried coding this up in Mathematica to test it and got weird results– but I’ve spent enough time on it for now.

How to easily find (forward) finite difference approximations to multiple derivatives with an arbitrary order of accuracy

Possibly relevant posts:

No Comments »

Leave a comment

Archives

intelligently designed

light and not filling