离散微积分
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
--------------------------------------------------------------------------------------
好久没更博客了...
趁这几天放假没什么事写点科普系列造福一下大众好了...
虽然好像没什么人看...
罢了罢了,有人看就看,没人看就算了吧,就当我自己复习一遍了
--------------------------------------------------------------------------------------
这次要写的是离散微积分(又叫有限微积分)
微积分大家都很熟悉了(毕竟小学就学过)
但是这玩意儿还能放到离散意义下?
当然
离散微积分在离散求和方面很有用(可以用来花式求和)
另外我自己对有些概念记得也不太清了(毕竟我现在也不太常用),如果觉得有不正确或者不严谨的地方又不愿意当做没有看见就指出来吧
--------------------------------------------------------------------------------------
首先介绍离散意义下的求导、微分和积分运算,以下介绍的运算都是对整数域上有定义的函数适用(当然,如果定义域不包含整数集,但是在关注的区间内的所有整数上都有定义,那么也可以(相当于微积分中的"连续"),另外,离散意义下只要连续就可导,具体为什么一会儿再说)
离散意义下的微分(求导):
大家都知道导数就是函数的微分除以自变量的微分
而离散意义下,自变量的微分就是$1$(这是一个无穷小等于$1$的世界)
因此求导和微分其实是一样的,这里叫做差分(又叫离散微分)
定义差分算子$\Delta$:
$\Delta f(x)=f(x+1)-f(x)$
嘿嘿,由定义可见可以差分唯一的条件就是在离散意义下连续~
离散意义下的积分:
大家都知道积分有定积分和不定积分
这里只说定积分,不定积分的话把定积分的范围去掉就可以了
离散意义下的定积分定义为$[a,b)$区间上的求和:
$\sum_{a}^{b}f(x)\delta x = \sum_{x=a}^{b-1}f(x)$
积分的符号是$\sum$,咦咦怎么和求和的符号一样?(一脸茫然)
这里的$\delta x$对应于微积分中的$dx$,表示对$x$积分
这些就是定义,接下来说一下离散意义下的微积分基本定理,他和微积分中的基本一样:
若$f = \Delta g$
那么$\sum_{a}^{b}f(x)\delta x = g|_{a}^{b} = g(b)-g(a)$
这个的证明简直容易爆了..
就算没学过微积分也应该会证
那么问题来了,怎么求差分呢?
显然基本上只能根据定义来求,但是我们可以搞一些公式出来让大家背,以减少使用的时候推导所花的时间(空间换时间)
首先是幂函数$x^k$的差分,我们知道他的导数是$kx^{k-1}$,简直炒鸡容易记住,那么差分是不是也有类似的简单的公式呢?
很可惜,没有...
但是$x^{\underline{k}}$是有的
$\Delta x^{\underline{k}} $
$= (x+1)^{\underline{k}}-x^{\underline{k}} $
$= (x+1-(x-k+1))x^{\underline{k-1}} $
$= kx^{\underline{k-1}}$
真是一颗赛艇,看起来下降幂取代了通常的幂的地位
($x^{\underline{k}}$表示$x$的$k$次下降幂,
当$k \gt 0$时,$x^{\underline{k}}=\prod_{i=x-k+1}^{x}i$,
当$k=0$时,$x^{\underline{k}}=1$,
当$k \lt 0$时,$x^{\underline{k}}=(\prod_{i=x+1}^{x+m}i)^{-1}$)
那幂级数怎么办呢?
不虚,使用第二类斯特数,可以在幂级数和下降幂之间转换:
设$\{_{b}^{a}\}$表示第二类斯特林数(把一个大小为$a$的集合划分成$b$个非空子集的方案数),那么就有:$x^{k} = \sum_{i=0}^{k}\{_{b}^{a}\}x^{\underline{i}}$
于是幂级数的差分我们也会求了w
(实际上如果$f$可以由$g$线性表示,那么$f$的差分也可以由$g$的差分线性表示,至于为什么一会儿就知道了)
指数函数又怎么样呢?
简单得很
$\Delta k^{x} = k^{x+1}-k^{x} = (k-1)k^{x}$
而且有一个一颗赛艇的事实是,$\Delta 2^{x} = 2^{x}$,也就是离散微积分中的$2$和微积分中的$e$在这一点上很相似,而$2$正好等于$\lfloor e \rfloor$,这是巧合吗?
其他的差分公式你们自己去推吧 _(:3 」∠)_
另外,在微积分中常用的导数和积分的一些性质,离散意义下基本也满足
比如:
$\Delta(f(x)+g(x)) $
$= f(x+1)+g(x+1)-f(x)-g(x) $
$= \Delta(f(x)) + \Delta(g(x))$
两边求和就得到了这个定理的积分版本
那么分部积分法还适不适用呢?
为了方便,我们先定义一个位移算子$E$:$Ef(x)=f(x+1)$
$\Delta(f(x)*g(x)) $
$= f(x+1)g(x+1)-f(x)g(x) $
$= (f(x+1)-f(x))g(x+1)+(g(x+1)-g(x))f(x)$
$= \Delta f(x)Eg(x) + \Delta g(x)f(x)$
同样两边求和得到积分版本
我们可以发现他和微积分中的分部积分法很像,只是多了一个位移算子$E$
我们还缺些什么呢?
啊,泰勒展开
离散意义下有泰勒展开吗?
当然:
定义$n$阶差分:$\Delta^{n} f = \Delta(\Delta^{n-1}f)$,特殊地,$\Delta ^{0}f = f$
熟悉差分表那一套理论的同学都知道:
对于$k$阶多项式$f$:
$f(n) $
$= \sum_{i=0}^{k}\Delta^{i}f(0)*(_{i}^{n})$
$= \sum_{i=0}^{k}\Delta^{i}f(0)*\frac{n!}{i!(n-i)!}$
$= \sum_{i=0}^{k}\Delta^{i}f(0)*\frac{n^{\underline{i}}}{i!}$
有没有发现这个和麦克劳林公式很像!!!只是把$n^{i}$改成了$n^{\underline{i}}$!!
都已经得到麦克劳林展开的离散版本了,要得到泰勒展开的离散版本就不难了:
设$g(x)=f(x+a)$
那么就有$f(n+a) = g(n)$
$= \sum_{i=0}^{k}\Delta^{i}g(0)*\frac{n^{\underline{i}}}{i!}$
$= \sum_{i=0}^{k}\Delta^{i}f(a)*\frac{((n+a)-a)^{\underline{i}}}{i!}$
这就是离散意义下的泰勒展开了
--------------------------------------------------------------------------------------
感觉介绍得也差不多了,来看几道例题好了...
(1)求$\sum_{i=1}^{n}i^{\underline{k}}$的封闭形式
不用离散微积分的话,大概可以用斯特林数转成幂级数然后二项式反演搞一搞?
用了离散积分之后就简单多了,一眼秒:
解:原式$= \sum_{1}^{n+1}x^{\underline{k}}\delta x=\frac{x^{\underline{k+1}}}{k+1}|_{1}^{n+1}$
(2)求$\sum_{i=1}^{n}k^{i}$
解:原式$= \sum_{1}^{n+1}k^{x}\delta x = \frac{k^{x}}{k-1}|_{1}^{n+1}$
(3)求证:$f(n)=\sum_{i=0}^{n}i^x$是一个$n+1$次多项式
证明:因为$i^x$是一个关于i的$x$次多项式,因此:
$i^x = \sum_{j=0}^{k}c_{j}*(_{j}^{x})$
其中$c_{j} = \Delta^{j}i^0$
因此$f(n) = \sum_{i=0}^{n}\sum_{j=0}^{i}c_j*(^{i}_{j})$
$= \sum_{j=0}^{n}c_j\sum_{i=j}^{n}(^{i}_{j})$
$= \sum_{j=0}^{n}c_j\sum_{i=0}^{n}(^{i}_{j})$
$= \sum_{j=0}^{n}c_j(^{n+1}_{j+1})$
$= \sum_{j=1}^{n+1}c_{j-1}(^{n+1}_{j})$
$= \sum_{j=0}^{n+1}c_{j}^{'}(^{n+1}_{j})$
其中$c_{j}^{'} = c_{j-1},c_{0}^{'}=0$
令$c_{j}^{'} = \Delta^{i}f(0)$,不难构造出一个$(n+1)$次多项式$f$,使得$f(n)=\sum_{i=0}^{n}i^x$
--------------------------------------------------------------------------------------
2016年6月13日 20:25
大爷好强orz