差分与有限微积分

阅读这篇文章需要微积分基础。
从《具体数学》上看来的,感觉十分有用。
为了思维的连贯性,省略了大量细节。这些细节将在最后补充。

差分算子

首先,有一个关于“算子”的定义:

如果一个运算作用在函数上,则我们称这个运算为“算子”。

显然,多项式的卷积、狄利克雷卷积等都是算子。
在迈入高等数学的大门时,我们遇到过一个强劲的算子:微分算子

微分算子$\text D$是这样定义的:$\text Df(x) = \displaystyle \lim _{h \to 0}\frac{f(x + h)-f(x)}{h}$.它的几何意义是,对于某个$x$,以 ($x$加上无穷小) 处的函数值减去$x$的函数值。
因此,$\text Df(x)$就是$f(x)$的导函数。

由于微分算子使用了无穷小,所以微分算子用于连续数学。但是对于别的函数——它们只能在整数范围内取值,微分算子就无法通用。

面对离散数学,定义差分算子$\Delta$$\displaystyle \Delta f(x)= f(x+1)-f(x)$.

它的几何意义如图:
差分

容易看出,差分算子给出相邻的整数之间函数值的差。

有限微积分

众所周知,微分里有一个很妙的公式:$\text D(x^m)=m\cdot x^{m-1}$.
差分有没有类似的公式呢?

来考虑下降阶乘幂:$x^{\underline m} = x \cdot (x-1) \cdot (x-2)\cdots (x-m+1)$.
手推一番,我们发现$\Delta(x^{\underline m})=m\cdot x^{\underline {m-1}}$.
惊喜的是,差分的运算法则和微分的运算法则如出一辙。例如$\text Df(x)+\text Dg(x)=\text D(f(x)+g(x))$之类的导数运算,都可以直接套在差分上

有什么用?

牛顿-莱布尼茨公式:若$g(x)=\text Df(x)$,则有$\displaystyle \int _a ^b g(x) = f(b) - f(a)$. 类似积分,可以构造出和式:

首先,我们令$\textstyle \sum _a^bf(x)=\displaystyle \sum_{i=a}^{b-1}f(x)$.注意两个$\Sigma$之间的区别。

那么有基本定理:

如果$g(x)=\Delta f(x)$,则有$\textstyle \sum_a^b g(x) = f(b)-f(a)$.

如何理解这个公式?举个例子。假设我们找到了$g(x)=\Delta f(x)$,那么我们可以快速求:
$\displaystyle \sum_{i=1}^{n} g(x) =\textstyle \sum_{1}^{n+1}g(x)=f(n+1)-f(1)$.

回到之前讨论的下降阶乘幂。我们有$\Delta(x^{\underline m})=m\cdot x^{\underline {m-1}}$.
所以实践中,可以直接用下降阶乘幂来解决问题。

例子

$\displaystyle \sum_{i=0}^{100}x^2$.

首先,我们把$x^2$表示成下降阶乘幂的形式。稍加计算得到:$g(x)=x^2=x(x-1)+x=x^{\underline 2}+x^{\underline 1}$.

然后构造$g(x)$的原函数:$f(x)=\frac{1}{3}x^{\underline 3}+\frac{1}{2}x^{\underline 2}=\frac{x(x-1)(x-2)}{3}+\frac{x(x-1)}{2}$.

于是有:$\displaystyle \sum_{i=0}^{100}x^2 = \textstyle \sum^{101}_0g(x)=f(101)-f(0)=\frac{101\cdot 100 \cdot 99}{3}+\frac{101 \cdot 100}{2} =338350$.

这就是有限微积分

一个例题

$1^k + 2^k + 3^k \cdots + n^k$.

$n<1000 , k<1000$
暴力。

$n<100000,k<1000000$
快速幂。

$n<10^8 , k<10$
先写个程序推出$x^k$的下降阶乘幂形式,然后用有限微积分$O(1)$做。

$n<10^8 , k<1000$
从有限微积分中可以知道,答案一定是一个$k+1$阶多项式。

故先$O(n \log k)$求出$n=1 ,2,3\cdots k+1$时的答案,然后$O(k^2)$插值回多项式(拉格朗日插值法),然后$O(k)$计算答案(霍纳法则)。
总复杂度$O(k^2)$.

$n<=10^8 , k<10^5$
orz Gromah.

几个细节

差分表

原函数$f(x)$ 差分函数$\Delta f(x)$
$x^\underline m$ $m\cdot x^\underline {m-1}$
$2^x$ $2^x$
$c^x$ $(c-1)c^x$

差分运算法则
下面的向量代表函数。

原函数$f(x)$ 差分函数$\Delta f(x)$
$c\cdot \vec u$ $c \cdot \Delta\vec u$
$\vec u + \vec v$ $\Delta \vec u + \Delta \vec v$

序列差分

考虑一个序列的差分: $\{a_1,a_2,a_3\cdots \}\leftrightarrow\{a_2-a_1,a_3-a_2,\cdots\}$
记一阶差分的结果为$\vec b$,对$\vec b$再做一次差分,得到二阶差分:
$\{b_2-b_1,b_3-b_2,\cdots\}$

如果这个初始序列由$f(1),f(2)\cdots$给出,则有:
如果$f(x)$$k$次多项式,那么$\vec a$$k+1$阶差分全部相等,$k+2$阶差分全为$0$.

例如:$f(x)=x^3$

(0, 1, 8, 27, 64, 125)    ->
(1, 7, 19, 37, 61)        ->
(6, 12, 18, 24)           ->
(6, 6, 6)                 ->
(0, 0)

负指数下降幂

定义$x^{-\underline m} , m \in Z_+$为:
$x^{-\underline m} = \frac{1}{(x+1)\cdot (x+2)\cdot (x+3)\cdots}$


CC0协议 @ ruanxingzhi 2017. CC0是啥玩意?
Home apps close