【组合数学】递推方程 ( 特特解示例 1 汉诺塔 完整求解过程 | 特解示例 2 特征根为 1 的情况下的特解处理 )

  • 时间:
  • 来源:互联网
  • 文章标签:

文章目录

  • 一、特解示例 1 ( 汉诺塔 )
  • 二、特解示例 2 ( 特征根为 1 的情况 )





一、特解示例 1 ( 汉诺塔 )



Hanoi 问题 :

  • 递推方程为 : T ( n ) = 2 T ( n − 1 ) + 1 T(n) =2 T(n-1) + 1 T(n)=2T(n1)+1
  • 初值 : T ( 1 ) = 1 T(1) = 1 T(1)=1

求该递推方程的解 ?




先解出其特解



1 . 特解形式 :

上述递推方程左侧是 “常系数线性齐次递推方程” 形式 , 不用管 ,

右侧的 1 1 1 与特解相关 ,

1 1 1 n n n 0 0 0 次多项式 ,

因此特解 H ∗ ( n ) H^*(n) H(n) 也是 n n n 0 0 0 次多项式 ;



2 . 写出特解形式 :

特解项数 :特解项数 0 + 1 = 1 0 + 1 = 1 0+1=1 项 ;

特解每项组成 : 特解每一项由 常数 乘以 n n n 的次幂 组成 ,

  • 1 1 1 个常数 设为 P 1 P_1 P1 ,

  • 1 1 1 n n n 的次幂 , 幂取值 0 0 0 ,

因此特解的形式为 T ∗ ( n ) = P 1 n 0 T^*(n) = P_1n^0 T(n)=P1n0 ,

化简后为 : T ∗ ( n ) = P 1 T^*(n) = P_1 T(n)=P1



3 . 将特解代入递推方程 :

将特解 T ∗ ( n ) = P 1 T^*(n) = P_1 T(n)=P1 ,

代入到递推方程 T ( n ) = 2 T ( n − 1 ) + 1 T(n) =2 T(n-1) + 1 T(n)=2T(n1)+1 中 ,

得到 :

P 1 = 2 P 1 + 1 P_1 = 2P_1 + 1 P1=2P1+1

解方程结果 : P 1 = − 1 P_1 = -1 P1=1


特解为 : T ∗ ( n ) = − 1 T^*(n) = -1 T(n)=1






递推方程求解完整过程 : 求解上述汉诺塔 常系数线性齐次递推方程 部分的通解 , T ( n ) − 2 T ( n − 1 ) = 0 T(n) - 2 T(n-1) = 0 T(n)2T(n1)=0 ;


1 . 特征方程 :

( 1 ) 递推方程标准形式 : 写出递推方程 标准形式 , 所有项都在等号左边 , 右边是 0 0 0 ;

T ( n ) − 2 T ( n − 1 ) = 0 T(n) - 2 T(n-1) = 0 T(n)2T(n1)=0


( 2 ) 特征方程项数 : 确定 特征方程项数 , 与 递推方程项数相同 ;

2 2 2 项 ;


( 3 ) 特征方程次幂数 : 最高次幂是 特征方程项数 − 1 -1 1 , 最低次幂 0 0 0 ;

最低次幂 0 0 0 , 最高次幂 1 1 1 ;


( 4 ) 写出 没有系数 的特征方程 ;

x + 1 = 0 x + 1 = 0 x+1=0


( 5 ) 逐位将递推方程的系数 抄写 到特征方程中 ;

x − 2 = 0 x - 2 = 0 x2=0



2 . 解特征根 : 将 特征方程的 特征根 解出来 , x = − b ± b 2 − 4 a c 2 a x = \cfrac{-b \pm \sqrt{b^2 - 4ac}}{2a} x=2ab±b24ac

特征根 q 1 = 2 q_1=2 q1=2 ;



3 . 构造递推方程的通解 :

( 1 ) 无重根 : 构造 c 1 q 1 n + c 2 q 2 n + ⋯ + c k q k n c_1q_1^n + c_2q_2^n + \cdots + c_kq_k^n c1q1n+c2q2n++ckqkn 形式的线性组合 , 该线性组合就是递推方程的 通解 ;

递推方程的齐次部分通解是 : T ( n ) ‾ = c 2 n \overline{T(n)} = c2^n T(n)=c2n

“常系数线性非齐次递推方程” 的通解是 T ( n ) = T ( n ) ‾ + T ∗ ( n ) T(n) = \overline{T(n)} + T^*(n) T(n)=T(n)+T(n)

非齐次部分的特解是 : T ∗ ( n ) = − 1 T^*(n) = -1 T(n)=1

因此汉诺塔递推方程的通解是 : T ( n ) = c 2 n − 1 T(n) = c2^n - 1 T(n)=c2n1


( 2 ) 有重根 : 参考下面的 “有重根下的通解形式列出” 内容 ;



4 . 求通解中的常数 :

( 1 ) 代入初值获得方程组 : 将递推方程初值代入通解 , 得到 k k k k k k 元方程组 , 通过 解该方程组 , 得到 通解中的常数 ;

将初值 T ( 1 ) = 1 T(1) = 1 T(1)=1 代入上述通解 T ( n ) = c 2 n − 1 T(n) = c2^n - 1 T(n)=c2n1 , 得到 2 c − 1 = 1 2c - 1 = 1 2c1=1

常数 c = 1 c = 1 c=1 ;


( 2 ) 代入常数获得通解 : 将常数代入通解 , 就可以得到最终的递推方程的解 ;

将常数 c = 1 c=1 c=1 代入通解 , 最终得到的就是递推方程的解 :

T ( n ) = 2 n − 1 T(n) = 2^n - 1 T(n)=2n1





二、特解示例 2 ( 特征根为 1 的情况 )



递推方程为 : H ( n ) − H ( n − 1 ) = 7 n H(n) - H(n-1) = 7n H(n)H(n1)=7n , 求该递推方程通解 ?




先求其齐次部分 H ( n ) − H ( n − 1 ) = 0 H(n) - H(n-1) = 0 H(n)H(n1)=0 的通解 ;

写出特征方程 : x − 1 = 0 x - 1 = 0 x1=0 , 特征根是 q = 1 q= 1 q=1 ;

齐次部分通解形式 : H ( n ) ‾ = c 1 1 n = c 1 \overline{H(n)} =c_11^n = c_1 H(n)=c11n=c1




求其特解 ( 失败尝试 ) :

上述是常系数 线性 非齐次方程 , 那么先求其 非齐次 部分对应的 特解 ,

右侧是 n n n 1 1 1 次方程 , 则对应的特解是 H ∗ ( n ) = P 1 n + P 2 H^*(n) = P_1n + P_2 H(n)=P1n+P2 , 将上述特解 , 代入到递推方程中 ,

     P 1 n + P 2 − ( P 1 ( n − 1 ) + P 2 ) = 7 n \ \ \ \ P_1n + P_2 - (P_1(n - 1) + P_2) =7n     P1n+P2(P1(n1)+P2)=7n , 化简后变成 :

     P 1 n + P 2 − P 1 n + P 1 − P 2 = 7 n \ \ \ \ P_1n + P_2 - P_1n + P_1 - P_2 = 7n     P1n+P2P1n+P1P2=7n

     P 1 = 7 n \ \ \ \ P_1 = 7n     P1=7n

此时无法解出特解中的常数 P 1 , P 2 P_1, P_2 P1,P2 , 因此不能设置特解为 n n n 1 1 1 次方程 ,


出现这种问题的原因是 , 齐次部分 , 特征方程是 x − 1 = 0 x-1 = 0 x1=0 , 对应的的特征根是 1 1 1 ,

特征根为 1 1 1 时 , 多项式的最高项会抵消掉 , 常数项也会被抵消掉 ;



求特解 , 将 n n n 的次幂提高 1 1 1 :


提高的次幂是 特征根 1 1 1 的重复度 , 如果重复度为 2 2 2 , 则需要提高 2 2 2 次幂 ;


为了解决上述问题 , 这里需要将 n n n 的次幂提高 1 1 1 , 将特解形式中的一次方项 , 设置成平方项 , 其中常数项不设置 , 即使设置了也会抵消掉 , 无法求出常数项值 ;


将特解设置成 n n n 2 2 2 次方程 ,

特解形式为 H ∗ ( n ) = P 1 n 2 + P 2 n H^*(n) = P_1n^2 + P_2n H(n)=P1n2+P2n ;

将特解代入递推方程中 :

P 1 n 2 + P 2 n − ( P 1 ( n − 1 ) 2 + P 2 ( n − 1 ) ) = 7 n P_1n^2 + P_2n - ( P_1(n-1)^2 + P_2(n-1) )=7n P1n2+P2n(P1(n1)2+P2(n1))=7n

P 1 n 2 + P 2 n − ( P 1 ( n 2 − 2 n + 1 ) + P 2 ( n − 1 ) ) = 7 n P_1n^2 + P_2n - ( P_1(n^2 -2n + 1) + P_2(n-1) )=7n P1n2+P2n(P1(n22n+1)+P2(n1))=7n

P 1 n 2 + P 2 n − P 1 n 2 + 2 P 1 n − P 1 − P 2 n + P 2 = 7 n P_1n^2 + P_2n - P_1n^2 + 2P_1n - P_1 - P_2n + P_2=7n P1n2+P2nP1n2+2P1nP1P2n+P2=7n

2 P 1 n − P 1 + P 2 = 7 n 2P_1n - P_1 + P_2=7n 2P1nP1+P2=7n


分析 n n n 的幂写出方程组 :

左右两侧是相等的 , 这里 根据 n n n 的次幂前的系数 , 写出方程组 ;

分析 n n n 的次幂的系数 :

  • n 2 n^2 n2 系数分析 : 右侧没有 n 2 n^2 n2 , 因此左侧的 n 2 n^2 n2 项之前的系数为 0 0 0 ; 左侧也没有 n 2 n^2 n2 项 , 无法抽取方程 ;

  • n 1 n^1 n1 系数分析 : 右侧是 7 n 7n 7n , 因此 n n n 前的系数是 7 7 7 ; 将左侧展开 , n n n 前的系数是 2 P 1 2P_1 2P1 ; 2 P 1 n = 7 n 2P_1n = 7n 2P1n=7n

  • n 0 n^0 n0 系数分析 : 右侧是 0 0 0 ; 将左侧展开 , n 0 n^0 n0 前的系数是 P 2 − P 1 P_2-P_1 P2P1 ; P 2 − P 1 = 0 P_2-P_1 = 0 P2P1=0

最终得到方程组 :


{ 2 P 1 = 7 − P 1 + P 2 = 0 \begin{cases} 2P_1 = 7 \\\\ -P_1 + P_2 = 0 \end{cases} 2P1=7P1+P2=0


解上述方程组 , 得到结果 :

{ P 1 = 7 2 P 2 = 7 2 \begin{cases} P_1 = \cfrac{7}{2} \\\\ P_2 = \cfrac{7}{2} \end{cases} P1=27P2=27


特解是 : H ∗ ( n ) = 7 2 n 2 + 7 2 n H^*(n) = \cfrac{7}{2} n^2 + \cfrac{7}{2}n H(n)=27n2+27n


齐次部分通解形式 : H ( n ) ‾ = c 1 \overline{H(n)} = c_1 H(n)=c1


最终通解是 : H ( n ) = H ( n ) ‾ + H ∗ ( n ) = c 1 + 7 2 n 2 + 7 2 n H(n) = \overline{H(n)} + H^*(n) = c_1 +\cfrac{7}{2} n^2 + \cfrac{7}{2}n H(n)=H(n)+H(n)=c1+27n2+27n

本文链接http://www.taodudu.cc/news/show-1782082.html