0
$\begingroup$

Let $f : \mathbb{R} \rightarrow \mathbb{R}$ and let $x = (x_0, x_1, x_2, \dots)$ be a sequence of pairwise distinct real numbers. For every $n \in \{1, 2, \dots\}$ and every ordered $(n+1)$-tuple $(i_0, i_1, \dots, i_n)$ of pairwise distinct indices $i_k \in \{0, 1, 2, \dots\}$, the divided difference $f_x[i_0, i_1, \dots, i_n]$ is defined recursively as follows.

$$ \begin{align} f_x[i_{k + 0}, i_{k + 1}] & := \frac{f(x_{i_{k + 1}}) - f(x_{i_{k + 0}})}{x_{i_{k + 1}} - x_{i_{k + 0}}} \\ f_x[i_{k + 0}, i_{k + 1}, \dots, i_{k + n + 1}] & := \frac{f_x[i_{k + 1}, \dots, i_{k + n + 1}] - f_x[i_{k + 0}, i_{k + 1}, \dots, i_{k + n}]}{x_{i_{k + n + 1}} - x_{i_{k + 0}}} \end{align} $$

I need help proving the following formula, stated without proof on pp. 39-40 of [1], which expresses any value $f(x_n)$ ($n \in \{1, 2, \dots\}$) in terms of $f(x_0)$ and the divided differences $f_x[0, 1, \dots, k]$, $k \in \{0, 1, \dots, n\}$: $$ \begin{align} f(x_n) & = f(x_0) + \sum_{i = 1}^n\left(\prod_{j = 0}^{i - 1} (x_n - x_j)\right)f_x[0, 1, \dots, i] \\ & = f(x_0) + (x_n - x_0) f_x[0, 1] + \cdots + (x_n - x_0)(x_n - x_1)\cdots(x_n - x_{n - 1}) f_x[0, 1, \dots, n] \end{align} $$

According to [1], this formula can be proved by means of induction.


What I've accomplished so far

I can derive the first couple cases, as follows.

$n = 1$

$$ \begin{align} f(x_0) + \sum_{i = 1}^1\left(\prod_{j = 0}^{i - 1} (x_n - x_j)\right)f_x[0, 1, \dots, i] & = f(x_0) + (x_1 - x_0) f_x[0, 1] \\ & = f(x_0) + (x_1 - x_0)\frac{f(x_1) - f(x_0)}{x_1 - x_0} \\ & = f(x_0) + \left(f(x_1) - f(x_0)\right) \\ & = f(x_1) \end{align} $$

$n = 2$

$$ \begin{align} f(x_0) + \sum_{i = 1}^2\left(\prod_{j = 0}^{i - 1}(x_2 - x_j)\right)f_x[0, 1, \dots, i] & = f(x_0) + (x_2 - x_0)f_x[0, 1] + (x_2 - x_0)(x_2 - x_1) f_x[0, 1, 2] \\ & = f(x_0) + (x_2 - x_0)f_x[0, 1] + (x_2 - x_1)\left(f_x[1, 2] - f_x[0, 1]\right) \\ & = f(x_0) + \left((x_2 - x_0) - (x_2 - x_1)\right) f_x[0, 1] + (x_2 - x_1) f_x[1, 2] \\ & = f(x_0) + (x_1 - x_0)f_x[0, 1] + (x_2 - x_1)f_x[1, 2] \\ & = f(x_0) + \left(f(x_1) - f(x_0)\right) + \left(f(x_2) - f(x_1)\right) \\ & = f(x_2) \end{align} $$

Unfortunately, I can't figure out how to extrapolate this to the general case. Any help will be appreciated.


Works cited

[1] Krylov, V. I., "Approximate Calculation of Integrals", Dover 2005 (Originally published 1962)

$\endgroup$
1
$\begingroup$

Using the total symmetry of the indices in brackets in the divided differences, for instance as in $f_x[0,1,…,i,n]=f_x[n,0,1,…,i]$, show per induction in $m=n,n-1,...,0$ that \begin{align} B_m=\sum_{i = m}^n\left(\prod_{j = m}^{i - 1} (x_n - x_j)\right)f_x[0, 1, \dots, i] & = f_x[0, 1, \dots,m-2,m-1, n] \end{align} where the expression on the right is $f_x[0,n]$ for $m=1$ and $f_x[n]=f(x_n)$ for $m=0$.


The $B_m$ follow a recursion similar to the Newton-Lagrange scheme (wrongly named Horner-Ruffini scheme). For the interpolation polynomial of degree $n$ this is \begin{alignat}{2} \\ B_n&=&&&&f_x[0,1,…,n]\\ B_{n-1}&=&(x_n-x_{n-1})&B_n&+&f_x[0,1,…,n-1]\\ &\;\;\vdots\\ B_m&=&(x_n-x_m)&B_{m+1}&+&f_x[0,1,…,m]\\ &\;\;\vdots\\ B_1&=&(x_n-x_1)&B_2&+&f_x[0,1]\\ B_0&=&(x_n-x_0)&B_1&+&\underbrace{f_x[0]}_{=f(x_0)}\\ \end{alignat}

from where the induction hypotheses follows almost naturally.


On the symmetry: $f_x[0,1,2,…,n]$ is the highest degree coefficient for the degree $n$ interpolation polynomial for the sampling points $x_0,x_1,…,x_n$. This is readily visible from the Newton interpolation formula. From the Lagrange interpolation formula for the same interpolating polynomial one sees the independence of this coefficient on the order of the sampling points.

$\endgroup$
  • $\begingroup$ Thanks. I don't understand the formula $B_m=\sum_{i = m}^n\left(\prod_{j = m}^{i - 1} (x_n - x_j)\right)f_x[0, 1, \dots, i]$, which you wrote. Isn't the product always empty there? $\endgroup$ – Evan Aad Apr 10 '15 at 10:50
  • 1
    $\begingroup$ No, only the first one with $i=m$. The next one for $i=m+1$ has the single factor $(x_n-x_m)$. Etc. $\endgroup$ – LutzL Apr 10 '15 at 13:01
  • $\begingroup$ Thank you. And how can I see, please, that there's total symmetry of the indices in brackets in the divided differences, as you stated? $\endgroup$ – Evan Aad Apr 10 '15 at 20:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.