Thursday, May 2, 2013

Divided differences

I stumbled on this concept in an beautiful old paper of  Feller.    This seems to be well known to numerical analysts, but since  this construction got me out of a jam I thought it would nice to advertise it.  Most of what follows is from the    Milne Thompson's  classic "The Calculus of Finite Differences".

To start, suppose $\newcommand{\bR}{\mathbb{R}}$ $\newcommand{\bZ}{\mathbb{Z}}$  that $f:\bR\to \bR$ is a smooth function. For any  pairwise distinct points $x_0, x_1,\dotsc,x_n$ we define recursively

$$f[x_0] :=f(x_0),\;\; f[x_0,x_1]:=\frac{f(x_1)-f(x_0)}{x_1-x_0},$$

$$f[x_0,x_1,\dotsc, x_n] :=\frac{f[x_1,\dotsc,x_n]-f[x_0,\dotsc, x_{n-1}]}{x_n-x_0}=\frac{f[x_0,\dotsc,x_{n-1}]-f[x_1,\dotsc, x_n]}{x_0-x_n}.\tag{R}\label{R}$$

The   quantity $f[x_0,\dotsc, x_n]$ is called the $n$-th divided difference of $f$ at the nodes $x_0,\dotsc, x_n$.  Note that we have

$$f[x_0,x_1]= \frac{f(x_0)}{x_0-x_1}+\frac{f(x_1)}{x_1-x_0}.$$

Observe that

$$f[x_1,x_2]- f[x_0,x_1]= \frac{f(x_1)}{x_1-x_2}+\frac{f(x_2)}{x_2-x_1}- \frac{f(x_0)}{x_0-x_1}-\frac{f(x_1)}{x_1-x_0}$$

$$=\frac{f(x_2)}{x_2-x_1}+\frac{f(x_1)(x_2-x_0)}{(x_1-x_2)(x_1-x_0)} - \frac{f(x_0)}{x_0-x_1}.$$

We deduce

f[x_0,x_1,x_2]=\frac{ f[x_1,x_2]- f[x_0,x_1]}{x_2-x_0}=\frac{f(x_0)}{(x_0-x_1)(x_0-x_2)}+\frac{f(x_1)}{(x_1-x_2)(x_1-x_0)}+ \frac{f(x_2)}{(x_2-x_0)(x_2-x_1)}\tag{I}\label{I}.

Arguing inductively  we  obtain the following  description

$$f[x_0, x_1,\dotsc, x_n]=\frac{f(x_0)}{(x_0-x_1)(x_0-x_2)\cdots (x_0-x_n)}+\frac{f(x_1)}{(x_1-x_0)(x_1-x_2)\cdots(x_1-x_n)}+\cdots + \frac{f(x_n)}{(x_n-x_0)\cdots (x_n-x_{n-1})}.$$

This last expression can be given a more symmetric   expression by introducing the polynomial

$$\Phi_{x_0,\dotsc,x_n}:=\prod_{k=0}^n (x-x_k).$$

We then have

$$\Phi'_{x_0,\dotsc, x_n}(x)=(x-x_1)\cdots (x-x_n)+(x-x_0)(x-x_2)\cdots (x-x_n)+\cdots +(x-x_0)\cdots (x-x_{n-1}),$$

$$f[x_0, x_1,\dotsc, x_n]=\sum_{k=0}^n\frac{f(x_k)}{\Phi'_{x_0,\dotsc,x_n}(x_k)}.\tag{1}\label{1}$$

The last  equality  shows  has the following useful consequence.

Proposition 1.  The $n$-th divided difference  $f[x_0,\dotsc, x_n]$  does not change if we permute the nodes $x_0, x_1,\dotsc, x_n$. $\Box$

The equality   (\ref{1}) can be conveniently  rephrased in terms of Vandermonde-like determinants.    Denote by $V(x_0,\dotsc, x_n)$ the $(n+1)\times (n+1)$ matrix

$$V(x_0, \dotsc, x_n)=\left[ \begin{array}{ccccc} 1 & 1 & 1 &\cdots & 1\\ x_0 & x_1 & x_2 &\cdots & x_n\\ x_0^2 & x_1^2 & x_2^2 & \cdots & x_n^2\\ \vdots & \vdots & \vdots & \vdots & \vdots\\ x_0^n & x_1^n & x_2^n & \cdots & x_n^n \end{array} \right],$$
and by $V_f(x_0,\dotsc, x_n)$ the $(n+1)\times (n+1)$ matrix

$$V_f(x_0, \dotsc, x_n)=\left[ \begin{array}{ccccc} 1 & 1 & 1 &\cdots & 1\\ x_0 & x_1 & x_2 &\cdots & x_n\\ x_0^2 & x_1^2 & x_2^2 & \cdots & x_n^2\\ \vdots & \vdots & \vdots & \vdots & \vdots\\ x_0^{n-1} & x_1^{n-1} & x_2^{n-1} & \cdots & x_n^{n-1}\\ f(x_0) & f(x_1) & f(x_2) & \cdots & f(x_n) \end{array} \right].$$

Expanding along the last row of $V_f(x_0,\dotsc, x_n)$ we obtain  the following   alternate description of the $n$-th divided difference

$$f[x_0,x_1,\dotsc, x_n]= \frac{\det V_f(x_0,\dotsc, x_n)}{V(x_0,\dotsc, x_n)}. \tag{V}$$

Next, we want to prove that $f[x_0,\dotsc, x_n]$   makes sense  even if the nodes  are not pairwise disjoint.     We need  to make    small technical  digression.

Consider the $n$-simplex

$$\Delta_n :=\Bigl\{ (t_0,\dotsc, t_n)\in\bR^{n+1}_{\geq 0};\;\;\sum_{k=0}^n t_k=1\Bigr\}.$$

We can   view $\Delta_n$  as the graph of the function

$$T_n\ni (t_1,\dotsc, t_n)\mapsto t_0=1-(t_1+\cdots +t_n)\in\bR,$$

where
$$T_n:=\bigr\{ (t_1,\dotsc, t_n)\in\bR^n_{\geq 0};\;\; t_1+t_2+\cdots +t_n\leq 1\bigr\}.$$

If we use $(t_1,\dotsc, t_n)$ as coordinates on  $\Delta_n$, then  we deduce that  $dA_{\Delta_n}$,  the area    density on $\Delta_n$ is given by

$$|dA_{\Delta_n}(t_1,\dotsc, t_n)|={\sqrt{n+1}} |dt_1\cdots d t_n|.$$

On $T_n$ we can introduce new coordinates

$$s_1=t_1+\cdots +t_n, \;\; s_2= t_2+\cdots +t_n,\dotsc, s_n=t_n.$$

We observe that

$$0\leq s_n\leq \cdots \leq s_1\leq 1,\;\; dt_1\cdots dt_n=ds_1\cdots ds_n,$$

$$t_1=s_1-s_2,\;\;t_2=s_2-s_3,\dotsc.$$

If $u: \Delta_n\to \bR$ is a continuous function,  then  we can regard it as a function of the  variables $s_1, \dotsc, s_n$ and we have

$$\int_{\Delta_n} u(t_0,\dotsc, t_n) |dA_{\Delta_n}| = \sqrt{n+1}\int_{0\leq s_n\leq \cdots \leq s_1\leq 1} u(s_1, \dotsc, s_n) ds_1\cdots ds_n$$

$$={\sqrt{n+1}}\int_0^1d s_1 \int_0^{s_1} ds_2 \cdots \int_0^{s_{n-1}} u(s_1,\dotsc, s_n) ds_n.$$

Hence

$$\int_0^1d s_1 \int_0^{s_1} ds_2 \cdots \int_0^{s_{n-1}} u(s_1,\dotsc, s_n)=\frac{1}{\sqrt{n+1}}\int_{\Delta_n} u(t_0,\dotsc, t_n) |dA|. \tag{2} \label{2}$$

Proposition 2. (Hermite)   For any $n>0$ and  pairwise distinct  points $x_0,\dotsc, x_n\in\bR$ we have

$$f[x_0,\dotsc, x_n]=\frac{1}{\sqrt{n+1}}\int_{\Delta_n} f^{(n)} (t_0x_0+\cdots +t_n x_n) dA(t_0,\dotsc, t_n). \tag{3} \label{3}$$

Proof.       In  view of (\ref{2}) we see that  (\ref{3})  is equivalent to

$$f[x_0,\dotsc, x_n]= \int_0^1d s_1 \int_0^{s_1} ds_2 \cdots \int_0^{s_{n-1}} f^{(n)} (y_n) ds_n, \tag{4}\label{4}$$

where

$$y_n=(1-s_1) x_0 +(s_1-s_2) x_1+\cdots +(s_{n-1}-s_n)x_{n-1}+ s_n x_n.\tag{5} \label{5}$$

For $n=1$ the right-hand-side of (\ref{4})  becomes

$$\int_0^1 f'(x_0+t(x_1-x_0)) dt = \frac{1}{x_1-x_0} (f(x_1)-f(x_0))=f[x_0,x_1].$$

We now proceed inductively  and we observe that

$$\int_0^{s_{n-1}} f^{(n)} (y_n) ds_n = \frac{1}{x_n-x_{n-1}} f^{(n-1)}\bigl(\; (1-s_1) x_0 +(s_1-s_2) x_1+\cdots +(s_{n-2}-s_{n-1})x_{n-2} +s_{n-1} x_n\;\bigr)$$

$$- \frac{1}{x_n-x_{n-1}} f^{(n-1)}\bigl(\; (1-s_1) x_0 +(s_1-s_2) x_1+\cdots +(s_{n-2}-s_{n-1})x_{n-2}+s_{n-1} x_{n-1}\;\bigr).$$

Hence

$$\int_0^1d s_1 \int_0^{s_1} ds_2 \cdots \int_0^{s_{n-1}} f^{(n)} (y_n) ds_n$$

$$= \frac{1}{x_n-x_{n-1}} \int_0^1d s_1 \int_0^{s_1} ds_2 \cdots \int_0^{s_{n-2}}f^{(n-1)}\bigl(\; (1-s_1) x_0 +(s_1-s_2) x_1+\cdots +(s_{n-2}-s_{n-1})x_{n-2} +s_{n-1} x_n\;\bigr) ds_{n-1}$$

$$- \frac{1}{x_n-x_{n-1}} \int_0^1d s_1 \int_0^{s_1} ds_2 \cdots \int_0^{s_{n-2}} f^{(n-1)}\bigl(\; (1-s_1) x_0 +(s_1-s_2) x_1+\cdots +(s_{n-2}-s_{n-1})x_{n-2}+s_{n-1} x_{n-1}\;\bigr) ds_{n-1}$$

$$\frac{1}{x_n-x_{n-1}}f[x_0,\dotsc,x_{n-2},x_{n}]- \frac{1}{x_n-x_{n-1}}f[x_0,\dotsc, x_{n-2}, x_{n-1}]$$

$$= \frac{1}{x_n-x_{n-1}}f[x_0,\dotsc,x_{n-2},x_{n}]- \frac{1}{x_n-x_{n-1}}f[x_{n-1}, x_0,\dotsc, x_{n-2}]$$

$$= f[x_{n-1}, x_0,\dotsc, x_{n-2}, x_{n}]= f[x_0,x_1,\dotsc, x_{n-1}, x_n].\;\;\Box$$

For fixed $f$, the $n$-th divided difference $f[x_0,\dotsc,x_n]$  defines a smooth  real valued function  on the confinguration space $\newcommand{\eC}{\mathscr{C}}$

$$\eC_{n+1}=\bigl\lbrace\; (x_0,\dotsc, x_n)\in\bR^{n+1};\;\;x_i\neq x_j,\;\;\forall i\neq j\;\bigr\rbrace.$$

The above result shows that   this function admits a smooth extension to $\bR^{n+1}$.  This extension is unique since $\eC_{n+1}$ is dense in $\bR^{n+1}$.

The volume of the connected region

$$S_n=\bigl\lbrace (s_1,\dotsc, s_n)\in\bR^n;\;\;0\leq s_n\leq \cdot \leq s_1\leq 1\;\bigr\rbrace$$
is $\frac{1}{n!}$. Invoking  Proposition 2 we deduce that for any $x_0,\dotsc, x_n\in \bR$ there exists $\xi\in [\min x_j,\max x_k]$ such that
$$f[x_0,\dotsc, x_n]=\frac{1}{n!} f^{(n)}(\xi).$$
In particular, this implies that
$$f[\,\underbrace{x,\dotsc,x}_{n+1}\,]=\frac{1}{n!} f^{(n)}(x).\tag{6} \label{6}$$
The recurrence relation (\ref{R}) extends by continuity to any nodes $x_0,\dotsc, x_n$ not necessarily distinct.   Given the sequence of  nodes $x_0,\dotsc, x_n,\dotsc$ we  defined following  Feller  the sequence of polynomials $F_n(x)$

$$F_n(x):=\sum_{k=0}^n f[x_0,\dotsc, x_k] (x-x_0)\cdots (x-x_{k-1}).$$

Observe  that

$$F_0(x)= f(x_0),\;\; F_1(x)= F_0(x)+f[x_0,x_1)(x-x_0), ...$$

Define

$$R_n(x)= f[x,x_0,\dotsc, x_n](x-x_0)\cdots (x-x_n).$$

Observe that

$$R_0(x)=f(x)-f(x_0),$$

$$R_{n}(x) =\bigl(f[x,x_0,\dotsc, x_{n-1}]- f[x_0,\dotsc, x_n]\bigr)(x-x_0)\dotsc (x-x_{n-1})= R_{n-1}(x) +\bigl(\, F_{n-1}(x)-F_n(x)\,\bigr)$$

We deduce that

$$R_n(x) = R_0(x) + F_0(x)-F_n(x)$$

which translates  into Newton's interpolation formula

$$f(x) = F_n(x) + R_n(x)$$

$$= f(x_0)+f[x_0,x_1](x-x_0)+\cdots +f[x_0,x_1,\dotsc,x_n](x-x_0)\cdots (x-x_{n-1})+ f[x,x_0,\dotsc, x_n](x-x_0)\cdots (x-x_n). \tag{N}$$