均差

均差（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是均差的皮亞諾核。