《矩阵二分快速幂.doc》由会员分享，可在线阅读，更多相关《矩阵二分快速幂.doc（3页珍藏版）》请在金锄头文库上搜索。
1、矩阵二分快速幂by hzoi2008(东) Rubby&CJH一.矩阵的定义 由mn个数 aij（i=1,2,m; 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+a13b31 c12=a11b12+a12b22+a13b32三.矩阵运算律结合律：（A
2、B）C=A(BC)分配律：（A+B）C=AC+BC C（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 an我们设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) 当然矩阵越大，花在矩阵乘法中的时间就越长，时间效率也会低些PS：转载请注明出处，谢谢合作.
