分类目录归档：Math Tricks

机器猫和玩具鼠

发表于 由
2

引子

上过舒幼生老爷子课的同学应该都会对下面这道概率题印象深刻

舒老师给的标准解法是利用递归：

将所求概率记为\(P\).

猫第一步以\(\frac{1}{2}\)概率左行捉到鼠，对\(P\)的贡献为\(\frac{1}{2}\).

猫第一步以\(\frac{1}{2}\)概率右行，到达\(x=2\)位置。为捉住鼠，猫首先必须左行到\(\frac{1}{2}\)位置，这与开局时要求猫从\(x=1\)位置左行到\(x=0\)位置捉到鼠的情况相同，概率同构也为\(P\)。到达\(x=1\)位置后，游戏又回到初态，猫左行到\(x=0\)位置捉到鼠的概率仍为\(P\)。据此，猫第一步到达\(x=2\)位置，接着也能捉到鼠，对\(P\)的贡献为\(\frac{1}{2}PP\)。

综上所述，可得

\[P=\frac{1}{2}+\frac{1}{2}PP\]

即可解出\(P=1\)

很直接的一个推广就是，假定机器猫向左和向右一步的概率分别为\(q\)和\(1-q\)，问此时是否还一定能抓到老鼠？

我们同样列出等式：

\[P = q + (1-q)P^2\]

不幸的是，这个二次方程有两个根：\(P = 1, q/(1-q)\)

当\(q \ge 1/2\)时，我们知道猫肯定能抓到老鼠，但是对于其他情况呢？到底是有一定的非零概率还是必然能？递归方法遇到了困难。

当然你可以谈\(q=0\)处的情况以及物理问题应有的连续性，我也可以反问\(q=1/2\)时连续性到哪去了。事实上，这种递归方法，类似于对一个连收敛性都未知的无穷级数做种种操作，期望最终能得到结果，而数学，显然不允许你这样瞎搞。
继续阅读 →

Krylov子空间与Arnoldi迭代

发表于 由
回复

看师兄的代码，对于为什么预设一个矩阵是三对角的，纠结了很久，拿出纸笔写了写发现简直就是易得。由于感觉证明太过巧妙，特此记录

引子：Gram Schmitt 正交化步骤

学过线性代数的应该都知道，如果我们有一组线性无关但是不正交的向量组，我们有一套标准的方法，通过重新线性组合将其正交化，称为Gram Schimitt正交化步骤。具体的说，假定我们手上的向量组是\(\{x_1, x_2, ..., x_n\}\)，我们进行如下操作：

\[
\begin{aligned}
&v_1 = x_1 / \|x_1\| \\
&i = 2, ..., n \\
&\quad v_i = x_i \\
&\quad j = 1, ..., i-1 \\
&\quad \quad v_i = v_i - v_j v_j^T v_i \\
&\quad v_i = v_i / \|v_i\|
\end{aligned}
\]

这样我们就拿到了一个正交归一的向量组\(\{v_1, v_2, ..., v_n\}\)

继续阅读 →

极值问题中的Fibonacci序列

发表于 由
2
(*虽然这学期分数出来了是跪了，还是把这一篇写完吧TAT*)
众所周知，在寻找单峰函数的极值问题中有一个著名的，总是带着华罗庚名字的\(0.618\)法，但是它实际上并不是这个思路下最优的算法。最优的算法直接和Fibonacci数列相联系。
这是我在看袁亚湘的《非线性优化数值计算方法》中看到的一个有关Fibonacci数列的一个算法，感觉很有意思。我尝试在他的基础上将这个算法讲的更清楚一些。

(*话说刷过不少blog后发现博主们都喜欢一些自己专业之外的小东西，毕竟自己专业的东西看起来要么太trival，要么就太难以向读者讲清楚了*)

继续阅读 →

二维曲线的傅里叶分解

发表于 由
回复

受看到的一幅动图：一千个圆零一个姑娘 的刺激，
photo-media
心血来潮花了半个晚上加一上午做了这个Mma的程序。思路是
1.录入部分使用Button[]以及MousePosition[]
2.傅里叶分解时把(x,y)看做z=x+i y一个变量直接按离散傅里叶变换变换，与寻常的二维傅里叶变换不同，这样就可以保证最后出来是圆周运动的叠加
3.哪个圆排前面哪个圆排后面纠结了我很久，最后的决定是，按照基频的0,M-1,1,M-2,2,...倍排序

录入的代码：

Clear;
Dynamic[posi];
posi = {};
Button[Show[
Graphics[Line[Dynamic[posi]], PlotRange -> {1, GoldenRatio},
ImageSize -> 600]],
posi = Append[posi, MousePosition["Graphics"]]]

在生成的那个大按钮上一个一个描点连线就可以了。
图画完后运行这一段：

M = Length[posi];
z = (#[[1]] + I #[[2]]) & /@ posi;
c = Sort[Transpose[{Fourier[z]/Sqrt[M], Array[# - 1 &, M]}],
Norm[#1[[1]]] > Norm[#2[[1]]] &];
cir = Table[
FoldList[#1 + #2[[1]] Exp[-2 \[Pi] I #2[[2]] t/M] &, 0, c], {t, 0,
M - 1}];
file =
Table[
Show[Graphics[
Table[Circle[{Re[#], Im[#]} &[cir[[n, m]]],
Norm[If[m == M, 0, c[[m, 1]]]]], {m, 1, M}]],
Graphics[{Red, Line[{Re[#], Im[#]} & /@ (z[[;; n]])]}],
PlotRange -> {1, GoldenRatio}, ImageSize -> 600], {n, 2,
Length[c]}];
ListAnimate[file, AnimationRate -> 4]

Mathematica里面的Fourier函数用的直接就是快速傅里叶变换
还有图片的帧数直接是等于你描的点数。
然后就尝试了几个：
1.丧尸群头像：
photo-media
感觉手残了。。。
2,附中校徽
photo-media
3.pku校徽：（之所以放在后面是为了避免画残然后被各种...）
photo-media
尝试了一下画人的头像，画的惨不忍睹...所以还是放弃了。