【组合数学】递推方程 ( 常系数线性非齐次递推方程 的 非齐次部分是 多项式 与 指数 组合方式 | 通解的四种情况 )

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

文章目录

  • 一、常系数线性非齐次递推方程 的 非齐次部分是 多项式 与 指数 组合方式
  • 二、递推方程通解的四种情况

一、常系数线性非齐次递推方程 的 非齐次部分是 多项式 与 指数 组合方式

如果 “常系数线性非齐次递推方程” 的非齐次部分 , 是

n

的

t

次多项式 , 与

beta^n

的指数 , 的组合 ;

那么其特解的形式 , 是

n

的

t

次多项式 , 与

Pbeta^n

的 和 ;

递推方程 :

a_n - 2a_{n-1} = n 3^n

初值 :

a_0 = 0

通解形式 ( 重要 ) :

① 非齐次部分是

n

的

t

次多项式 :

  • 特征根不为
1

, 特解是

n

的

t

次多项式 ;

  • 如果特征根为
1

, 且重数为

e

, 那么特解是

n

的

t e

次多项式 ;

② 非齐次部分是

Pbeta^n

:

  • 特征根不能是底
beta

, 特解是

Pbeta^n

;

  • 特征根是底
beta

, 该特征根重数为

e

, 特解是

Pn^ebeta^n

;

③ 齐次部分没有重根 :

H(n) = c_1q_1^n c_2q_2^n cdots c_kq_k^n

④ 齐次部分有重根 : 通解第

i

项 , 特征根

q_i

, 重数

e_i

,

H_i(n) = (c_{i1} c_{i2}n cdots c_{ie_i}n^{e_i - 1})q_i^n

, 最终通解

H(n) = sumlimits_{i=1}^tH_i(n)

;

参考博客 : 【组合数学】递推方程 ( 常系数线性非齐次递推方程 的 非齐次部分是 多项式 与 指数 组合方式 | 通解的四种情况 )

计算齐次部分通解 :

递推方程齐次部分标准形式 :

a_n - 2a_{n-1} = 0

特征方程 :

x - 2 = 0

特征根 :

x=2

齐次部分通解 :

overline{a_n} =c2^n

计算非齐次部分通解 :

上述递推方程非齐次部分是

n 3^n

, 由两部分构成 :

n

的

t

次多项式 :

n

, 特征根不为

1

, 对应的特解是

n

的

t

次多项式 , 形式为

P_1n P_2

;

beta^n

指数 :

3^n

, 特征根不是底

3

, 对应的特解是

Pbeta^n

形式 , 形式为

P_33^n

;

完整的特解 :

a^*_n = P_1n P_2 P_33^n

将特解代入到递推方程 :

(P_1n P_2 P_33^n) - 2[P_1(n-1) P_2 P_33^{n-1}] = n 3^n

将左边式子展开 :

-P_1n (2P_1 - P_2) P_33^{n-1}=n 3^n

根据分析

n

的次幂项 , 常数项 ,

3^n

项的对应关系 , 可以得到以下方程组 :

begin{cases} -P_1 = 1 \\ 2P_1 - P_2 = 0 \\ cfrac{P_3}{3} =1 end{cases}

解上述方程组 , 结果为 :

begin{cases} P_1 = -1 \\ P_2 = -2 \\ P_3 =3 end{cases}

特解 : 将上述常数代入到

a^*_n = P_1n P_2 P_33^n

中 , 得到最终特解 :

a^*_n = -n - 2 3^{n 1}

;

齐次部分通解形式 :

overline{a_n} =c2^n

完整通解 :

a_n = overline{a_n} a^*_n = c2^n -n - 2 3^{n 1}

将初值

a_0 = 0

代入上述通解 :

c2^0 - 0 - 2 3^{0 1} = 0
c - 2 3 = 0
c=-1

最终递推方程的通解是

a_n = 2^n -n - 2 3^{n 1}

二、递推方程通解的四种情况

通解形式 ( 重要 ) :

① 非齐次部分是

n

的

t

次多项式 :

  • 特征根不为
1

, 特解是

n

的

t

次多项式 ;

  • 如果特征根为
1

, 且重数为

e

, 那么特解是

n

的

t e

次多项式 ;

② 非齐次部分是

Pbeta^n

:

  • 特征根不能是底
beta

, 特解是

Pbeta^n

;

  • 特征根是底
beta

, 该特征根重数为

e

, 特解是

Pn^ebeta^n

;

③ 齐次部分没有重根 :

H(n) = c_1q_1^n c_2q_2^n cdots c_kq_k^n

④ 齐次部分有重根 : 通解第

i

项 , 特征根

q_i

, 重数

e_i

,

H_i(n) = (c_{i1} c_{i2}n cdots c_{ie_i}n^{e_i - 1})q_i^n

, 最终通解

H(n) = sumlimits_{i=1}^tH_i(n)

;

参考博客 : 【组合数学】递推方程 ( 常系数线性非齐次递推方程 的 非齐次部分是 多项式 与 指数 组合方式 | 通解的四种情况 )

博客 数学

0 人点赞