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

韩曙亮

发布于 2023-03-28 18:29:01

6630

发布于 2023-03-28 18:29:01

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

文章目录

一、特征方程与特征根

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

\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

项 , 特征方程项的

的次幂从

到

, 总共有

k + 1

项 ;

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

x^k

前的系数

对应

H(n)

项前的系数

;

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

可以导出

元

次特征方程 :

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

该

元

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

该

元

次特征方程有

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

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

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

;

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

-1

, 最低次幂

;

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

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

一元二次方程形式

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-1

项和第

n-2

项之和 ;

如 : 第

项的值

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-1=2

到

;

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

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)

项前的系数

;

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}

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

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

数学

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

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

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

数学

登录后参与评论

0 条评论

热度