均差

均差（Divided differences）是递归除法过程。在数值分析中，可用于计算牛顿多项式形式的多项式插值的系数。在微积分中，均差与导数一起合称差商，是对函数在一个区间内的平均变化率的测量。

均差也是一种算法，查尔斯·巴贝奇的差分机，是他在1822年发表的论文中提出的一种早期的机械计算机，在历史上意图用来计算对数表和三角函数表，它设计在其运算中使用这个算法。

## 定义

给定n+1个数据点

$$(x_0, y_0),\ldots,(x_{n}, y_{n})$$

定义前向均差为：

$$\begin{align} <pre> \mathopen[y_\nu] &= y_\nu, \quad \nu \in \{ 0,\ldots,n\} \\ \mathopen[y_\nu,\ldots,y_{\nu+j}] &= \frac{[y_{\nu+1},\ldots , y_{\nu+j}] - [y_{\nu},\ldots , y_{\nu+j-1}]}{x_{\nu+j}-x_\nu}, \quad \nu\in\{0,\ldots,n-j\},\ j\in\{1,\ldots,n\} \\ </pre> \end{align}$$

定义后向均差为：

$$\begin{align} <pre> \mathopen[y_\nu] &= y_{\nu},\quad \nu \in \{ 0,\ldots,n\} \\ \mathopen[y_\nu,\ldots,y_{\nu-j}] &= \frac{[y_\nu,\ldots , y_{\nu-j+1}] - [y_{\nu-1},\ldots , y_{\nu-j}]}{x_\nu - x_{\nu-j}}, \quad \nu\in\{j,\ldots,n\},\ j\in\{1,\ldots,n\} \\ </pre> \end{align}$$

## 表示法

假定数据点给出为函数 ƒ。

$$(x_0, f(x_0)),\ldots,(x_{n}, f(x_{n}))$$

其均差可以写为：

$$\begin{align} <pre> f[x_\nu] &= f(x_{\nu}), \qquad \nu \in \{ 0,\ldots,n \} \\ f[x_\nu,\ldots,x_{\nu+j}] &= \frac{f[x_{\nu+1},\ldots , x_{\nu+j}] - f[x_\nu,\ldots , x_{\nu+j-1}]}{x_{\nu+j}-x_\nu}, \quad \nu\in\{0,\ldots,n-j\},\ j\in\{1,\ldots,n\} </pre> \end{align}$$

对函数 ƒ 在节点 x0, ..., xn 上的均差还有其他表示法，如：

$$\begin{matrix} <pre> \mathopen [x_0,\ldots,x_n]f \\ </pre> \mathopen [x_0,\ldots,x_n;f] \\ \mathopen D[x_0,\ldots,x_n]f \\ \end{matrix}$$

## 例子

给定ν=0：

$$\begin{align} <pre> \mathopen[y_0] &= y_0 \\ \mathopen[y_0,y_1] &= \frac{y_1-y_0}{x_1-x_0} \\ \mathopen[y_0,y_1,y_2] &= \frac{\mathopen[y_1,y_2]-\mathopen[y_0,y_1]}{x_2-x_0} \\ \mathopen[y_0,y_1,y_2,y_3] &= \frac{\mathopen[y_1,y_2,y_3]-\mathopen[y_0,y_1,y_2]}{x_3-x_0} \\ \mathopen[y_0,y_1,\dots,y_n] &= \frac{\mathopen[y_1,y_2,\dots,y_n]-\mathopen[y_0,y_1,\dots,y_{n-1}]}{x_n-x_0} </pre> \end{align}$$

为了使涉及的递归过程更加清楚，以列表形式展示均差的计算过程：

$$\begin{matrix} x_0 & [y_0] = y_0 & & & \\ <pre> & & [y_0,y_1] & & \\ </pre> x_1 & [y_1] = y_1 & & [y_0,y_1,y_2] & \\ <pre> & & [y_1,y_2] & & [y_0,y_1,y_2,y_3]\\ </pre> x_2 & [y_2] = y_2 & & [y_1,y_2,y_3] & \\ <pre> & & [y_2,y_3] & & \\ </pre> x_3 & [y_3] = y_3 & & & \\ \end{matrix}$$

## 展开形式

用数学归纳法可证明

$$\begin{align} \mathopen[y_0] &= y_0 \\ \mathopen[y_0,y_1] &= \frac{y_1-y_0}{x_1-x_0} = \frac{y_0}{x_0-x_1} + \frac{y_1}{x_1-x_0}\\ <pre> &= \sum_{j=0}^{1} \frac{y_j} { \prod_{k=0,k\neq j}^{1} (x_j-x_k)} \\ </pre> \mathopen[y_0,y_1,y_2] &= \frac{\cfrac{y_1}{x_1-x_2} + \cfrac{y_2}{x_2-x_1} - \cfrac{y_0}{x_0-x_1} - \cfrac{y_1}{x_1-x_0}}{x_2-x_0} \\ <pre> &= \frac{y_0}{(x_0-x_1)(x_0-x_2)} + \frac{y_1}{(x_1-x_0)(x_1-x_2)} + \frac{y_2}{(x_2-x_0)(x_2-x_1)} \\ &= \sum_{j=0}^{2} \frac{y_j} {\prod_{k=0,k\neq j}^{2} (x_j-x_k)} \\ </pre> \mathopen[y_0, y_1,\dots, y_n] &=\sum_{j=0}^{n} \frac{y_j} {\prod_{k=0,k\neq j}^{n} (x_j-x_k)} \\ \mathopen[y_0, y_1,\dots, y_{n+1}] &=\frac{\sum_{j=1}^{n+1} \frac{y_j}{\prod_{k=1,\, k\neq j}^{n+1} (x_j-x_k)} - \sum_{j=0}^{n} \frac{y_j}{\prod_{k=0,\, k\neq j}^{n} (x_j-x_k)}}{x_{n+1}-x_0} \\ <pre> &= \frac{\frac {y_{n+1}}{\prod_{k=1}^{n} (x_{n+1}-x_k)} + \sum_{j=1}^{n} y_j\left(\frac{1}{\prod_{k=1,\, k\neq j}^{n+1} (x_j-x_k)}-\frac{1}{\prod_{k=0,\, k\neq j}^{n} (x_j-x_k)}\right) - \frac{y_0}{\prod_{k=1}^{n} (x_0-x_k)}}{x_{n+1}-x_0} \\ &= \frac{\frac {y_{n+1}}{\prod_{k=1}^{n} (x_{n+1}-x_k)} + \sum_{j=1}^{n} y_j\left(\frac{x_j-x_0}{\prod_{k=0,\, k\neq j}^{n+1} (x_j-x_k)}-\frac{x_j-x_{n+1}}{\prod_{k=0,\, k\neq j}^{n+1} (x_j-x_k)}\right) - \frac{y_0}{\prod_{k=1}^{n} (x_0-x_k)}}{x_{n+1}-x_0} \\ &= \frac{\frac {y_{n+1}}{\prod_{k=1}^{n} (x_{n+1}-x_k)} + \sum_{j=1}^{n} y_j\left(\frac{x_{n+1}-x_0}{\prod_{k=0,\, k\neq j}^{n+1} (x_j-x_k)}\right) - \frac{y_0}{\prod_{k=1}^{n} (x_0-x_k)}}{x_{n+1}-x_0} \\ &= \frac {y_{n+1}}{\prod_{k=0}^{n} (x_{n+1}-x_k)} + \sum_{j=1}^{n} \frac{y_j}{\prod_{k=0,\, k\neq j}^{n+1} (x_j-x_k)} + \frac{y_0}{\prod_{k=1}^{n+1} (x_0-x_k)}\\ &=\sum_{j=0}^{n+1} \frac{y_j}{\prod_{k=0,\, k\neq j}^{n+1} (x_j-x_k)} </pre> \end{align}$$

$$\begin{align} \mathopen[y_0] &= y_0 \\ \mathopen[y_0,y_1] &= \frac{y_0}{x_0-x_1} + \frac{y_1}{x_1-x_0} \\ \mathopen[y_0,y_1,y_2] &= \frac{y_0}{(x_0-x_1)(x_0-x_2)} + \frac{y_1}{(x_1-x_0)(x_1-x_2)} + \frac{y_2}{(x_2-x_0)(x_2-x_1)} \\ \mathopen[y_0, y_1,\dots, y_n] &=\sum_{j=0}^{n} \frac{y_j}{\prod_{k=0,\, k\neq j}^{n} (x_j-x_k)} \\ \end{align}$$

此公式体现了均差的对称性质。故可推知：任意调换数据点次序，其值不变。

## 性质

- 对称性：若$\sigma : \{0, \dots, n\} \to \{0, \dots, n\}$是一个排列则

$$f[x_0, \dots, x_n] = f[x_{\sigma(0)}, \dots, x_{\sigma(n)}]$$

$$\begin{align} (f+g)[x_0,\dots,x_n] &= f[x_0,\dots,x_n] + g[x_0,\dots,x_n] \\ (\lambda\cdot f)[x_0,\dots,x_n] &= \lambda\cdot f[x_0,\dots,x_n] \\ \end{align}$$

$$(f\cdot g)[x_0,\dots,x_n] = f[x_0]\cdot g[x_0,\dots,x_n] + f[x_0,x_1]\cdot g[x_1,\dots,x_n] + \dots + f[x_0,\dots,x_n]\cdot g[x_n]$$

$$\exists \xi \in (\min\{x_0,\dots,x_n\},\max\{x_0,\dots,x_n\}) \quad f[x_0,\dots,x_n] = \frac{f^{(n)}(\xi)}{n!}$$

## 等价定义

通过对换 n 阶均差中(x0,y0)与(xn-1,yn-1)，可得到等价定义：

$$\begin{align} <pre> \mathopen[y_0,y_1,\dots,y_{n-1},y_n] &= \frac{\mathopen[y_1,y_2,\dots,y_n]-\mathopen[y_0,y_1,\dots,y_{n-1}]}{x_n-x_0} \\ &= \frac{\mathopen[y_1,\dots,y_{n-2},y_0,y_n]-\mathopen[y_{n-1},y_1,\dots,y_{n-2},y_0]}{x_n-x_{n-1}} \\ &= \frac{\mathopen[y_0,\dots,y_{n-2},y_n]-\mathopen[y_0,y_1,\dots,y_{n-1}]}{x_n-x_{n-1}} \\ </pre> \end{align}$$

这个定义有着不同的计算次序：

$$\begin{align} <pre> \mathopen[y_0] &= y_0 \\ \mathopen[y_0,y_1] &= \frac{y_1-y_0}{x_1-x_0} \\ \mathopen[y_0,y_1,y_2] &= \frac{\mathopen[y_0,y_2]-\mathopen[y_0,y_1]}{x_2-x_1} \\ \mathopen[y_0,y_1,y_2,y_3] &= \frac{\mathopen[y_0,y_1,y_3]-\mathopen[y_0,y_1,y_2]}{x_3-x_2} \\ \mathopen[y_0,y_1,\dots,y_n] &= \frac{\mathopen[y_0,\dots,y_{n-2},y_n]-\mathopen[y_0,y_1,\dots,y_{n-1}]}{x_n-x_{n-1}} \\ \end{align} </pre>$$

以列表形式展示这个定义下均差的计算过程：

$$\begin{matrix} x_0 & [y_0] = y_0 & & & \\ <pre> & & [y_0,y_1] & & \\ </pre> x_1 & [y_1] = y_1 & & [y_0,y_1,y_2] & \\ <pre> & & [y_0,y_2] & & [y_0,y_1,y_2,y_3]\\ </pre> x_2 & [y_2] = y_2 & & [y_0,y_1,y_3] & \\ <pre> & & [y_0,y_3] & & \\ </pre> x_3 & [y_3] = y_3 & & & \\ \end{matrix}$$

## 牛顿插值法

<image>

牛顿插值公式，得名于伊萨克·牛顿爵士，最早发表为他在1687年出版的《自然哲学的数学原理》中第三编“宇宙体系”的引理五，此前詹姆斯·格雷果里于1670年和牛顿于1676年已经分别独立得出这个成果。一般称其为连续泰勒展开的离散对应。

使用均差的牛顿插值法为：

$$\begin{align} N_n(x) &= y_0 + (x-{x}_{0})\left([{y}_{0}, {y}_{1}] + (x-{x}_{1})\left([{y}_{0}, {y}_{1},{y}_{2}] + \cdots\right)\right) \\ <pre> &=[y_0]+[{y}_{0}, {y}_{1}](x-{x}_{0})+\cdots+[{y}_{0},{y}_{1},\ldots,{y}_{n}]\prod_{k=0}^{n-1} (x-{x}_{k}) </pre> \end{align}$$

可以在计算过程中任意增添节点如点(xn+1,yn+1)，只需计算新增的n+1阶均差及其插值基函数，而无拉格朗日插值法需重算全部插值基函数之虞。

对均差采用展开形式：

$$\begin{align} <pre> N_n(x) &= y_0 + y_0\frac{x-{x}_{0}}{x_0-x_1}+ y_1\frac{x-{x}_{0}}{x_1-x_0}+\cdots+ \sum_{j=0}^{n} y_j \frac{\prod_{k=0}^{n-1} (x-{x}_{k})} {\prod_{k=0,\, k\neq j}^{n} (x_j-x_k)} \\ </pre> \end{align}$$

以2阶均差牛顿插值为例：

$$\begin{align} <pre> N_2(x)&=y_0\left(1+ \frac{x-{x}_{0}}{x_0-x_1}+\frac{(x-x_0)(x-x_1)}{(x_0-x_1)(x_0-x_2)}\right) + y_1\left(\frac{x-{x}_{0}}{x_1-x_0}+\frac{(x-x_0)(x-x_1)}{(x_1-x_0)(x_1-x_2)}\right) + y_2\frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)} \\ &=y_0\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)} + y_1\frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)} + y_2\frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)} \\ &= \sum_{j=0}^{2} y_j \prod_{\begin{smallmatrix} k=0 \\ k\neq j \end{smallmatrix}}^{2} \frac{x-{x}_{k}} { x_j-x_k} \\ </pre> \end{align}$$

## 前向差分

当数据点呈等距分布的时候，这个特殊情况叫做“前向差分”。它们比计算一般的均差要容易。

### 定义

给定n+1个数据点

$$(x_0, y_0),\ldots,(x_{n}, y_{n})$$

有着

$$x_i = x_0 + ih , \quad h > 0 \mbox{ , } 0 \le i \le n$$

定义前向差分为：

$$\begin{align} <pre> \triangle^{0}y_{i} &= y_{i} \\ \triangle^{k}y_{i} &= \triangle^{k-1}y_{i+1} - \triangle^{k-1}y_{i} , \quad 1 \le k \le n-i\\ </pre> \end{align}$$

前向差分所对应的均差为：

$$f[x_0, x_1, \ldots , x_k] = \frac{1}{k!h^k}\Delta^{(k)}f(x_0)$$

### 例子

$$\begin{matrix} y_0 & & & \\ <pre> & \triangle y_0 & & \\ </pre> y_1 & & \triangle^{2} y_0 & \\ <pre> & \triangle y_1 & & \triangle^{3} y_0\\ </pre> y_2 & & \triangle^{2} y_1 & \\ <pre> & \triangle y_2 & & \\ </pre> y_3 & & & \\ \end{matrix}$$

### 展开形式

差分的展开形式是均差展开形式的特殊情况：

$$\begin{align} <pre> \triangle^{k}y_{i} &= \sum_{j = 0}^{k} (-1)^{k-j} \binom{k}{j} y_{i+j}, \quad 0 \le k \le n-i </pre> \end{align}$$

这里的表达式

$${n \choose k} = \frac{(n)_k}{k!} \quad\quad (n)_k=n(n-1)(n-2)\cdots(n-k+1)$$

是二项式系数，其中的(n)k是“下降阶乘幂”，空积(n)0被定义为1。

### 插值公式

其对应的牛顿插值公式为：

$$\begin{align} f(x) &= y_0 + \frac {x-x_0} {h} \left( \Delta^1y_0 + \frac {x-x_0-h} {2h}\left(\Delta^2y_0 + \cdots \right) \right) \\ <pre> &= y_0 + \sum_{k=1}^n \frac{\Delta^ky_0}{k!h^k} \prod_{i=0}^{n-1} (x-x_0-ih) \\ &= y_0 + \sum_{k=1}^n \frac{\Delta^ky_0}{k!} \prod_{i=0}^{n-1} (\frac{x-x_0}{h}-i) \\ &= \sum_{k=0}^n {\frac{x-x_0}{h} \choose k}~ \Delta^k y_0 \\ </pre> \end{align}$$

### 无穷级数

牛顿在1665年得出并在1671年写的《流数法》中发表了ln(1+x)的无穷级数，在1666年得出了arcsin(x)和arctan(x)的无穷级数，在1669年的《分析学》中发表了sin(x)、cos(x)、arcsin(x)和ex的无穷级数；莱布尼茨在1673年大概也得出了sin(x)、cos(x)和arctan(x)的无穷级数。布鲁克·泰勒在1715年著作《Methodus Incrementorum Directa et Inversa》中研讨了“有限差分”方法，其中论述了他在1712年得出的泰勒定理，这个成果此前詹姆斯·格雷果里在1670年和莱布尼茨在1673年已经得出，而约翰·伯努利在1694年已经在《教师学报》发表。

他对牛顿的均差的步长取趋于0的极限，得出：

$$\begin{align} f(x) &= f(a) + \lim_{h \to 0}\sum_{k=1}^\infty \frac{\Delta_h^k[f](a)}{k!h^k} \prod_{i=0}^{k-1} ((x-a)-ih) \\ <pre> &= f(a) + \sum_{k=1}^\infty \frac{d^k}{dx^k}f(a) \frac{(x-a)^k}{k!} \\ </pre> \end{align}$$

## 幂函数的均差

使用普通函数记号表示幂运算，$p_n(x) = x^n$，有：

$$\begin{align} p_j[x_0,\dots,x_n] &= 0 \qquad \forall j<n\\ p_n[x_0,\dots,x_n] &= 1 \\ p_{n+1}[x_0,\dots,x_n] &= x_0 + \dots + x_n \\ p_{n+m}[x_0,\dots,x_n]&= \sum_{k_0+\cdots+k_n=m} \begin{matrix} \prod_{t=0}^nx_{t}^{k_{t}} \end{matrix} \\ \end{align}$$

此中n+1元m次齐次多项式的记法同于多项式定理。

## 泰勒形式

泰勒级数和任何其他的函数级数，在原理上都可以用来逼近均差。将泰勒级数表示为:

$$f = f(0) p_0 + f'(0) p_1 + \frac{f''(0)}{2!} p_2 + \dots$$

均差的泰勒级数为：

$$f[x_0,\dots,x_n] = f(0)p_0[x_0,\dots,x_n] + f'(0) p_1[x_0,\dots,x_n] + \dots + \frac{f^{(n)}(0)}{n!} p_n[x_0,\dots,x_n] + \dots$$

前$n$项消失了，因为均差的阶高于多项式的阶。可以得出均差的泰勒级数本质上开始于：

$$\frac{f^{(n)}(0)}{n!}$$

依据均差中值定理，这也是均差的最简单逼近。

## 皮亚诺形式

均差还可以表达为

$$f[x_0,\ldots,x_n] = \frac{1}{n!} \int_{x_0}^{x_n} f^{(n)}(t)B_{n-1}(t) \, dt$$

这里的Bn-1是数据点x0,...,xn的n-1次B样条，而f(n)是函数f的n阶导数。这叫做均差的皮亚诺形式，而Bn-1是均差的皮亚诺核。