矩阵二分快速幂

《矩阵二分快速幂》由会员分享，可在线阅读，更多相关《矩阵二分快速幂（2页珍藏版）》请在金锄头文库上搜索。

1、矩阵二分快速幂矩阵二分快速幂by hzoi2008(东东) Rubby j=1,2,，n）排成的 m 行 n 列的数表如 称为一个 mn 的矩阵，记做 A=简记做 A=Amn=（aij）mn 其中的 mn 个数称为 A 的元素，简称为元。二.矩阵乘法定义：Ams与 Bsn的乘积是一个 mn 的矩阵 Cmn 其中 cij=ai1b1j+ai2b2j+ai3b3j+aisbsj= aikbkj（k（1，s） ）记做 C=AB 称“AB”为“以 A 左乘 B”或“以 B 右乘 A” ，如其中 c11=a11b11+a12b21+a13b31c12=a11b12+a12b22+a13b32 三.矩阵运

2、算律结合律：（AB）C=A(BC) 分配律：（A+B）C=AC+BCC（A+B）=CA+CB 注：矩阵运算并不满足交换律，AB 与 BA 不等价 若 A 为 ms 矩阵，B 为 sn 矩阵，则 AB 为 mn 矩阵 而 BA 无法进行矩阵乘法运算；即便是方阵（nn）交换后乘得的结果也不一定相同，除 了相当特殊的，例如每个元素都是 1 的方阵四.矩阵与线性递推线性递推方程即形如 fn=a1fn-1+a2fn-2+aifn-i的方程 以斐波那契数列为例 an=an-1+an-2 我们的目的是通过矩阵乘法，求得斐波那契数列的第 n 项，为了得到这个结果，我们还需要由an-2 an-1推得an-1 a

3、n 我们设an-2 an-1为矩阵 A，因为 A12B22=C12，所以 C 与 A 是同规模的矩阵an-2 an-1 = an-1 an一般的对于线性递推方程 fn=a1fn-1+a2fn-2+aifn-i可以建立 B=设 A=f1 f2 f3 fi，则由 ABBB（k 个 B）即可得到 fi+k 这个自行手模一下就可以发现规律五.利用矩阵乘法优化递推原理：快速幂矩阵乘法满足结合律 如 AB7=AB4B2B AB19=AB16B2B 快速幂的有关知识不清楚的请自行检索 这样可以令每一步运算都得到最大限度利用 理论上可以由普通递推的 O(n)降至 O(logn) 当然矩阵越大，花在矩阵乘法中的时间就越 长，时间效率也会低些PSPS：转载请注明出处，谢谢合作：转载请注明出处，谢谢合作. .