📂Numerical Analysis

Derivation of Newton's Forward Difference Formula

Formulas

For different data $x_{0} , \cdots , x_{n}$ of $(x_{0}, f(x_{0} )) , \cdots , (x_{n} , f( x_{n} ) )$, $$p_{n} (x) =\sum_{i=0}^{n} f [ x_{0} , \cdots , x_{i} ] \prod_{j=0}^{i-1} (x - x_{j} )$$

Description

Though it seems complicated, when actually expanding for $n=0,1,2$, it simplifies as follows. $$\begin{align*} p_{0} (x) =& f(x_{0}) \\ p_{1} (x) =& f( x_{0} ) + (x - x_{0} ) f [ x_{0} , x_{1} ] \\ p_{2} (x) =& f( x_{0} ) + (x - x_{0} ) f [ x_{0} , x_{1} ] + ( x - x_{0} ) ( x - x_{1} ) f [ x_{0} , x_{1} , x_{2} ] \end{align*}$$ Newton’s divided differences formula uses divided differences for representing polynomial interpolation, and although it seems more complex than Lagrange’s formula, it’s much more convenient when data needs to be updated. Newton’s divided differences formula recursively expresses as $$p_{n} (x) = p_{n-1}(x) + f[x_{0} , \cdots , x_{n} ] \prod_{i=0}^{n-1} (x - x_{i})$$ which means, if only Lagrange’s formula existed, one would need to go through the trouble of calculating the inverse matrix of size $(n+1) \times (n+1)$ again even though $p_{n-1}$ is already known. Regardless of the calculation method, the result is exactly the same as Lagrange’s formula, so if there is not much data added, Newton’s divided differences formula can be very useful.

Moreover, by utilizing the fact that it is exactly the same but looks different from Lagrange’s formula, various useful theorems about divided differences can be proven.

Derivation

Strategy: If the difference between $p_{n}$ and $p_{n-1}$ is called $C$, then the highest-order term coefficients of $p_{n}$ and $C$ must be the same, so by calculating the coefficient of $C$ indirectly, the recursion formula is derived.

---

If it is said that $$p_{n}(x) = p_{n-1}(x) + C(x)$$, then $\deg C = n$ and for $i= 0, \cdots, (n-1)$, $$p_{n}(x_{i}) = f(x_{i}) = p_{n-1}(x_{i})$$ thus for some constant $a_{n} \ne 0$, $$C (x) = a_{n} (x - x_{0}) \cdots (x - x_{n-1})$$ appears like this. Since the highest order terms of $p_{n}$ and $C$ are the same, it needs to be shown that $a_{n} = f [ x_{0} , \cdots , x_{n}]$ holds. Let’s say polynomial interpolation obtained from data $\left\{ x_{0}, \cdots , x_{k} \right\}$ with $x_{k}$ removed is $\left\{ x_{0}, \cdots , x_{k-1} \right\}$ and the polynomial interpolation obtained from data $\left\{ x_{1}, \cdots , x_{k} \right\}$ missing $x_{0}$ is $R_{k-1}(x)$. Each alphabet indicates Left and Right respectively. Let’s set $p_{k}$ as follows. $$p_{k}(x) := {{ (x-x_{0}) R_{k-1} (x) - (x-x_{k}) L_{k-1} (x) } \over { x_{k} - x_{0} }}$$ Then, for $i=1,\cdots , k-1$, $$p_{k}(x_{0}) = L_{k-1} (x_{0}) = f(x_{0})$$

$$p_{k}(x_{i}) = L_{k-1} (x_{i}) = R_{k-1} (x_{i}) = f(x_{i})$$

$$p_{k}(x_{k}) = R_{k-1} (x_{k}) = f(x_{k})$$ Therefore, it’s guaranteed that $p_{k}$ accurately interpolates the given data. When the highest order term’s coefficient of $p_{k}$ is called $a_{k}$, it will be shown by mathematical induction that $a_k = f[ x_{0} , \cdots , x_{k} ]$ holds.

When $k=1$, $$p_{1}(x) = {{ (x-x_{0}) f(x_{1}) - (x-x_{k}) f(x_{0}) (x) } \over { x_{1} - x_{0} }}$$ thus, the coefficient of the highest order term $x$ is $$a_{1} = {{ f(x_{1} - x_{0}) } \over { x_{1} - x_{0} }} = f[x_{0},x_{1}]$$ Assuming $k > 1$ is valid when $a_{k-1} = f[ x_{0} , \cdots , x_{k-1} ]$ holds, the coefficient of the highest order term of $L_{k-1}$ is $f[ x_{0} , \cdots , x_{k-1} ]$, and the highest order term’s coefficient of $R_{k-1}$ is $f[ x_{1} , \cdots , x_{k} ]$. Breaking down the fraction form of $p_{k}$, $$p_{k}(x) = {{ R_{k-1} (x) - L_{k-1} (x) } \over { x_{k} - x_{0} }} x + {{ x_{k} L_{k-1} (x) - x_{0} R_{k-1} (x) } \over { x_{k} - x_{0} }}$$ Therefore, the coefficient of the highest order term $p_{k}(x)$ is $$a_{k} = {{ f[ x_{1} , \cdots , x_{k} ]- f[ x_{0} , \cdots , x_{k-1} ] } \over { x_{k} - x_{0} }} = f[ x_{0} , \cdots , x_{k} ]$$ By mathematical induction, for all natural numbers $n$, $$a_{n} = f [ x_{0} , \cdots , x_{n}]$$

■