欢迎来到天天文库
浏览记录
ID:40606788
大小:94.15 KB
页数:5页
时间:2019-08-04
《矩阵乘法递推的优化》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、线性递推关系与矩阵乘法致远学院2011级计算机科学班郭晓旭杨宽March2,2013Abstract对于一般的具有常系数线性递推关系的递推数列,若需要很快算出某一项的精确值,一般的方法是求出特征方程的解然后解出这个递推关系的通项公式。可是随着递推关系阶数的升高,解特征方程的难度也逐渐增大,甚至在递推关系阶数大于5之后,特征方程的次数随之超过5,根本没有代数解法。本3文利用矩阵乘法,提出了一个在O(k⌈logn⌈)的时间复杂度内算出k阶常系数线性递推数列第n项的2精确值的算法,并利用转移矩阵和特征方程的联系,把这个算法的时间复杂度优化到了O(k⌈logn⌉).1常系数线性递推关系的特征方程解法1
2、.1常系数线性递推关系对于一个数列fang,如果fang满足一个递推关系:an=ckan 1+ck 1an 2++c1an k+c08n2N;n>k其中8i2N;ik;ci是常数.则称数列fang满足k阶常系数线性递推关系。特别地,若c0=0,则称fang满足k阶常系数线性齐次递推关系。1.2齐次线性递推关系的特征方程设数列fhng(n0),且存在a1;a2;:::;ak满足:hn=a1hn 1+a2hn 2++akhn k定理1.1:令q为非零常数,则h=qn是常系数线性齐次递推关系nhn=a1hn 1+a2hn 2++akhn k的解的充分必要条件是:q是多项式方程x
3、k axk 1 axk 2 a=0的一个根。该多项式方程12k称为对应的递推关系的特征方程,q称为特征方程的一个特征根。若该多项式方程有k个不同的特征根q1;q2;q3;;qk,则:h=cqn+cqn+cqn++cqnn112233kk是下述意义下的一般解:无论给定h0;h1;h2;:::;hk 1什么初始值,都存在常数c1;c2;c3;:::;ck使得该通项公式是满足其递推关系和初始条件的唯一序列。然而当某个递推关系的特征方程有重根时,我们会发现无法应用以上定理求得该数列的通项公式,这时候我们需要将定理加强为有重根的形式:定理1.2:令q为非零常数,则h=qn是常系数线性
4、齐次递推关系nhn=a1hn 1+a2hn 2++akhn k的特征方程中的s个等根,设其余部分特征根的一般解为Tn,则:cqn+cnqn+cn2qn++cns 1qn+T123sn是原递推关系的一般解。11.3非齐次线性递推关系的特解和通项公式在常系数线性递推关系:hn=a1hn 1+a2hn 2+a3hn 3++akhn k+bn中,如果bn̸=0为常数,那么这个递推关系称为常系数线性非齐次递推关系。事实上,若或bn是与n有关的函数这个递推关系也是可以解出通项公式的。定理1.3:常系数线性非齐次递推关系:hn=a1hn 1+a2hn 2+a3hn 3++akhn k
5、+bn的一般解可以写成如下形式:hn=Tn+pn其中Tn是递推关系hn=a1hn 1+a2hn 2+a3hn 3++akhn k的一般解。而pn是一个常数(或关于n的函数),满足pn=a1pn 1+a2pn 2+a3pn 3++akpn k+bn称为原递推关系的一个特解。若bn为常数,则pn为常数或n的一次多项式,这取决于方程∑kpn=aipn+bni=1是否有解。一般地,pn可以由待定系数法求得。常见的bn和特解pn的对应关系如下:1.bn是n的k次多项式,那么特解pn也应当是n的k次多项式;2.b是n的指数形式,那么p是n的多项式与指数形式的乘积,例如b=dn,那么p应当具有
6、nnnnrdn或rndn的形式。2利用矩阵乘法计算递推数列的某一项2.1构造递推矩阵设数列fhng满足k阶常系数线性递推关系:hn=a1hn 1+a2hn 2+a3hn 3++akhn k构造矩阵01a1a2a3ak 2ak 1akB100000CBCB010000CBCM=B001000CBCB..............CBB.......CC@000100A000010kk与初始值向量01hk 1BBhk 2CCBBhk 3CCB.CX=B..CBCBhCB2C@h1Ah0k12易见010101a1a2a3ak 2ak 1akhk
7、 1hkBB100000CCBBhk 2CCBBhk 1CCBB010000CCBBhk 3CCBBhk 2CCY=MX=B001000CB..C=B..CBCB.CB.CB..............CBCBCBB.......CCBBh2CCBBh3CC@000100A@h1A@h2A000010h0h1对于非齐次的线性递推关系hn=a1hn 1+a2hn 2+a
此文档下载收益归作者所有