【组合数学】递推方程 ( 有重根下递推方程通解结构 | 线性无关解 | 有重根下的通解 | 有重根下的递推方程求解示例 | 递推方程公式解法总结 ) ★

韩曙亮

发布于 2023-03-28 18:30:18

5350

发布于 2023-03-28 18:30:18

文章被收录于专栏：韩曙亮的移动开发专栏

文章目录

一、线性无关解

线性无关解 :

如果

是递推方程的

重特征根 , 则

q^n , nq^n , n^2q^n , \cdots , n^{e-1}q^n

是递推方程的线性无关的解 ;

是特征根的重数 ;

二、有重根下的通解

q_1, q_2, \cdots , q_t

是递推方程的不相等的特征根 , 有

个不相等的特征根 ,

q_i

的重数是

e_i

某一个特征根

q_i

, 其重复度是

e_i

, 该特征根对应的通解中的项是 :

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

上述通解项的系数中 , 含有

e_i

个项 , 这

e_i

个项的常数之外的

次幂取值是从

到

e_i - 1

该递推方程通解是 :

H(n) = \sum\limits_{i=1}^tH_i(n)

二、有重根下的通解写法

有重根下的通解形式列出 :

1 . 特征根数 :

q_1, q_2, \cdots , q_t

是递推方程特征根 , 不相等的特征根数

;

2 . 根据特征根写出通解中的项

H_i(n)

: 特征根

q_i

, 重复度

e_i

, 其中

的取值是

到

; 第

个特征根对应的通解项 , 记作

H_i(n)

;

( 1 ) 组成 : 系数项乘以

q_i^n

;

( 2 ) 系数项 :
- ① 个数 : 有
e_i
项 ; 系数项的个数 , 就是该特征根的重复度 ;
- ② 形式 : 常数乘以
n
的次幂 ; 如 :
n^{e_i-1}
, 这里有
e_i
个常数 ;
- 1 >常数 : 常数下标是从
c_{i1}
到
c_{ie_i}
, 下标的右侧部分是
1
到
e_i
;
- 2 >
n
的次幂 : 幂的取值是从
0
到
e_i - 1
;
- 3 >建议排列方式 : 常数和次幂 , 最好都从小到大排列 , 常数下标与
n
的幂相差
1
;
( 3 ) 通解第

项 :

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

3 . 写出通解 :

( 1 ) 通解项数 : 特征根数

;

( 2 ) 通解组成 : 每个特征根对应的通解项 , 加到一起 , 就是完整的通解 ;
( 3 ) 最终结果 :

H(n) = \sum\limits_{i=1}^tH_i(n)

三、有重根下的递推方程求解示例

求解方法 :

1 . 特征方程 :

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

;

该递推方程目前就是标准形式 ;

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

项 ;

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

-1

, 最低次幂

;

的次幂从

到

;

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

x^4 + x^3 + x^2 + x + 1 = 0

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

x^4 + x^3 - 3x^2 -5 x -2 = 0

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

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

解出的特征根是

-1, -1, -1, 2

;

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

( 1 ) 无重根 : 构造

c_1q_1^n + c_2q_2^n + \cdots + c_kq_k^n

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

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

此处的情况属于有重根的情况 , 参考下面的解法 :

重根

-1

项需要按照重根的通解项规则写 ;

非重根

, 可以按照一般的形式写出 , 即

c_42^n

c_4

是常数 ,

代表这是第

个特征根 ;

重根是

-1

, 重复度是

;

H_1(n)

代表该重根项 , 该项由系数项乘以

(-1)^n

组成 ;

系数项中有

项 ; 每个系数项的形式是常数乘以

的幂 ;

常数使用

c_1, c_2, c_3

表示 ,

的幂取值是

到

( 系数项个数

-1

) ;

写出

-1

特征根对应的通解项 :

H_1(n) = (c_1 + c_2n + c_3n^2)(-1)^n

完整的通解是 :

H(n) = (c_1 + c_2n + c_3n^2)(-1)^n + c_42^n

4 . 求通解中的常数 :

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

个

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

\begin{cases} ( c_1 + 0c_2 + 0^2c_3 )(-1)^0 + 2^0c_4 = F(0) = 1 \\\\ ( c_1 + 1c_2 + 1^2c_3 )(-1)^1 + 2^1c_4 = F(1) = 0 \\\\ ( c_1 + 2c_2 + 2^2c_3 )(-1)^2 + 2^2c_4 = F(2) = 1 \\\\ ( c_1 + 3c_2 + 3^2c_3 )(-1)^3 + 2^3c_4 = F(3) = 2 \end{cases}

化简后为 :

\begin{cases} c_1 +c_4= 1 \\\\ -c_1 - c_2 - c_3 + 2c_4 = 0 \\\\ c_1 +2 c_2 +4 c_3 + 4c_4= 1 \\\\ -c_1 - 3c_2 - 9c_3 + 8c_4= 2 \end{cases}

解上述

个常数值为 :

c_1 = \cfrac{7}{9}, c_2 = -\cfrac{1}{3}, c_3 = 0, c_4 = \cfrac{2}{9}

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

完整的通解 :

H(n) = \cfrac{7}{9} (-1)^n - \cfrac{1}{3} (-1)^n + \cfrac{2}{9}2^n

四、递推方程公式解法总结

递推方程求解完整过程 :

1 . 特征方程 :

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

;

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

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

-1

, 最低次幂

;

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

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

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

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

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

( 1 ) 无重根 : 构造

c_1q_1^n + c_2q_2^n + \cdots + c_kq_k^n

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

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

4 . 求通解中的常数 :

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

个

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

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

有重根下的通解形式列出 :

1 . 特征根数 :

q_1, q_2, \cdots , q_t

是递推方程特征根 , 不相等的特征根数

;

2 . 根据特征根写出通解中的项

H_i(n)

: 特征根

q_i

, 重复度

e_i

, 其中

的取值是

到

; 第

个特征根对应的通解项 , 记作

H_i(n)

;

( 1 ) 组成 : 系数项乘以

q_i^n

;

( 2 ) 系数项 :
- ① 个数 : 有
e_i
项 ; 系数项的个数 , 就是该特征根的重复度 ;
- ② 形式 : 常数乘以
n
的次幂 ; 如 :
n^{e_i-1}
, 这里有
e_i
个常数 ;
- 1 >常数 : 常数下标是从
c_{i1}
到
c_{ie_i}
, 下标的右侧部分是
1
到
e_i
;
- 2 >
n
的次幂 : 幂的取值是从
0
到
e_i - 1
;
- 3 >建议排列方式 : 常数和次幂 , 最好都从小到大排列 , 常数下标与
n
的幂相差
1
;
( 3 ) 通解第

项 :

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

3 . 写出通解 :

( 1 ) 通解项数 : 特征根数

;

( 2 ) 通解组成 : 每个特征根对应的通解项 , 加到一起 , 就是完整的通解 ;
( 3 ) 最终结果 :

H(n) = \sum\limits_{i=1}^tH_i(n)

递推方程 -> 特征方程 -> 特征根 -> 通解 -> 代入初值求通解常数

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-10-24，如有侵权请联系 cloudcommunity@tencent.com 删除

数学

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

数学

登录后参与评论

0 条评论

热度