差分
差分，又名差分函数或差分运算，一般是指有限差分（英语：Finite difference），是数学中的一个概念，将原函数 <math>f(x)</math> 映射到 <math>f(x+a)-f(x+b)</math>。差分运算，相应于微分运算，是微积分中重要的一个概念。
| 系列条目 |
| 微积分学 |
|---|
| File:Fundamental Theorem of Calculus.svg |
定义[编辑]
差分分为前向差分和逆向差分。
前向差分[编辑]
函数的前向差分通常简称为函数的差分。对于函数<math>\ f(x)</math>，如果在等距节点：
- <math>x_k = x_0 + kh, (k = 0,1,...,n)</math>
- <math>\ \Delta f(x_k)=f(x_{k+1})-f(x_k)</math>
则称<math>\ \Delta f(x)</math>，函数在每个小区间上的增量<math>y_{k+1} - y_k</math>为<math>\ f(x)</math>一阶差分。[1]
在微积分学中的有限差分（finite differences），前向差分通常是微分在离散的函数中的等效运算。差分方程的解法也与微分方程的解法相似。当<math>\ f(x)</math>是多项式时，前向差分为Delta算子（称<math>\Delta</math>为差分算子[2]），一种线性算子。前向差分会将多项式阶数降低 1。
逆向差分[编辑]
对于函数<math>\ f(x_k)</math>，如果：
- <math>\ \nabla f(x_k)=f(x_k)-f(x_{k-1}).\,</math>
则称<math>\ \nabla f(x_k)</math>为<math>\ f(x)</math>的一阶逆向差分。
差分的阶[编辑]
一阶差分的差分为二阶差分，二阶差分的差分为三阶差分，其余类推。记：
<math>\ \Delta^n [f](x)</math>为<math>\ f(x)</math>的<math>\ n</math>阶差分。
如果
<math>\ \Delta^n [f](x) </math> <math>\ = \Delta \{ \Delta^{n-1} [f](x) \} </math> <math>\ = \Delta^{n-1} [f](x+1) - \Delta^{n-1} [f](x)</math>
根据数学归纳法，有
- <math>\ \Delta^n [f](x) = \sum_{i=0}^n {n \choose i} (-1)^{n-i} f(x+i)</math>
其中，<math>\ {n \choose i}</math>为二项式系数。
特别的，有
- <math>\ \Delta^2 [f](x) = f(x+2) - 2f(x+1) + f(x) </math>
差分的性质[编辑]
- 如果C为常数，则有
- <math>\Delta C=0</math>
- 线性：如果 <math>\ a</math> 和 <math>\ b</math> 为常数，则有
- <math>\Delta (af+bg) = a \Delta f + b \Delta g </math>
- 乘法定则(此处步长<math>h\equiv1</math>)：
- <math>\Delta (fg) = f \Delta g + g \Delta f + \Delta f \Delta g </math>
- <math>\nabla (f g) = f \nabla g + g \nabla f - \nabla f \nabla g </math>
- 除法定则：
- <math>\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} </math>
- <math>\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} </math>
- 或
- <math>\nabla\left( \frac{f}{g} \right)= \frac {g \nabla f - f \nabla g}{g \cdot (g - \nabla g)}</math>
- <math>\Delta\left( \frac{f}{g} \right)= \frac {g \Delta f - f \Delta g}{g \cdot (g + \Delta g)}</math>
- 级数：
- <math>\sum_{n=a}^{b} \Delta f(n) = f(b+1)-f(a)</math>
- <math>\sum_{n=a}^{b} \nabla f(n) = f(b)-f(a-1)</math>
牛顿级数[编辑]
牛顿插值公式也叫做牛顿级数，由“牛顿前向差分方程”的项组成，得名于伊萨克·牛顿爵士，最早发表为他在1687年出版的《自然哲学的数学原理》中第三编“宇宙体系”的引理五[3]，此前詹姆斯·格雷果里于1670年和牛顿于1676年已经分别独立得出这个成果。一般称其为连续泰勒展开的离散对应。
单位步长情况[编辑]
当<math>x</math>值间隔为单位步长<math>1</math>时，有：
- <math>\begin{align}
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{align} </math> 这成立于任何多项式函数和大多数但非全部解析函数。这里的表达式
- <math>{x \choose k} = \frac{(x)_k}{k!} \quad\quad (x)_k=x(x-1)(x-2)\cdots(x-k+1)</math>
是二项式系数，其中的<math>(x)_k</math>是“下降阶乘幂”(另一种常见的标记法为<math>x^\underline{k}</math>)，空积<math>(x)_0</math>被定义为<math>1</math>。这里的<math>\Delta_k\left[f\right](x)</math>是“前向差分”的特定情况，即间距<math>h=1</math>。
实例[编辑]
为了展示牛顿的这个公式是如何使用的，举例数列 1, 4, 9,16...的前几项，可以找到一个多项式重新生成这些值，首先计算一个差分表，接着将对应于x0（标示了下划线）的这些差分代换入公式，
- <math>
\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{align} 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{align} \end{matrix} </math>
一般情况[编辑]
对于x值间隔为非一致步长的情况，牛顿计算均差，在间隔一致但非单位量时，即上述前向差分的一般情况，插值公式为：
- <math>
\begin{align} 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{align} </math> 在最终公式中hk被消去掉了，对于非一致步长的情况则不会出现阶乘。
参考[编辑]
- ^ 科学出版社 《数值分析及科学计算》 薛毅（编） 第六章 第2节 Newton插值. P204.
- ^ 科学出版社 《数值分析及科学计算》 薛毅（编） 第六章 第2节 Newton插值. P205.
- ^ Newton, Isaac, (1687). Principia, Book III, Lemma V, Case 1
参见[编辑]
参考文献[编辑]
- 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[永久失效链接].