【组合数学】递推方程 ( 特征方程与特征根 | 特征方程示例 | 一元二次方程根公式 )

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

文章目录

  • 一、特征方程与特征根
  • 二、特征方程与特征根 示例 ( 重要 )

一、特征方程与特征根

常系数线性齐次递推方程标准型 :

begin{cases} H(n) - a_1H(n-1) - a_2H(n-2) - cdots - a_kH(n-k) = 0 \\ H(0) = b_0 , H(1) = b_1 , H(2) = b_2 , cdots , H(k-1) = b_{k-1} end{cases}

常系数 是指数列的 项之前的 系数

a_1 , a_2 , cdots , a_k

都是常数 ,

a_k not=0

;

b_0 , b_1, b_2 , cdots , b_{k-1}

是 递推方程的

k-1

个初值 ;

写出特征方程 :

x^k - a_1x^{k-1} - cdots - a^k = 0

特征方程、递推方程的项数、特征方程的次幂数 :

  • 特征方程、递推方程的项数 : 特征方程项的个数 与 常系数线性齐次 递推方程项的个数相同 , 有
k 1

项 ;

  • 特征方程的次幂数 : 总共有
k 1

项 , 特征方程项的

x

的次幂 从

k

到

0

, 总共有

k 1

项 ;

递推方程 与 特征方程关系 :

x^k

前的系数

1

对应

H(n)

项前的系数

1

;

x^{k-1}

前的系数

-a_1

对应

H(n-1)

项前的系数

-a_1

;

vdots
x^{0}

前的系数

-a_k

对应

H(n-k)

项前的系数

-a_k

;

由 递推方程 :

H(n) - a_1H(n-1) - a_2H(n-2) - cdots - a_kH(n-k) = 0

可以导出

1

元

k

次特征方程 :

x^k - a_1x^{k-1} - cdots - a^k = 0

该

1

元

k

次特征方程 称为 原递推方程的 特征方程 ;

该

1

元

k

次特征方程 有

k

个根 , 称为 递推方程 的特征根 ;

由递推方程到特征方程 ( 重点 ) :

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

;

  • 特征方程项数 : 确定 特征方程项数 , 与 递推方程项数相同 ;
  • 特征方程次幂数 : 最高次幂是 特征方程项数
-1

, 最低次幂

0

;

  • 写出 没有系数 的特征方程 ;
  • 逐位将递推方程的系数 抄写 到特征方程中 ;

解出上述特征方程 , 就可以得到特征根 , 一般都是一元二次方程 ;

一元二次方程形式

ax^2 bx c = 0

解为 :

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

二、特征方程与特征根 示例 ( 重要 )

1 . 斐波那契数列示例 :

( 1 ) 斐波那契数列 :

1 , 1 , 2 , 3 , 5 , 8 , 13 , cdots

( 2 ) 递推方程 :

F(n) = F(n-1) F(n-2)

描述 : 第

n

项等于第

n-1

项 和 第

n-2

项之和 ;

如 : 第

4

项的值

F(4) = 5

, 就等于

第

4-1=3

项的值

F(4-1)=F(3) = 3

加上 第

4-2=2

项的值

F(4-2) = F(2) =2

;

( 3 ) 初值 :

F(0) = 1 , F(1) = 1

根据

F(0) = 1, F(1) = 1

可以计算

F(2)

, 根据

F(1),F(2)

可以计算

F(3)

, 根据

F(2)F(3)

可以 计算

F(4)

,

cdots

, 根据

F(n-2) , F(n-1)

可以计算

F(n)

;

2 . 写出斐波那契数列的特征方程 :

递推方程 :

F(n) = F(n-1) F(n-2)

( 1 ) 递推方程标准形式 :

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

( 2 ) 递推方程写法 :

① 先确定特征方程的项数 : 与递推方程项数相同 ,

3

项 ;

② 在确定特征方程

x

的次幂 : 从

3-1=2

到

0

;

③ 初步写出没有系数的递推方程 :

x^2 x^1 x^0 = 0

④ 填充系数 : 然后将没有系数的特征方程

x^2 x^1 x^0 = 0

与

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

对应位的系数填充到特征方程中 :

x^2

前的系数 对应

F(n)

项前的系数

1

;

x^1

前的系数 对应

F(n-1)

项前的系数

-1

;

x^0

前的系数 对应

F(n-2)

项前的系数

-1

;

则最终的 特征方程是

1 x^2 (-1)x^1 (-1)x^0 = 0

, 化简后为 :

x^2 - x - 1 = 0

特征方程的特征根是 : 上述方程的解就是特征根 , 一般都是一元二次方程 ;

x = cfrac{1 pm sqrt{5}}{2}

参考 : 一元二次方程形式

ax^2 bx c = 0

解为 :

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

0 人点赞