矩阵与递推
课件： 矩阵与递推
矩阵在第二个月就学过，递推就更早。 当时教练说矩阵可以加速递推，但是我弱，当时并不知道怎么加速。
直到上个月我才在厕所里脑补出来矩阵如何加速递推……
由于概念在课件中讲得很详细，我们来探讨一下如何推出对应的矩阵吧。
我们需要构造：
我们应该如何构造矩阵乘法的结果呢？显然这个东西必须循环，也就是变成
那么大体的思路就是：
首先我们发现，
由于斐波那契数列的性质，构造
然后就可以快速幂了。
总结一下思路：
1.先构造起始矩阵和目标矩阵。
2.确定乘数矩阵。
3.快速幂。
2.确定乘数矩阵。
3.快速幂。
然后问题就解决了。
一个递推如果要用矩阵来加速，应该满足后项可以由前项唯一确定。同时构造的矩阵要尽量小，以免在矩阵乘法上浪费过多的时间。
blue
矩阵与递推
斐波那契数列
已知：
푎1 = 푎2 = ꢀ
푎푖 = 푎푖−1 + 푎푖−2
求푎푛。
问题
有一些递推数列，很难推出通项公式。往往以푂(ꢁ)的时间复
杂度来硬算。
但是，如果只询问某个项的值，线性时间的算法将会浪费大量
时间。
有没有优化的办法，让它只占用푂 푙표푔푛 的时间复杂度？
数学基础
群
群的定义
集合퐺和在퐺上的二元运算⨂，且具有：
1.封闭性 a⨂푏一定在퐺内.
2.结合律 a⨂푏 ⨂푐 = 푎⨂ 푏⨂푐 .
3.单位元 G内存在푒，使得a⨂푒 = 푒⨂푎 = 푎.
4.逆元 对于每一个a，存在b，使得a⨂푏 = b⨂푎 = 푒.
则称(퐺, ⨂)是一个群。
几个例子
请回答：
1.指出(푍,×)的单位元和푎的逆元。
单位元： ꢀ
逆元：ꢂ1
2.指出(푍, ꢃ)的单位元和푎的逆元。
不是群，因为不满足结合律。 푎 ꢃ 푏 ꢃ 푐 ≠ 푎 ꢃ (푏 ꢃ 푐)
有用的性质
凡是乘法意义下的群都可以快速幂。
想一想，为什么？
因为满足结合律。
ꢄ × ꢄ × ꢄ × ꢄ × ꢄ × ꢄ × ꢄ × ꢄ = ꢄ × ꢄ × ꢄ × ꢄ × ꢄ × ꢄ × ꢄ × ꢄ
矩阵群
对于矩阵M和矩阵乘法×，(M,×)是一个群。
ꢀ 0 0
0 ꢀ 0
单位元：
逆元：逆矩阵푀−1
0 0 ꢀ
关于单位元
N阶矩阵的单位元是N阶单位矩阵。
单位矩阵：对角线是ꢀ，其余以0填充。
容易发现，对应的单位矩阵乘以矩阵，总是得到原矩阵。
ꢀ 0 0
0 ꢀ 0
0 0 ꢀ
ꢀ 0
0 ꢀ
1阶： ꢀ
2阶：
3阶：
矩阵快速幂
刚刚说过，凡是乘法运算群都可以快速幂。
矩阵也一样。
代码？和平常的快速幂一样写，重载一下乘号。
加速
学会了矩阵的快速幂，我们不由开始想……
能不能用矩阵乘法的快速幂，来加速递推？
加速递推的工具
递推矩阵
斐波那契数列
回到最初的问题。如何构造斐波那契数列的加速？
提示：构造
ꢀ ꢀ
ꢀ 0
퐹 퐹푛−1
퐹푛ꢅ1 퐹
=
×
푛
푛
解决
퐹 퐹
设置初始矩阵
。那么：
2
1
푛−1
ꢀ ꢀ
ꢀ 0
퐹 퐹푛−1
퐹2 퐹
=
×
푛
1
顺利完成O(푙표푔푛)复杂度的求斐波那契数。
另一种
更好看的版本：
푛
퐹푛ꢅ1
퐹
ꢀ ꢀ
ꢀ 0
푛
=
퐹 퐹푛−1
푛
忘记怎么推出来的了……
汉诺塔问题
令퐻푛为解ꢁ层汉诺塔所需要的移动次数。已知：
퐻푛 = ꢄ퐻푛−1 + ꢀ
试构造矩阵加速递推。
（虽然我知道你们能推出通项公式QAQ）
思路
看黑板。
ꢄ 0
ꢀ ꢀ
퐻푛 ꢀ
퐻푛ꢅ1 ꢀ
=
×
总结
看到递推而且只需要推一个项的题目，可以考虑这样做：
1.先求出递推公式，尝试求出容易计算的通项。
2.如果没办法求出容易计算的通项，就构造矩阵加速。
如何构造矩阵？好的构造 = 经验 + 数学直觉。
blue
END
评论
发表评论