矩阵乘法递推的优化

《矩阵乘法递推的优化》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、线性递推关系与矩阵乘法致远学院2011级计算机科学班郭晓旭杨宽March2,2013Abstract对于一般的具有常系数线性递推关系的递推数列，若需要很快算出某一项的精确值，一般的方法是求出特征方程的解然后解出这个递推关系的通项公式。可是随着递推关系阶数的升高，解特征方程的难度也逐渐增大，甚至在递推关系阶数大于5之后，特征方程的次数随之超过5，根本没有代数解法。本3文利用矩阵乘法，提出了一个在O(k⌈logn⌈)的时间复杂度内算出k阶常系数线性递推数列第n项的2精确值的算法，并利用转移矩阵和特征方程的联系，把这个算法的时间复杂度优化到了O(k⌈logn⌉).1常系数线性递推关系的特征方程解法1

2、.1常系数线性递推关系对于一个数列fang，如果fang满足一个递推关系:an=ckan1+ck1an2+


+c1ank+c08n2N;n>k其中8i2N;ik;ci是常数.则称数列fang满足k阶常系数线性递推关系。特别地，若c0=0，则称fang满足k阶常系数线性齐次递推关系。1.2齐次线性递推关系的特征方程设数列fhng(n0),且存在a1;a2;:::;ak满足：hn=a1hn1+a2hn2+


+akhnk定理1.1：令q为非零常数，则h=qn是常系数线性齐次递推关系nhn=a1hn1+a2hn2+


+akhnk的解的充分必要条件是：q是多项式方程x

3、kaxk1axk2


a=0的一个根。该多项式方程12k称为对应的递推关系的特征方程，q称为特征方程的一个特征根。若该多项式方程有k个不同的特征根q1;q2;q3;


;qk,则：h=cqn+cqn+cqn+


+cqnn112233kk是下述意义下的一般解:无论给定h0;h1;h2;:::;hk1什么初始值，都存在常数c1;c2;c3;:::;ck使得该通项公式是满足其递推关系和初始条件的唯一序列。然而当某个递推关系的特征方程有重根时，我们会发现无法应用以上定理求得该数列的通项公式，这时候我们需要将定理加强为有重根的形式：定理1.2：令q为非零常数，则h=qn是常系数线性

4、齐次递推关系nhn=a1hn1+a2hn2+


+akhnk的特征方程中的s个等根，设其余部分特征根的一般解为Tn，则：cqn+cnqn+cn2qn+


+cns1qn+T123sn是原递推关系的一般解。11.3非齐次线性递推关系的特解和通项公式在常系数线性递推关系：hn=a1hn1+a2hn2+a3hn3+


+akhnk+bn中，如果bn̸=0为常数，那么这个递推关系称为常系数线性非齐次递推关系。事实上，若或bn是与n有关的函数这个递推关系也是可以解出通项公式的。定理1.3：常系数线性非齐次递推关系：hn=a1hn1+a2hn2+a3hn3+


+akhnk

5、+bn的一般解可以写成如下形式：hn=Tn+pn其中Tn是递推关系hn=a1hn1+a2hn2+a3hn3+


+akhnk的一般解。而pn是一个常数(或关于n的函数)，满足pn=a1pn1+a2pn2+a3pn3+


+akpnk+bn称为原递推关系的一个特解。若bn为常数，则pn为常数或n的一次多项式，这取决于方程∑kpn=ai
pn+bni=1是否有解。一般地，pn可以由待定系数法求得。常见的bn和特解pn的对应关系如下：1.bn是n的k次多项式，那么特解pn也应当是n的k次多项式；2.b是n的指数形式，那么p是n的多项式与指数形式的乘积，例如b=dn，那么p应当具有

6、nnnnr
dn或r
n
dn的形式。2利用矩阵乘法计算递推数列的某一项2.1构造递推矩阵设数列fhng满足k阶常系数线性递推关系：hn=a1hn1+a2hn2+a3hn3+


+akhnk构造矩阵01a1a2a3


ak2ak1akB100


000CBCB010


000CBCM=B001


000CBCB..............CBB.......CC@000


100A000


010kk与初始值向量01hk1BBhk2CCBBhk3CCB.CX=B..CBCBhCB2C@h1Ah0k12易见010101a1a2a3


ak2ak1akhk

7、1hkBB100


000CCBBhk2CCBBhk1CCBB010


000CCBBhk3CCBBhk2CCY=MX=B001


000CB..C=B..CBCB.CB.CB..............CBCBCBB.......CCBBh2CCBBh3CC@000


100A@h1A@h2A000


010h0h1对于非齐次的线性递推关系hn=a1hn1+a2hn2+a