解密卡尔曼滤波(Kalman Filter)算法:深入解析卡尔曼滤波算法原理与在线可视化实例
从记忆到洞察:轻松掌握泰勒展开式(Taylor Series)的记忆技巧
By Long Luo
在数学、物理学、工程和计算机领域中,泰勒公式[1] 是一种广泛使用的分析方法,用来计算函数的近似值。在实践中,很多函数非常复杂,而且某些函数是不可积的,想求其某点的值,直接求无法实现。
泰勒公式可以将复杂的函数近似地表达为简单的多项式函数,用一个多项式函数去逼近一个给定的函数(即尽量使多项式函数图像拟合给定的函数图像)。注意在逼近的时候一定是从函数图像上的某个点展开。
下图所示就是不同项数的泰勒公式对 sinx 的逼近:
泰勒级数的定义为:
f(x)=n=0∑∞n!f(n)(a)(x−a)n=f(a)+1!f′(a)(x−a)+2!f′′(a)(x−a)2+3!f′′′(a)(x−a)3+⋯
这里,n! 表示 n 的阶乘,而 f(n)(a) 表示函数 f 在点 a 处的 n 阶导数。如果 a=0 ,这个级数也被称为麦克劳林级数(Maclaurin series)[2] 。
泰勒展开式有很多,那么如何记忆呢?首先我们需要明白,泰勒公式之间都是有相互关联的,我们可以通过推导来理解性记忆这些公式。泰勒公式的具体推导过程可以参考数学分析教材或者网络[3] 。
下面我们就推导这些公式,以便更好的记忆[4] !
几何级数 Geometric series
对于 −1<x<1 的情况,几何级数[5] 由等比数列求和公式可得:
1−x1=n=0∑∞xn=1+x+x2+⋯+xn
用 −x 代入 x 上式,则:
1+x1=n=0∑∞(−1)nxn=1−x+x2−x3+⋯+(−1)nxn
用 x2 替代 x , 由于 arctanx=∫0x1+x21dx ,对于 −1≤x≤1,x=±i ,
arctanx=n=0∑∞2n+1(−1)nx2n+1=x−3x3+5x5−⋯+2n+1(−1)nx2n+1
因为 (1−x)21=(1−x1)′ ,则:
(1−x)21=n=1∑∞nxn−1=1+2x+3x2+⋯+nxn−1
同 (1−x)31=21((1−x)21)′ ,则有:
(1−x)31=n=2∑∞2n(n−1)xn−2
指数函数 Exponent function
由于 dxdex=ex ,e0=1 那么:
ex=n=0∑∞n!xn=1+x+2!x2+3!x3+⋯+n!xn
很明显:
(ex)′ex=(0!1+1!x+2!x2+3!x3+⋯)′=0+1+1x+2!x2+3!x3⋯=1+x+2!x2+3!x3+⋯
对于普通指数函数 ax , 由于 ax=exlna ,如果将 x 换为 xlna ,那么 ax 的泰勒展开式:
ax=exlna=1+xlna+2!(xlna)2+3!(xlna)3+⋯+n!(xlna)n
哪个更大呢? 2^100! 还是 (2^100)! ?
By Long Luo
昨天在B站看到一个数学视频[1],比较 2100! 和 2100! 的大小。直观感受就是这2个数都非常非常大,但哪个更大无法一眼看出来。
虽然指数爆炸,但阶乘实际上增长的速度比指数更快,如下图1所示:
可以看出阶乘图像 y=x! 实际上比指数 y=ex 要快很多,而 y=xx 是最快的。
但具体哪个更大呢?
这个问题有很多种方法,这里展示了4种方法。
对数放缩法 (Zoom)
由于对数[2] 函数 y=logab 当 a>1 是单调递增函数,所以比较两个数大小时,可以通过比较两者对数值来实现大小比较。
两边同取对数 log2x ,
左边:
A=log2(2100!)=100!
右边:
B=log22100!=log22100+log2(2100−1)+⋯+1+0
共有 2100 项,值从 0 到 log22100=100 ,所以
B<100⋅2100<128⋅2100=27⋅2100=2107
综合上式,我们只需要比较 100! 和 2107 的大小即可。
100! 至少有 (100−64+1)=37 项是大于等于 64=26 ,也就是 (26)37=2222 。
显然可得 100!≫2222≫2107 。
故有虽然两个数都非常大,但 2100! 仍然远远大于 2100! 。
斯特林公式 (Stirling’s Approximation)
由于存在阶乘,我们可以使用斯特林公式(Stirling’s Approximation)[3] 来估计。
n!∼2πn(en)n=2πn2n+1e−n
两边同取对数:
lnn!∼21ln(2π)+(n+21)ln(n)−n
根据上式,可见 n 足够大时,斯特林公式可以近似为:
ln(n!)∼n(ln(n)−1)
则有:
A=ln(2100!)=100!ln(2)B=ln(2100!)∼2100(ln(2100)−1)=2100(100ln(2)−1)
由于 210=1024≈103 ,则有 2100≈1030 , 那么 B≈1032ln(2) 。
很明显 100!≫1032 ,因此
2100!≫2100!
Google编程竞赛题:计算 (3 + √5)^n 的整数部分末三位数
By Long Luo
袁哥在微博上发布了一道 数学挑战题 :
计算 (3+5)n 的整数末三位数,给出能口算或者可以用计算器计算的算法的第一个人,免费给一个价值 1000 元的 A9 投资分享群入群名额。
最开始看到这道题目时,我觉得很简单啊,于是给出了下面的解答:
令 y=(3+5)n ,两边同取对数,log10y=nlog10(3+5) , y=10nlog105.23607 ,lg5≈0.7 ,所以 y≈100.7n 。
但问题没有这么简单,因为上述解答只在 n=1 是正确的,n=2 , y=101.4=25 就不对了,因为精度不够!
之外,根据评论中其他人给的思路,分析得出这个是周期性的,所以又提交了下面的答案:
但问题仍然没有这么简单,因为即使循环周期 k=100 , log10(3+5) 取的位数再多仍然会出现精度不够的问题。
袁哥的题解省略了很多东西,很多人可能看不太明白。我重新写了题解,重新整理了思路及缺失的步骤,外加证明,有高一数学水平即可看懂。
后来通过搜索,发现这道题是 Google CodeJam[1] 编程竞赛题,原题如下: