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

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

文章目录

  • 一、线性无关解
  • 二、有重根下的通解
  • 二、有重根下的通解写法
  • 三、有重根下的递推方程求解示例
  • 四、递推方程公式解法总结

一、线性无关解

线性无关解 :

如果

q

是递推方程的

e

重特征根 , 则

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

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

e

是特征根的重数 ;

二、有重根下的通解

q_1, q_2, cdots , q_t

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

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

个项的常数之外的

n

次幂取值是从

0

到

e_i - 1

,

该递推方程通解是 :

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

二、有重根下的通解写法

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

1 . 特征根数 :

q_1, q_2, cdots , q_t

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

t

;

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

H_i(n)

: 特征根

q_i

, 重复度

e_i

, 其中

i

的取值是

0

到

t

; 第

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 ) 通解第
i

项 :

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

3 . 写出通解 :

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

;

  • ( 2 ) 通解组成 : 每个特征根对应的通解项 , 加到一起 , 就是完整的通解 ;
  • ( 3 ) 最终结果 :
H(n) = sumlimits_{i=1}^tH_i(n)

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

求解方法 :

1 . 特征方程 :

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

0

;

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

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

5

项 ;

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

-1

, 最低次幂

0

;

x

的次幂从

0

到

4

;

( 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

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

非重根

2

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

c_42^n

,

c_4

是常数 ,

4

代表这是第

4

个特征根 ;

重根是

-1

, 重复度是

3

;

H_1(n)

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

(-1)^n

组成 ;

系数项中有

3

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

n

的幂 ;

常数使用

c_1, c_2, c_3

表示 ,

n

的幂 取值是

0

到

2

( 系数项个数

-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 ) 代入初值获得方程组 : 将递推方程初值代入通解 , 得到

k

个

k

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

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}

解上述

4

个常数值为 :

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 ) 递推方程标准形式 : 写出递推方程 标准形式 , 所有项都在等号左边 , 右边是

0

;

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

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

-1

, 最低次幂

0

;

( 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 ) 代入初值获得方程组 : 将递推方程初值代入通解 , 得到

k

个

k

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

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

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

1 . 特征根数 :

q_1, q_2, cdots , q_t

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

t

;

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

H_i(n)

: 特征根

q_i

, 重复度

e_i

, 其中

i

的取值是

0

到

t

; 第

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 ) 通解第
i

项 :

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

3 . 写出通解 :

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

;

  • ( 2 ) 通解组成 : 每个特征根对应的通解项 , 加到一起 , 就是完整的通解 ;
  • ( 3 ) 最终结果 :
H(n) = sumlimits_{i=1}^tH_i(n)

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

数学

0 人点赞