1

The chapter I'm looking at is 'numerical differentiation'. There's a formula that just got thrown in there out of nowhere and I've got no idea where it comes from. Anyway, let's get the notation out of the way.

$f[x_i, ..., x_{i+k}]$ - denotes the divided difference of $k$-th order starting at $i$-th node.

$\omega_{n+1}(x)$ - denotes $\prod_{j=0}^{n}(x-x_j)$

Anyway, we want to see what the error of differentiation is when taking the derivative of an interpolation polynomial (in our case Newton's forward interpolation polynomial, but it's written in general form). So we take a look at:

$$f^{(k)}(x) - L_n^{(k)}(x) = (f(x) - L_n(x))^{(k)} = (f[x, x_0, ..., x_n]\omega_{n+1}(x))^{(k)} = \sum_{j=0}^{k}{k \choose j}(f[x, x_0, ..., x_n])^{(j)}\omega^{(k-j)}_{n+1}(x)$$

Seems alright so far. We take the difference of the actual derivative and the polynomial derivative, use the fact that the derivative is linear. Inside we get $f(x) - L_n(x)$ which is an error of the polynomial interpolation itself which corresponds to the formula $f[x, x_0, ...x_n]\omega_{n+1}(x)$. Take the $k$-th derivative of that, break it down into that sum. Now check this out: $$(f[x, x_0, ...x_n])^{(j)} = j!f[x,..., x, x_0, ...x_n], \text{ where the } x \text{ in } x, ..., x \text{ repeats } j+1 \text{ times}$$

Then it uses that for further derivation, but I'm stuck right here. Where does this come from? Any ideas? Thanks.

Koy
  • 877
  • 1
  • 6
  • 13
  • Did you try playing around with identities involving sums of divided differences? – Zim Jun 16 '20 at 15:57
  • Yeah I have, no luck though EDIT: Sorry didn't read the comment correctly. Which identities do you mean exactly? – Koy Jun 17 '20 at 14:27
  • Can you find a pattern for $f([x,x_0,\ldots,x_n])^{(j)}$ and rewrite it in terms of a divided difference? What happens if you add them all up? Can you rearrange all of those terms to make it look like another divided difference? Also, this result smells like you might need to use the binomial theorem https://en.wikipedia.org/wiki/Binomial_theorem – Zim Jun 17 '20 at 15:23

1 Answers1

1

Consider the first derivative. Written as a limit, it can be seen to be

$$\lim_{h\to0}\frac{f[x+h,x_0,\dots,x_n]-f[x,x_0,\dots,x_n]}h=\lim_{h\to0}f[x+h,x,x_0,\dots,x_n]$$

For the second derivative, we then have

$$\lim_{h\to0}\frac{f[x+2h,x+h,x_0,\dots,x_n]-f[x+h,x,x_0,\dots,x_n]}h\\=\lim_{h\to0}2f[x+2h,x+h,x,x_0,\dots,x_n]$$

Note the factor of $2$ comes from $(x+2h)-x=2h$ being on the denominator of the divided difference on the RHS.

Can you spot the pattern?

Simply Beautiful Art
  • 74,685