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
\begin{equation}
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}.
\end{equation}
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} $$
Hope to add bits of mathematics or mathematical news I find interesting.
No comments:
Post a Comment