均差

**均差**（Divided differences）是遞歸除法過程。在數值分析中，可用於計算牛頓多項式形式的多項式插值的係數。在微積分中，均差與導數一起合稱差商，是對函數在一個區間內的平均變化率的測量。

均差也是一種算法，查爾斯・巴貝奇的差分機，是他在 1822 年發表的論文中提出的一種早期的機械計算機，在歷史上意圖用來計算對數表和三角函數表， 它設計在其運算中使用這個算法。

## 定義

給定 n+1 個數據點

　
: $(x_{0},y_{0}),\ldots ,(x_{n},y_{n})$

定義**前向均差**為：

　
: ${\begin{aligned}{\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\}\\\end{aligned}}$

定義**後向均差**為：

　
: ${\begin{aligned}{\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\}\\\end{aligned}}$

## 表示法

假定數據點給出為函數 ƒ，

　
: $(x_{0},f(x_{0})),\ldots ,(x_{n},f(x_{n}))$

其均差可以寫為：

　
: ${\begin{aligned}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\}\end{aligned}}$

對函數 ƒ 在節點 _x_0, ..., _x_n 上的均差還有其他表示法，如：

　
: ${\begin{matrix}{\mathopen {[}}x_{0},\ldots ,x_{n}]f\\{\mathopen {[}}x_{0},\ldots ,x_{n};f]\\{\mathopen {D}}[x_{0},\ldots ,x_{n}]f\\\end{matrix}}$

## 例子

給定 ν=0：

　
: ${\begin{aligned}{\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}}}\end{aligned}}$

為了使涉及的遞歸過程更加清楚，以列表形式展示均差的計算過程：

　
: ${\begin{matrix}x_{0}&[y_{0}]=y_{0}&&&\\&&[y_{0},y_{1}]&&\\x_{1}&[y_{1}]=y_{1}&&[y_{0},y_{1},y_{2}]&\\&&[y_{1},y_{2}]&&[y_{0},y_{1},y_{2},y_{3}]\\x_{2}&[y_{2}]=y_{2}&&[y_{1},y_{2},y_{3}]&\\&&[y_{2},y_{3}]&&\\x_{3}&[y_{3}]=y_{3}&&&\\\end{matrix}}$

## 展開形式

用數學歸納法可證明：

　
: ${\begin{aligned}{\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{aligned}}$

此公式體現了均差的對稱性質。故可推知：任意調換數據點次序，其值不變。

## 性質

* 對稱性：若 $\sigma :\{0,\dots ,n\}\to \{0,\dots ,n\}$ 是一個排列則

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

* 線性：

　
: : ${\begin{aligned}(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{aligned}}$

* 萊布尼茨法則：

　
: : $(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{aligned}{\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}}}\\\end{aligned}}$

這個定義有著不同的計算次序：

　
: ${\begin{aligned}{\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{aligned}}$

以列表形式展示這個定義下均差的計算過程：

　
: ${\begin{matrix}x_{0}&[y_{0}]=y_{0}&&&\\&&[y_{0},y_{1}]&&\\x_{1}&[y_{1}]=y_{1}&&[y_{0},y_{1},y_{2}]&\\&&[y_{0},y_{2}]&&[y_{0},y_{1},y_{2},y_{3}]\\x_{2}&[y_{2}]=y_{2}&&[y_{0},y_{1},y_{3}]&\\&&[y_{0},y_{3}]&&\\x_{3}&[y_{3}]=y_{3}&&&\\\end{matrix}}$

## 牛頓插值法

牛頓插值公式，得名於伊薩克・牛頓爵士，最早發表為他在 1687 年出版的《自然哲學的數學原理》中第三編「宇宙體系」的引理五，此前詹姆斯・格雷果里於 1670 年和牛頓於 1676 年已經分別獨立得出這個成果。一般稱其為連續泰勒展開的離散對應。

使用均差的牛頓插值法為：

　
: ${\begin{aligned}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)\\&=[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})\end{aligned}}$

可以在計算過程中任意增添節點如點 (xn+1,yn+1)，只需計算新增的 n+1 階均差及其插值基函數，而無拉格朗日插值法需重算全部插值基函數之虞。

對均差採用展開形式：

　
: ${\begin{aligned}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})}}\\\end{aligned}}$

以 2 階均差牛頓插值為例：

　
: ${\begin{aligned}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}}}\\\end{aligned}}$

## 前向差分

當數據點呈等距分佈的時候，這個特殊情況叫做「前向差分」。它們比計算一般的均差要容易。

### 定義

給定 n+1 個數據點

　
: $(x_{0},y_{0}),\ldots ,(x_{n},y_{n})$

有著

　
: $x_{i}=x_{0}+ih,\quad h>0{\mbox{ , }}0\leq i\leq n$

定義前向差分為：

　
: ${\begin{aligned}\triangle ^{0}y_{i}&=y_{i}\\\triangle ^{k}y_{i}&=\triangle ^{k-1}y_{i+1}-\triangle ^{k-1}y_{i},\quad 1\leq k\leq n-i\\\end{aligned}}$

前向差分所對應的均差為：

　
: $f[x_{0},x_{1},\ldots ,x_{k}]={\frac {1}{k!h^{k}}}\Delta ^{(k)}f(x_{0})$

### 例子

　
: ${\begin{matrix}y_{0}&&&\\&\triangle y_{0}&&\\y_{1}&&\triangle ^{2}y_{0}&\\&\triangle y_{1}&&\triangle ^{3}y_{0}\\y_{2}&&\triangle ^{2}y_{1}&\\&\triangle y_{2}&&\\y_{3}&&&\\\end{matrix}}$

### 展開形式

差分的展開形式是均差展開形式的特殊情況：

　
: ${\begin{aligned}\triangle ^{k}y_{i}&=\sum _{j=0}^{k}(-1)^{k-j}{\binom {k}{j}}y_{i+j},\quad 0\leq k\leq n-i\end{aligned}}$

這裡的表達式

　
: ${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{aligned}f(x)&=y_{0}+{\frac {x-x_{0}}{h}}\left(\Delta ^{1}y_{0}+{\frac {x-x_{0}-h}{2h}}\left(\Delta ^{2}y_{0}+\cdots \right)\right)\\&=y_{0}+\sum _{k=1}^{n}{\frac {\Delta ^{k}y_{0}}{k!h^{k}}}\prod _{i=0}^{n-1}(x-x_{0}-ih)\\&=y_{0}+\sum _{k=1}^{n}{\frac {\Delta ^{k}y_{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}\\\end{aligned}}$

### 無窮級數

牛頓在 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{aligned}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)\\&=f(a)+\sum _{k=1}^{\infty }{\frac {d^{k}}{dx^{k}}}f(a){\frac {(x-a)^{k}}{k!}}\\\end{aligned}}$

## 冪函數的均差

使用普通函數記號表示冪運算， $p_{n}(x)=x^{n}$ ，有：

　
: ${\begin{aligned}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}^{n}x_{t}^{k_{t}}\end{matrix}}\\\end{aligned}}$

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

## 註釋與引用

## 參考書目

* Louis Melville Milne-Thomson. The Calculus of Finite Differences. American Mathematical Soc. 2000. Chapter 1: Divided Differences [1933]. ISBN 978-0-8218-2107-7.
* Myron B. Allen; Eli L. Isaacson. Numerical Analysis for Applied Science. John Wiley & Sons. 1998. Appendix A. ISBN 978-1-118-03027-1.
* Ron Goldman. Pyramid Algorithms: A Dynamic Programming Approach to Curves and Surfaces for Geometric Modeling. Morgan Kaufmann. 2002. Chapter 4:Newton Interpolation and Difference Triangles. ISBN 978-0-08-051547-2.

## 參見

* 差分
* 差商
* 插值
* 牛頓多項式