有限差分

**差分**，又名**差分函數**或**差分運算**，一般是指**有限差分**（英語：Finite difference），是數學中的一個概念，將原函數 $f(x)$ 映射到 $f(x+a)-f(x+b)$ 。差分運算，相應於微分運算，是微積分中重要的一個概念。

## 定義

差分分為**前向差分**和**逆向差分**。

### 前向差分

函數的前向差分通常簡稱為函數的差分。對於函數 $\ f(x)$ ，如果在等距節點：

　
: $x_{k}=x_{0}+kh,(k=0,1,...,n)$

　
: $\ \Delta f(x_{k})=f(x_{k+1})-f(x_{k})$

則稱 $\ \Delta f(x)$ ，函數在每個小區間上的增量 $y_{k+1}-y_{k}$ 為 $\ f(x)$ 一階差分。

在微積分學中的有限差分（finite differences），前向差分通常是微分在離散的函數中的等效運算。差分方程式的解法也與微分方程式的解法相似。當 $\ f(x)$ 是多項式時，前向差分為 Delta 算子（稱 $\Delta $ 為差分算子），一種線性算子。前向差分會將多項式階數降低 1。

### 逆向差分

對於函數 $\ f(x_{k})$ ，如果：

　
: $\ \nabla f(x_{k})=f(x_{k})-f(x_{k-1}).\,$

則稱 $\ \nabla f(x_{k})$ 為 $\ f(x)$ 的一階逆向差分。

## 差分的階

**一階差分**的差分為**二階差分**，二階差分的差分為三階差分，其餘類推。記：

 $\ \Delta ^{n}[f](x)$ 為 $\ f(x)$ 的 $\ n$ 階差分。

如果

　
:

根據數學歸納法，有

　
: $\ \Delta ^{n}[f](x)=\sum _{i=0}^{n}{n \choose i}(-1)^{n-i}f(x+i)$

其中， $\ {n \choose i}$ 為二項式係數。

特別的，有

　
: $\ \Delta ^{2}[f](x)=f(x+2)-2f(x+1)+f(x)$

前向差分有時候也稱作數列的二項式轉換

## 差分的性質

對比解析函數中的微分的屬性，差分的性質有：

* 如果 C 為常數，則有

　
: : $\Delta C=0$

* 線性：如果 $\ a$ 和 $\ b$ 為常數，則有

　
: : $\Delta (af+bg)=a\Delta f+b\Delta g$

* 乘法定則：

　
: : $\Delta (fg)=f\Delta g+g\Delta f+\Delta f\Delta g$

　
: $\nabla (fg)=f\nabla g+g\nabla f-\nabla f\nabla g$

* 除法定則：

　
: : $\nabla \left({\frac {f}{g}}\right)={\frac {1}{g}}\det {\begin{bmatrix}\nabla f&\nabla g\\f&g\end{bmatrix}}\det {\begin{bmatrix}g&\nabla g\\1&1\end{bmatrix}}^{-1}$

　
: $\Delta \left({\dfrac {f}{g}}\right)={\dfrac {1}{g}}\det {\begin{bmatrix}\Delta f&\Delta g\\f&g\end{bmatrix}}\det {\begin{bmatrix}g&\Delta g\\-1&1\end{bmatrix}}^{-1}$

　
: 或

　
: $\nabla \left({\frac {f}{g}}\right)={\frac {g\nabla f-f\nabla g}{g\cdot (g-\nabla g)}}$

　
: $\Delta \left({\frac {f}{g}}\right)={\frac {g\Delta f-f\Delta g}{g\cdot (g+\Delta g)}}$

* 級數：

　
: : $\sum _{n=a}^{b}\Delta f(n)=f(b+1)-f(a)$

　
: $\sum _{n=a}^{b}\nabla f(n)=f(b)-f(a-1)$

## 牛頓級數

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

### 單位步長情況

當 $x$ 值間隔為單位步長 $1$ 時，有：

　
: ${\begin{aligned}f(x)&=f(a)+{\frac {x-a}{1}}\left[\Delta ^{1}[f](a)+{\frac {x-a-1}{2}}\left(\Delta ^{2}[f](a)+\cdots \right)\right]\\&=f(a)+\sum _{k=1}^{n}\Delta ^{k}[f](a)\prod _{i=1}^{k}{\frac {[(x-a)-i+1]}{i}}\\&=\sum _{k=0}^{n}{x-a \choose k}~\Delta ^{k}[f](a)\\\end{aligned}}$

這成立於任何多項式函數和大多數但非全部解析函數。這裡的表達式

　
: ${x \choose k}={\frac {(x)_{k}}{k!}}\quad \quad (x)_{k}=x(x-1)(x-2)\cdots (x-k+1)$

是二項式係數，其中的 $(x)_{k}$ 是「下降階乘冪」(另一種常見的標記法為 $x^{\underline {k}}$ )，空積 $(x)_{0}$ 被定義為 $1$ 。這裡的 $\Delta _{k}\left[f\right](x)$ 是「前向差分」的特定情況，即間距 $h=1$ 。

### 實例

為了展示牛頓的這個公式是如何使用的，舉例數列 1, 4, 9,16... 的前幾項，可以找到一個多項式重新生成這些值，首先計算一個差分表，接著將對應於 x0（標示了下劃線）的這些差分代換入公式，

　
: ${\begin{matrix}{\begin{array}{|c||c|c|c|c|}\hline x&\Delta ^{0}&\Delta ^{1}&\Delta ^{2}&\Delta ^{3}\\\hline 1&{\underline {1}}&&&\\&&{\underline {3}}&&\\2&4&&{\underline {2}}&\\&&5&&{\underline {0}}\\3&9&&2&\\&&7&&\\4&16&&&\\\hline \end{array}}&\quad {\begin{aligned}f(x)&=\Delta ^{0}+\Delta ^{1}{\dfrac {(x-x_{0})}{1!}}+\Delta ^{2}{\dfrac {(x-x_{0})(x-x_{0}-1)}{2!}}\quad (x_{0}=1)\\&=1+3\cdot {\dfrac {x-1}{1}}+2\cdot {\dfrac {(x-1)(x-2)}{2}}\\&=1+3(x-1)+(x-1)(x-2)\\&=x^{2}\end{aligned}}\end{matrix}}$

### 一般情況

對於 x 值間隔為非一致步長的情況，牛頓計算均差，在間隔一致但非單位量時，即上述前向差分的一般情況，插值公式為：

　
: ${\begin{aligned}f(x)&=f(a)+{\frac {x-a}{h}}\left[\Delta _{h}^{1}[f](a)+{\frac {x-a-h}{2h}}\left(\Delta _{h}^{2}[f](a)+\cdots \right)\right]\\&=f(a)+\sum _{k=1}^{n}{\frac {\Delta _{h}^{k}[f](a)}{k!h^{k}}}\prod _{i=0}^{k-1}[(x-a)-ih]\\&=f(a)+\sum _{k=1}^{n}{\frac {\Delta _{h}^{k}[f](a)}{k!}}\prod _{i=0}^{k-1}\left({\frac {x-a}{h}}-i\right)\end{aligned}}$

在最終公式中 hk 被消去掉了，對於非一致步長的情況則不會出現階乘。

## 參考

## 參見

* 遞迴
* 招差術
* 遞迴關係式
* 拉格朗日多項式
* 吉爾布雷斯猜想
* 牛頓多項式
* 牛頓級數表
* 泰勒級數
* 時標微積分
* 分部求和法

## 參考文獻

* Flajolet, Philippe; Sedgewick, Robert, Mellin transforms and asymptotics: Finite differences and Rice's integrals, Theoretical Computer Science, 1995, **144** (1–2): 101–124, doi:10.1016/0304-3975(94)00281-M .