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

2023-03-28 18:31:32 浏览数 (1)

文章目录

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

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

Hanoi 问题 :

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

求该递推方程的解 ?

先解出其特解

1 . 特解形式 :

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

右侧的

1

与特解相关 ,

1

为

n

的

0

次多项式 ,

因此特解

H^*(n)

也是

n

的

0

次多项式 ;

2 . 写出特解形式 :

特解项数 : 则 特解项数 是

0 1 = 1

项 ;

特解每项组成 : 特解每一项由 常数 乘以

n

的次幂 组成 ,

1

个常数 设为

P_1

,

1

个

n

的次幂 , 幂取值

0

,

因此特解的形式为

T^*(n) = P_1n^0

,

化简后为 :

T^*(n) = P_1

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

将特解

T^*(n) = P_1

,

代入到递推方程

T(n) =2 T(n-1) 1

中 ,

得到 :

P_1 = 2P_1 1

解方程结果 :

P_1 = -1

特解为 :

T^*(n) = -1

递推方程求解完整过程 : 求解上述汉诺塔 常系数线性齐次递推方程 部分的通解 ,

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

;

1 . 特征方程 :

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

0

;

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

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

2

项 ;

( 3 ) 特征方程次幂数 : 最高次幂是 特征方程项数

-1

, 最低次幂

0

;

最低次幂

0

, 最高次幂

1

;

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

x 1 = 0

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

x - 2 = 0

2 . 解特征根 : 将 特征方程的 特征根 解出来 ,

x = cfrac{-b pm sqrt{b^2 - 4ac}}{2a}

特征根

q_1=2

;

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

( 1 ) 无重根 : 构造

c_1q_1^n c_2q_2^n cdots c_kq_k^n

形式的线性组合 , 该线性组合就是递推方程的 通解 ;

递推方程的齐次部分通解是 :

overline{T(n)} = c2^n

“常系数线性非齐次递推方程” 的通解是

T(n) = overline{T(n)} T^*(n)

非齐次部分的特解是 :

T^*(n) = -1

因此汉诺塔递推方程的通解是 :

T(n) = c2^n - 1

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

4 . 求通解中的常数 :

( 1 ) 代入初值获得方程组 : 将递推方程初值代入通解 , 得到

k

个

k

元方程组 , 通过 解该方程组 , 得到 通解中的常数 ;

将初值

T(1) = 1

代入上述通解

T(n) = c2^n - 1

, 得到

2c - 1 = 1

常数

c = 1

;

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

将常数

c=1

代入通解 , 最终得到的就是递推方程的解 :

T(n) = 2^n - 1

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

递推方程为 :

H(n) - H(n-1) = 7n

, 求该递推方程通解 ?

先求其齐次部分

H(n) - H(n-1) = 0

的通解 ;

写出特征方程 :

x - 1 = 0

, 特征根是

q= 1

;

齐次部分通解形式 :

overline{H(n)} =c_11^n = c_1

求其特解 ( 失败尝试 ) :

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

右侧是

n

的

1

次方程 , 则对应的特解是

H^*(n) = P_1n P_2

, 将上述特解 , 代入到递推方程中 ,

P_1n P_2 - (P_1(n - 1) P_2) =7n

, 化简后变成 :

P_1n P_2 - P_1n P_1 - P_2 = 7n
P_1 = 7n

此时无法解出特解中的常数

P_1, P_2

, 因此不能设置特解为

n

的

1

次方程 ,

出现这种问题的原因是 , 齐次部分 , 特征方程是

x-1 = 0

, 对应的的特征根是

1

,

特征根为

1

时 , 多项式的最高项会抵消掉 , 常数项也会被抵消掉 ;

求特解 , 将

n

的次幂提高

1

:

提高的次幂是 特征根

1

的重复度 , 如果重复度为

2

, 则需要提高

2

次幂 ;

为了解决上述问题 , 这里需要将

n

的次幂提高

1

, 将特解形式中的一次方项 , 设置成平方项 , 其中常数项不设置 , 即使设置了也会抵消掉 , 无法求出常数项值 ;

将特解设置成

n

的

2

次方程 ,

特解形式为

H^*(n) = P_1n^2 P_2n

;

将特解代入递推方程中 :

P_1n^2 P_2n - ( P_1(n-1)^2 P_2(n-1) )=7n
P_1n^2 P_2n - ( P_1(n^2 -2n 1) P_2(n-1) )=7n
P_1n^2 P_2n - P_1n^2 2P_1n - P_1 - P_2n P_2=7n
2P_1n - P_1 P_2=7n

分析

n

的幂写出方程组 :

左右两侧是相等的 , 这里 根据

n

的次幂前的系数 , 写出方程组 ;

分析

n

的次幂的系数 :

n^2

系数分析 : 右侧没有

n^2

, 因此左侧的

n^2

项之前的系数为

0

; 左侧也没有

n^2

项 , 无法抽取方程 ;

n^1

系数分析 : 右侧是

7n

, 因此

n

前的系数是

7

; 将左侧展开 ,

n

前的系数是

2P_1

;

2P_1n = 7n
n^0

系数分析 : 右侧是

0

; 将左侧展开 ,

n^0

前的系数是

P_2-P_1

;

P_2-P_1 = 0

最终得到方程组 :

begin{cases} 2P_1 = 7 \\ -P_1 P_2 = 0 end{cases}

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

begin{cases} P_1 = cfrac{7}{2} \\ P_2 = cfrac{7}{2} end{cases}

特解是 :

H^*(n) = cfrac{7}{2} n^2 cfrac{7}{2}n

齐次部分通解形式 :

overline{H(n)} = c_1

最终通解是 :

H(n) = overline{H(n)} H^*(n) = c_1 cfrac{7}{2} n^2 cfrac{7}{2}n
数学

0 人点赞