Long Luo's Life Notes

每一天都是奇迹

By Long Luo

PID 算法[1] 是自动控制领域中很重要的算法。

Simple PID Controller

非常简单的 PID 算法在线互动式模拟器,传送门 →

PID Algorithm

之前这个是 PID v1.0 版本,最近重构了代码,增加了一些新功能:

  1. 增加机器人速度 vv 及加速度 aa 显示;
  2. 增加 2 个图表展示 PID X 轴方向及 Y 轴方向的 P、I、D 33 个分量随时间变化显示;
  3. 之前代码将时间及速度固定了,但这不符合实际,增加随 dtdt 变化积分和微分项;

pid_track

阅读全文 »

By Long Luo

在数学、物理学、工程和计算机领域中,泰勒公式[1] 是一种广泛使用的分析方法,用来计算函数的近似值。在实践中,很多函数非常复杂,而且某些函数是不可积的,想求其某点的值,直接求无法实现。

泰勒公式可以将复杂的函数近似地表达为简单的多项式函数,用一个多项式函数去逼近一个给定的函数(即尽量使多项式函数图像拟合给定的函数图像)。注意在逼近的时候一定是从函数图像上的某个点展开。

下图所示就是不同项数的泰勒公式对 sinx\sin x 的逼近:

768px-Sintay

泰勒级数的定义为:

f(x)=n=0f(n)(a)n!(xa)n=f(a)+f(a)1!(xa)+f(a)2!(xa)2+f(a)3!(xa)3+f(x) = \sum _{n=0}^{\infty}{\frac{f^{(n)}(a)}{n!}}(x-a)^{n} = f(a) + {\frac {f'(a)}{1!}}(x - a) + {\frac {f''(a)}{2!}}(x - a)^{2} + {\frac {f'''(a)}{3!}}(x - a)^{3} + \cdots

这里,n!n! 表示 nn 的阶乘,而 f(n)(a)f^{(n)}(a) 表示函数 ff 在点 aa 处的 nn 阶导数。如果 a=0a = 0 ,这个级数也被称为麦克劳林级数(Maclaurin series)[2]

泰勒展开式有很多,那么如何记忆呢?首先我们需要明白,泰勒公式之间都是有相互关联的,我们可以通过推导来理解性记忆这些公式。泰勒公式的具体推导过程可以参考数学分析教材或者网络[3]

下面我们就推导这些公式,以便更好的记忆[4]

几何级数 Geometric series

对于 1<x<1-1 < x < 1 的情况,几何级数[5] 由等比数列求和公式可得:

11x=n=0xn=1+x+x2++xn\frac{1}{1 - x} = \sum _{n=0}^{\infty}x^{n} = 1 + x + x^{2} + \cdots + x^{n}

x-x 代入 xx 上式,则:

11+x=n=0(1)nxn=1x+x2x3++(1)nxn\frac{1}{1 + x} = \sum _{n=0}^{\infty}(-1)^nx^{n} = 1 - x + x^{2} - x^3 + \cdots + (-1)^n x^{n}

x2x^2 替代 xx , 由于 arctanx=0x11+x2dx\arctan x = \int_{0}^{x} \frac{1}{1 + x^2} \mathrm{d}x ,对于 1x1,x±i-1 \le x \le 1, x \neq \pm i

arctanx=n=0(1)n2n+1x2n+1=xx33+x55+(1)n2n+1x2n+1\arctan x = \sum _{n=0}^{\infty }{\frac {(-1)^{n}}{2n + 1}}x^{2n + 1} = x - {\frac {x^3}{3}} + {\frac {x^5}{5}} - \cdots + \frac{(-1)^n}{2n + 1}x^{2n + 1}

因为 1(1x)2=(11x)\frac{1}{(1 - x)^2} = (\frac{1}{1 - x})' ,则:

1(1x)2=n=1nxn1=1+2x+3x2++nxn1\begin{aligned} \frac {1}{(1-x)^2} &= \sum _{n=1}^{\infty }n x^{n-1} \\ &= 1 + 2x + 3x^2 + \cdots + n x^{n-1} \end{aligned}

1(1x)3=12(1(1x)2)\frac{1}{(1 - x)^3} = \frac{1}{2} (\frac{1}{(1 - x)^2})' ,则有:

1(1x)3=n=2n(n1)2xn2\frac {1}{(1 - x)^3} = \sum _{n=2}^{\infty }{\frac {n(n - 1)}{2}}x^{n - 2}

指数函数 Exponent function

由于 dexdx=ex\frac{\mathrm{d} e^x}{\mathrm{d} x} = e^xe0=1e^0 = 1 那么:

ex=n=0xnn!=1+x+x22!+x33!++xnn!e^x = \sum _{n=0}^{\infty }{\frac{x^n}{n!}} = 1 + x + {\frac{x^2}{2!}} + {\frac {x^3}{3!}} + \cdots + {\frac{x^n}{n!}}

很明显:

(ex)=(10!+x1!+x22!+x33!+)ex=0+1+x1+x22!+x33!=1+x+x22!+x33!+\begin{aligned} (e^x)' &= (\frac{1}{0!}+\frac{x}{1!}+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots)' \\ e^x &= 0+1+\frac{x}{1}+\frac{x^2}{2!}+\frac{x^3}{3!}\cdots \\ &= 1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots \end{aligned}

对于普通指数函数 axa^x , 由于 ax=exlnaa^x=e^{x\ln a} ,如果将 xx 换为 xlnax\ln a ,那么 axa^x 的泰勒展开式:

ax=exlna=1+xlna+(xlna)22!+(xlna)33!++(xlna)nn!\begin{aligned} a^x &= e^{x \ln a} \\ &= 1 + x \ln a + \frac{(x \ln a)^2}{2!} + \frac{(x \ln a)^3}{3!} + \cdots + \frac{(x \ln a)^n}{n!} \\ \end{aligned}

阅读全文 »

By Long Luo

昨天在B站看到一个数学视频[1],比较 2100!2^{100!}2100!2^{100}! 的大小。直观感受就是这2个数都非常非常大,但哪个更大无法一眼看出来。

虽然指数爆炸,但阶乘实际上增长的速度比指数更快,如下图1所示:

function graph

可以看出阶乘图像 y=x!y = x! 实际上比指数 y=exy = e^x 要快很多,而 y=xxy = x^x 是最快的。

但具体哪个更大呢?

这个问题有很多种方法,这里展示了4种方法。

对数放缩法 (Zoom)

由于对数[2] 函数 y=logaby = \log_{a}{b}a>1a > 1 是单调递增函数,所以比较两个数大小时,可以通过比较两者对数值来实现大小比较。

两边同取对数 log2x\log_{2}{x}

左边:

A=log2(2100!)=100!A = \log_{2}{(2^{100!})} = 100!

右边:

B=log22100!=log22100+log2(21001)++1+0B = \log_{2}{2^{100}!}= \log_{2}{2^{100}} + \log_{2}{(2^{100} - 1)} + \dots + 1 + 0

共有 21002^{100} 项,值从 00log22100=100\log_{2}{2^{100}} = 100 ,所以

B<1002100<1282100=272100=2107B < 100 \cdot 2^{100} < 128 \cdot 2^{100} = 2^7 \cdot 2^{100} = 2^{107}

综合上式,我们只需要比较 100!100!21072^{107} 的大小即可。

100!100! 至少有 (10064+1)=37(100 - 64 + 1) = 37 项是大于等于 64=2664 = 2^6 ,也就是 (26)37=2222(2^6)^{37}=2^{222}

显然可得 100!22222107100! \gg 2^{222} \gg 2^{107}

故有虽然两个数都非常大,但 2100!2^{100!} 仍然远远大于 2100!2^{100}!

斯特林公式 (Stirling’s Approximation)

由于存在阶乘,我们可以使用斯特林公式(Stirling’s Approximation)[3] 来估计。

n!2πn(ne)n=2πnn+12enn! \sim \sqrt{2 \pi n}(\frac{n}{e})^n = \sqrt{2 \pi} n^{\frac{n + 1}{2}}e^{-n}

两边同取对数:

lnn!12ln(2π)+(n+12)ln(n)n\ln{n!} \sim \frac{1}{2} ln(2 \pi) + (n+\frac{1}{2}) ln(n) - n

根据上式,可见 nn 足够大时,斯特林公式可以近似为:

ln(n!)n(ln(n)1)\ln(n!) \sim n(ln(n) - 1)

则有:

A=ln(2100!)=100!ln(2)B=ln(2100!)2100(ln(2100)1)=2100(100ln(2)1)\begin{array}{l} A = ln(2^{100!}) = 100! ln(2) \\ B = ln(2^{100}!) \sim 2^{100}(ln(2^{100}) - 1) = 2^{100}(100 ln(2) - 1) \end{array}

由于 210=10241032^{10} = 1024 \approx 10^3 ,则有 210010302^{100} \approx 10^{30} , 那么 B1032ln(2)B \approx 10^{32} ln(2)

很明显 100!1032100! \gg 10^{32} ,因此

2100!2100!2^{100!} \gg 2^{100}!

阅读全文 »

By Long Luo

袁哥在微博上发布了一道 数学挑战题

计算 (3+5)n(3+ \sqrt{5})^n 的整数末三位数,给出能口算或者可以用计算器计算的算法的第一个人,免费给一个价值 1000 元的 A9 投资分享群入群名额。
Google_CodeJam_Problem

最开始看到这道题目时,我觉得很简单啊,于是给出了下面的解答:

y=(3+5)ny = (3+ \sqrt{5})^n ,两边同取对数,log10y=nlog10(3+5)\log_{10}{y} = n \log_{10}{(3+\sqrt5)}y=10nlog105.23607y = 10^{n\log_{10}{5.23607}}lg50.7lg5 \approx 0.7 ,所以 y100.7ny \approx 10^{0.7n}

但问题没有这么简单,因为上述解答只在 n=1n = 1 是正确的,n=2n = 2 , y=101.4=25y = 10^{1.4} = 25 就不对了,因为精度不够!

之外,根据评论中其他人给的思路,分析得出这个是周期性的,所以又提交了下面的答案:

Google_CodeJam_log_solution

但问题仍然没有这么简单,因为即使循环周期 k=100k = 100 , log10(3+5)\log_{10}{(3+\sqrt5)} 取的位数再多仍然会出现精度不够的问题。

之后袁哥发布了 解答 ,图片太大,这里放 链接

袁哥的题解省略了很多东西,很多人可能看不太明白。我重新写了题解,重新整理了思路及缺失的步骤,外加证明,有高一数学水平即可看懂。

Google_CodeJam_By_Hand_solution_1

Google_CodeJam_By_Hand_solution_2

后来通过搜索,发现这道题是 Google CodeJam[1] 编程竞赛题,原题如下:

阅读全文 »
0%