均差

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

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

定義

給定n+1個數據點

$(x_0,y_0),\dots ,(x_n,y_n)$

定義前向均差為：

$\begin{array}{cc}[y_{\nu }]& =y_{\nu },\nu \in \{0,\dots ,n\}\\ [y_{\nu },\dots ,y_{\nu +j}]& =\frac{[y_{\nu +1},\dots ,y_{\nu +j}]-[y_{\nu },\dots ,y_{\nu +j-1}]}{x_{\nu +j}-x_{\nu }},\nu \in \{0,\dots ,n-j\},j\in \{1,\dots ,n\}\\ \end{array}$

定義後向均差為：

$\begin{array}{cc}[y_{\nu }]& =y_{\nu },\nu \in \{0,\dots ,n\}\\ [y_{\nu },\dots ,y_{\nu -j}]& =\frac{[y_{\nu },\dots ,y_{\nu -j+1}]-[y_{\nu -1},\dots ,y_{\nu -j}]}{x_{\nu }-x_{\nu -j}},\nu \in \{j,\dots ,n\},j\in \{1,\dots ,n\}\\ \end{array}$

表示法

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

$(x_0,f(x_0)),\dots ,(x_n,f(x_n))$

其均差可以寫為：

$\begin{array}{cc}f[x_{\nu }]& =f(x_{\nu }),\nu \in \{0,\dots ,n\}\\ f[x_{\nu },\dots ,x_{\nu +j}]& =\frac{f[x_{\nu +1},\dots ,x_{\nu +j}]-f[x_{\nu },\dots ,x_{\nu +j-1}]}{x_{\nu +j}-x_{\nu }},\nu \in \{0,\dots ,n-j\},j\in \{1,\dots ,n\}\end{array}$

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

$\begin{array}{c}[x_0,\dots ,x_n]f\\ [x_0,\dots ,x_n;f]\\ D[x_0,\dots ,x_n]f\end{array}$

例子

給定ν=0：

$\begin{array}{cc}[y_0]& =y_0\\ [y_0,y_1]& =\frac{y_1-y_0}{x_1-x_0}\\ [y_0,y_1,y_2]& =\frac{[y_1,y_2]-[y_0,y_1]}{x_2-x_0}\\ [y_0,y_1,y_2,y_3]& =\frac{[y_1,y_2,y_3]-[y_0,y_1,y_2]}{x_3-x_0}\\ [y_0,y_1,\dots ,y_n]& =\frac{[y_1,y_2,\dots ,y_n]-[y_0,y_1,\dots ,y_{n-1}]}{x_n-x_0}\end{array}$

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

$\begin{array}{ccccc}{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{array}$

展開形式

用數學歸納法可證明：

$\begin{array}{cc}[y_0]& =y_0\\ [y_0,y_1]& =\frac{y_0}{x_0-x_1}+\frac{y_1}{x_1-x_0}\\ [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)}\\ [y_0,y_1,\dots ,y_n]& =\sum _{j=0}^n\frac{y_j}{\prod _{k=0,k\ne j}^n(x_j-x_k)}\\ \end{array}$

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

性质

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

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

• 線性：

$\begin{array}{cc}(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{array}$

• Template:Le：

$(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]$

• Template:Le：

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

等價定義

通過對換 n 阶均差中(x₀,y₀)与(x_n-1,y_n-1)，可得到等價定義：

$\begin{array}{cc}[y_0,y_1,\dots ,y_{n-1},y_n]& =\frac{[y_1,y_2,\dots ,y_n]-[y_0,y_1,\dots ,y_{n-1}]}{x_n-x_0}\\ & =\frac{[y_1,\dots ,y_{n-2},y_0,y_n]-[y_{n-1},y_1,\dots ,y_{n-2},y_0]}{x_n-x_{n-1}}\\ & =\frac{[y_0,\dots ,y_{n-2},y_n]-[y_0,y_1,\dots ,y_{n-1}]}{x_n-x_{n-1}}\\ \end{array}$

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

$\begin{array}{cc}[y_0]& =y_0\\ [y_0,y_1]& =\frac{y_1-y_0}{x_1-x_0}\\ [y_0,y_1,y_2]& =\frac{[y_0,y_2]-[y_0,y_1]}{x_2-x_1}\\ [y_0,y_1,y_2,y_3]& =\frac{[y_0,y_1,y_3]-[y_0,y_1,y_2]}{x_3-x_2}\\ [y_0,y_1,\dots ,y_n]& =\frac{[y_0,\dots ,y_{n-2},y_n]-[y_0,y_1,\dots ,y_{n-1}]}{x_n-x_{n-1}}\\ \end{array}$

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

$\begin{array}{ccccc}{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{array}$

牛頓插值法

《自然哲學的數學原理》的第三編“宇宙體系”的引理五的图例。這裡在橫坐標上有6個點H,I,K,L,M,N，對應著6個值A,B,C,D,E,F，生成一個多項式函數對這6個點上有對應的6個值，計算任意點S對應的值R。牛頓給出了間距為單位值和任意值的兩種情況。

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

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

$\begin{array}{cc}{N}_n(x)& =y_0+(x-x_0)([y_0,y_1]+(x-x_1)([y_0,y_1,y_2]+\cdots ))\\ & =[y_0]+[y_0,y_1](x-x_0)+\cdots +[y_0,y_1,\dots ,y_n]\prod _{k=0}^{n-1}(x-x_k)\end{array}$

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

對均差採用展開形式：

$\begin{array}{cc}{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\ne j}^n(x_j-x_k)}\\ \end{array}$

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

$\begin{array}{cc}{N}_2(x)& =y_0(1+\frac{x-x_0}{x_0-x_1}+\frac{(x-x_0)(x-x_1)}{(x_0-x_1)(x_0-x_2)})+y_1(\frac{x-x_0}{x_1-x_0}+\frac{(x-x_0)(x-x_1)}{(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)}\\ & =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{array}{c}k=0\\ k\ne j\end{array}}^2\frac{x-x_k}{x_j-x_k}\\ \end{array}$

前向差分

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

定義

給定n+1個數據點

$(x_0,y_0),\dots ,(x_n,y_n)$

有著

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

定義前向差分為：

$\begin{array}{cc}{\mathrm{△}}^0{y}_i& =y_i\\ {\mathrm{△}}^k{y}_i& ={\mathrm{△}}^{k-1}{y}_{i+1}-{\mathrm{△}}^{k-1}{y}_i,1\le k\le n-i\\ \end{array}$

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

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

例子

$\begin{array}{cccc}{y}_0& & & \\ & \mathrm{△}{y}_0& & \\ y_1& & {\mathrm{△}}^2{y}_0& \\ & \mathrm{△}{y}_1& & {\mathrm{△}}^3{y}_0\\ y_2& & {\mathrm{△}}^2{y}_1& \\ & \mathrm{△}{y}_2& & \\ y_3& & & \end{array}$

展開形式

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

$\begin{array}{cc}{\mathrm{△}}^k{y}_i& =\sum _{j=0}^k(-1{)}^{k-j}(\genfrac{}{}{0ex}{}{k}{j})y_{i+j},0\le k\le n-i\end{array}$

這裡的表達式

$(\genfrac{}{}{0ex}{}{n}{k})=\frac{(n{)}_k}{k!}(n{)}_k=n(n-1)(n-2)\cdots (n-k+1)$

是二項式係數，其中的(n)_k是“下降階乘冪”，空積(n)₀被定義為1。

插值公式

其對應的牛頓插值公式為：

$\begin{array}{cc}f(x)& =y_0+\frac{x-x_0}{h}({\mathrm{\Delta }}^1{y}_0+\frac{x-x_0-h}{2h}({\mathrm{\Delta }}^2{y}_0+\cdots ))\\ & =y_0+\sum _{k=1}^n\frac{{\mathrm{\Delta }}^k{y}_0}{k!h^k}\prod _{i=0}^{n-1}(x-x_0-ih)\\ & =y_0+\sum _{k=1}^n\frac{{\mathrm{\Delta }}^k{y}_0}{k!}\prod _{i=0}^{n-1}(\frac{x-x_0}{h}-i)\\ & =\sum _{k=0}^n(\genfrac{}{}{0ex}{}{\frac{x-x_0}{h}}{k}){\mathrm{\Delta }}^k{y}_0\\ \end{array}$

無窮級數

牛頓在1665年得出並在1671年寫的《流數法》中發表了ln(1+x)的無窮級數，在1666年得出了arcsin(x)和arctan(x)的無窮級數，在1669年的《分析學》中發表了sin(x)、cos(x)、arcsin(x)和e^x的無窮級數；萊布尼茨在1673年大概也得出了sin(x)、cos(x)和arctan(x)的無窮級數。布魯克·泰勒在1715年著作《Methodus Incrementorum Directa et Inversa》中研討了“有限差分”方法，其中論述了他在1712年得出的泰勒定理，這個成果此前詹姆斯·格雷果里在1670年和萊布尼茨在1673年已經得出，而約翰·伯努利在1694年已經在《教師學報》發表。

他對牛頓的均差的步長取趨於0的極限，得出：

$\begin{array}{cc}f(x)& =f(a)+\underset{h\to 0}{\lim }\sum _{k=1}^{\mathrm{\infty }}\frac{{\mathrm{\Delta }}_h^k[f](a)}{k!h^k}\prod _{i=0}^{k-1}((x-a)-ih)\\ & =f(a)+\sum _{k=1}^{\mathrm{\infty }}\frac{d^k}{d{x}^k}f(a)\frac{(x-a{)}^k}{k!}\\ \end{array}$

冪函數的均差

使用普通函數記號表示冪运算，$p_n(x)=x^n$，有：

$\begin{array}{cc}{p}_j[x_0,\dots ,x_n]& =0\mathrm{\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{array}{c}\prod _{t=0}^n{x}_t^{k_t}\end{array}\\ \end{array}$

此中n+1元m次齊次多項式的記法同於多項式定理。

泰勒形式

泰勒級數和任何其他的函數級數，在原理上都可以用來逼近均差。將泰勒級數表示為:

$f=f(0)p_0+f^{\prime }(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^{\prime }(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!}$

依據Template:Le，這也是均差的最簡單逼近。

皮亞諾形式

均差還可以表達為

$f[x_0,\dots ,x_n]=\frac{1}{n!}\underset{x_0}{\overset{x_n}{\int }}{f}^{(n)}(t)B_{n-1}(t)dt$

這裡的B_n-1是數據點x₀,...,x_n的n-1次B樣條，而f⁽ⁿ⁾是函數f的n階導數。這叫做均差的皮亞諾形式，而B_n-1是均差的皮亞諾核。

参考书目

• Template:Cite book
• Template:Cite book
• Template:Cite book

參見

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