均差

均差（Divided differences）是遞歸除法過程。在数值分析中，可用於計算牛頓多項式形式的多項式插值的係數。在微积分中，均差与导数一起合称差商，是对函数在一个区间内的平均变化率的测量。

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

定義
給定n+1個數據點

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

定義前向均差為：

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

定義後向均差為：

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

表示法
假定數據點給出為函數 ƒ，

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

其均差可以寫為：

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

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

: \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{align}
\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{align}

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

:
\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{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}
\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{align}

這個定義有著不同的計算次序：
:
\begin{align}
\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}

以列表形式展示這個定義下均差的計算過程：
:
\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}

牛頓插值法
》的第三編“宇宙體系”的引理五的图例。這裡在橫坐標上有6個點H,I,K,L,M,N，對應著6個值A,B,C,D,E,F，生成一個多項式函數對這6個點上有對應的6個值，計算任意點S對應的值R。牛頓給出了間距為單位值和任意值的兩種情況。]]
牛頓插值公式，得名於伊薩克·牛頓爵士，最早发表为他在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) \\
&=[y_0]+{y}_{0}, {y}_{1}+\cdots+[{y}_{0},{y}_{1},\ldots,{y}_{n}]\prod_{k=0}^{n-1} (x-{x}_{k})
\end{align}
可以在计算过程中任意增添节点如點(xn+1,yn+1)，只需計算新增的n+1階均差及其插值基函數，而无拉格朗日插值法需重算全部插值基函数之虞。

對均差採用展開形式：
:\begin{align}
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{align}

以2階均差牛頓插值為例：
:\begin{align}
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{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}
\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\\
\end{align}

前向差分所对应的均差为：
: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{align}
\triangle^{k}y_{i} &= \sum_{j = 0}^{k} (-1)^{k-j} \binom{k}{j} y_{i+j}, \quad 0 \le k \le n-i
\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) \\
&= 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 \\
\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^kf}{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{align}

冪函數的均差
使用普通函數記號表示冪运算，p_n(x) = x^n，有：
:
\begin{align}
p_j[x_0,\dots,x_n] &= 0 \qquad \forall j
此中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是均差的皮亞諾核。

註釋與引用
参考书目
*
*
*

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