《特征方程求解递归方程.ppt》由会员分享，可在线阅读，更多相关《特征方程求解递归方程.ppt（28页珍藏版）》请在三一办公上搜索。
1、求解递归方程,算法复杂性经常描述为递归方程，解递归方程得到算法复杂性的具体表示用特征方程解递归方程 用生成函数解递归方程用递推方法解递归方程,用特征方程解递归方程,K阶常系数线性齐次递归方程K阶常系数线性非齐次递归方程,K阶常系数线性齐次递归方程形如：,K阶常系数线性齐次递归方程,其中，bi为常数，第2项为方程初始条件。在上式中，用xn取代f(n),有：两边分别除以xn-k，得：,特征方程如下：解题原理：1）求解上述特征方程的根，得到递归方程的通解2）利用递归方程初始条件，确定通解中待定系数，得到递归方程的解 考虑2种情况：1）特征方程的k个根不相同2）特征方程有相重的根,特征方程的k个根不相
2、同：,假设：q1,q2,qk是k个不同的根，则递归方程的通解为,特征方程的k个根有重根：,假设：r个重根qi,qi+1,qi+r-1，则递归方程的通解为,前面2种情况下的c1,c2,ck均为待定系数；将初始条件代入，建立联立方程，确定各个系数具体值，得到通解f(n)例1.3阶常系数线性齐次递归方程如下,解：特征方程为 x3 6x2+11x 6=0,改写方程为：因式分解：(x-1)(x-2)(x-3)=0得到特征根：q1=1,q2=2,q3=3 递归方程的通解为：,由初始条件得：得到：c1=0,c2=-2,c3=2 因此，递归方程的解为：,例2。3阶常系数线性齐次递归方程如下,解：特征方程为 x
3、3 5x2+7x 3=0改写为：x3 5x2+6x+x 3=0因式分解：(x-3)(x2 2x+1)=0(x-3)(x-1)(x-1)=0,得到特征根：q1=1,q2=1,q3=3 递归方程的通解为：代入初始条件：,得到：c1=0,c2=-1,c3=1 因此，递归方程的解为：,作业1,解下列递归方程：1.f(n)=3f(n-1),f(0)=52.f(n)=2f(n-1)f(0)=23.f(n)=5f(n-1)6f(n-2),f(0)=1,f(1)=14.f(n)=-6f(n-1)9f(n-2),f(0)=3,f(1)=-3,K阶常系数线性非齐次递归方程形如：,二、K阶常系数线性非齐次递归方程,
4、其中，bi为常数，第2项为方程初始条件。它的通解形式为：其中，1）为对应齐次递归方程的通解2）f*(n)为原非齐次递归方程的特解,解题原理：1.一般没有寻找特解的有效方法2.先根据g(n)具体形式，确定特解；再将特解代入递归方程，用待定系数法，求解特解的系数3.g(n)分为以下几种情况:g(n)是n的m次的多项式 g(n)是n的指数函数,g(n)是n的m次的多项式,g(n)形如：其中，bi为常数。此时，特解f*(n)也是n的m次多项式，形如：各个系数Ai待定,例3。2阶常系数线性非齐次递归方程如下,解：对应的齐次方程的特征方程为 x2 7x+10=0因式分解：(x 2)(x 5)=0 特征根：
5、q1=2，q2=5对应齐次方程通解：,令非齐次递归方程的特解为：,代入原递归方程得：,!由此得到联立方程：解得：A1=1,A2=13/2,A3=103/8非齐次递归方程的通解为：,化简后得到：,初始条件代入有：,得到：c1=-41/3,c2=43/24最后，非齐次递归方程通解为：,g(n)是n的指数函数,g(n)形如：其中，a和bi为常数。1）如果a不是特征方程的重根，特解f*(n)形如：各个系数Ai待定,2）如果a是特征方程的r重特征根，特解f*(n)形如：各个系数Ai待定,例4。2阶常系数线性非齐次递归方程如下,解：对应的齐次方程的特征方程为 x2 7x+12=0因式分解：(x 3)(x 4)=0 特征根：q1=3，q2=4对应齐次方程通解：,a=2不是特征方程的重根，故令非齐次递归方程的特解为：,代入原递归方程得：化简后得到：,由此得到联立方程：解得：A1=2,A2=10非齐次递归方程的通解为：,初始条件代入有：,得到：c1=-14,c2=5最后，非齐次递归方程通解为：,作业2,解下列递归方程：1.f(n)=f(n-1)+n2,f(0)=02.f(n)=2f(n-1)+n,f(0)=13.f(n)=3f(n-1)+2n,f(0)=34.f(n)=2f(n-1)+2n n2,f(0)=1,
