资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,3.3常系数线性非其次递推关系,3.3.1 非其次递推关系,3.3.2 举例,3.3.1 非其次递推关系,常系数线性非其次递推关系,a,n,c,1,a,n-1,c,2,a,n-2,c,k,a,n-k,F(n),(),其中c,1,c,2,c,k,是实数常数,c,k,0;,F(n),是只依赖于n且不恒为0的函数。,相伴的齐次递推关系,a,n,c,1,a,n-1,c,2,a,n-2,c,k,a,n-k,(),3.3.1 非其次递推关系,定理,若a,n,x(n)为递推关系(3.3.1)相伴的齐次递推关系()的,通解,,a,n,y(n)为递推关系()的一个,特解,,则a,n,x(n)y(n)为递推关系()的,通解,。,3.3.1 非其次递推关系,定理,设常系数线性非齐次递推关,a,n,c,1,a,n-1,c,2,a,n-2,c,k,a,n-k,F(n),其中c,1,c,2,c,k,是实数常数,c,k,0;,且,F(n),(b,t,n,t,b,t-1,n,t-1,b,1,n b,0,),S,n,其中b,1,b,2,b,t,和S是实数常数。,当,S,是相伴的线性齐次递推关系的特征方程的,m,(m,0,)重根时,存在一个下述形式的特解:,a,n,n,m,(p,t,n,t,p,t-1,n,t-1,p,1,np,0,),S,n,其中p,1,p,2,p,t,为待定系数。,3.3.2 举例,例,解递归,解,(1),相伴齐次递推关系a,n,a,n-1,(,),(,)的特征方程x,10,(,)的特征根 x1,(,)的通解a,n,a,1,n,a(a为任意常数),3.3.2 举例,(2),由于,F(n),nn,1,n,且s,1,是(,)的,1,重,根,所以得()的一个特解形如,a,n,n,1,(p,1,np,0,),1,n,(p,1,p,0,为待定系数),代入a,1,1,a,2,3得,3.3.2 举例,故得()的一个特解,a,n,n,1,(n ),1,n,n,2,n,(3),()的通解,a,n,a n,2,n(a为任意常数),代入a,1,1得a0,(4),求得递归的解a,n,n,2,n,3.3.2 举例,例3.3.2,解Hanoi问题的递归,,,即,解,(1),相伴齐次递推关系a,n,2a,n-1,(,),(,)的特征方程x,20,(,)的特征根 x2,(,)的通解a,n,a,2,n,(a为任意常数),3.3.2 举例,(2),由于,F(n),11,1,n,且s,1,是(,)的,0,重,根,所以得()的一个特解形如,a,n,n,0,p,1,n,p(p为待定系数),代入()得p,1,故得()的一个特解a,n,1,3.3.2 举例,(3),()的通解,a,n,a2,n,1(a为任意常数),代入a,1,1得a1,(4),求得递归的解a,n,2,n,1,3.3.2 举例,定理,若a,n,x(n)和a,n,y(n)分别是递推关系,a,n,c,1,a,n-1,c,2,a,n-2,c,k,a,n-k,F,1,(n),a,n,c,1,a,n-1,c,2,a,n-2,c,k,a,n-k,F,2,(n),的解,其中c,1,c,2,c,k,(c,k,0)是实数常数,F,1,(n)与F,1,(n)是只依赖于n且不恒为0的函数,,则,a,n,x(n)y(n)为递推关系,a,n,c,1,a,n-1,c,2,a,n-2,c,k,a,n-k,F,1,(n),F,2,(n),的解,3.3.2 举例,例,解递归,解,(1),相伴齐次递推关系a,n,3a,n-1,(,),(,)的特征方程x,30,(,)的特征根 x3,(,)的通解a,n,a,3,n,(a为任意常数),3.3.2 举例,(2),分别求a,n,3a,n-1,32,n,(,),a,n,3a,n-1,4n,(,),的一个特解,(,),的一个特解形如b2,n,(b为常数),将其代入,(,),得b6,故求得,(,),的一个特解a,n,62,n,类似求得,(,),的一个特解a,n,2n3,故求得()的一个特解a,n,62,n,2n3,3.3.2 举例,(3),()的通解,a,n,a3,n,62,n,2n3(a为任意常数),(4),代入a,1,8得a5。故求得递归的解,a,n,53,n,62,n,2n3,
展开阅读全文