【组合数学】递推方程 ( 常系数线性齐次递推方程 | 常系数、线性、齐次 概念说明 | 常系数线性齐次递推方程公式解法 | 特征根 | 通解 | 特解 )

简介: 【组合数学】递推方程 ( 常系数线性齐次递推方程 | 常系数、线性、齐次 概念说明 | 常系数线性齐次递推方程公式解法 | 特征根 | 通解 | 特解 )

文章目录

一、常系数线性齐次递推方程

二、常系数、线性、齐次 概念说明

三、常系数线性齐次递推方程公式解法

四、常系数线性齐次递推方程公式解法内容概要





一、常系数线性齐次递推方程


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


{ H ( n ) − a 1 H ( n − 1 ) − a 2 H ( n − 2 ) − ⋯ − a k H ( n − k ) = 0 H ( 0 ) = b 0 , H ( 1 ) = b 1 , H ( 2 ) = b 2 , ⋯   , H ( k ) = b k

⎧⎩⎨H(n)−a1H(n−1)−a2H(n−2)−⋯−akH(n−k)=0H(0)=b0,H(1)=b1,H(2)=b2,⋯,H(k)=bk

{H(n)−a1H(n−1)−a2H(n−2)−⋯−akH(n−k)=0H(0)=b0,H(1)=b1,H(2)=b2,⋯,H(k)=bk


 

H(n)−a

1


H(n−1)−a

2


H(n−2)−⋯−a

k


H(n−k)=0

H(0)=b

0


,H(1)=b

1


,H(2)=b

2


,⋯,H(k)=b

k




常系数 是指数列的 项之前的 系数 a 1 , a 2 , ⋯   , a k a_1 , a_2 , \cdots , a_ka

1


,a

2


,⋯,a

k


 都是常数 , a k ≠ 0 a_k \not=0a

k


 


=0 ;


齐次 指的是将数列项移动到左边 , 右边项等于 0 00 ;


上述称为 k kk 阶 常系数线性齐次递推方程 ;


b 0 , b 1 , b 2 , ⋯   , b k b_0 , b_1, b_2 , \cdots , b_kb

0


,b

1


,b

2


,⋯,b

k


 是 递推方程的 k kk 个初值 ;






二、常系数、线性、齐次 概念说明


常系数、线性、齐次 概念说明 :



1 . 常系数概念 : 常系数指的是 T ( n ) , T ( n − 1 ) T(n) , T(n-1)T(n),T(n−1) 这些 项之前的系数 , 都是常数 , 如 2 T ( n − 1 ) 2 T(n-1)2T(n−1) , T ( n − 1 ) T(n-1)T(n−1) 项前的系数是 常数 2 22 ;


之前栗子中介绍过的递推方程 , 如


汉诺塔递推方程 T ( n ) = 2 T ( n − 1 ) + 1 T(n) =2 T(n-1) + 1T(n)=2T(n−1)+1

插入排序递推方程 W ( n ) = W ( n − 1 ) + n − 1 W(n) = W(n-1) + n-1W(n)=W(n−1)+n−1

都是 常系数线性递推方程 , 不是齐次的 ;



2 . 线性概念 : 第 n nn 项是前面若干项 n − 1 n-1n−1 的 线性组合 , 没有指数等关系 , 因此成为线性 ;



3 . 齐次概念 : 在 T ( n ) T(n)T(n) 项之外没有其它元素 , 只有项 , 上述 T ( n ) = 2 T ( n − 1 ) + 1 T(n) =2 T(n-1) + 1T(n)=2T(n−1)+1 在项之外还有一个常数 1 11 , 该递推方程就不是齐次的 ; 如果改成 T ( n ) = 2 T ( n − 1 ) T(n) =2 T(n-1)T(n)=2T(n−1) , 该递推方程就是齐次的 ;






三、常系数线性齐次递推方程公式解法


1 . 特征根、通解、特解


特征根 : 根据原始的 递推方程 , 求出 特征根 ;


通解 : 利用 特征根 , 写出 通解 ;


特解 : 根据 通解 , 代入递推方程初值 , 获取针对这些初值的 特解 , 即针对该数列的解 ,




2 . 通解与特解的关系 :


递推方程与初值 : 递推方程的依赖关系 , 递推方程表达的不止一个数列 , 递推方程是 表达具有相同依赖关系的无穷数列 , 不同的递推方程初值 , 对应着不同的数列 , 递推方程 和 初值才能唯一确定一个数列 ;


递推方程、通解关系 : 通解 实际上是对递推方程 对应的 无穷数列 的共有的解 , 并 不能唯一确定一个数列 ;


特解、数列关系 : 通解的一些待定系数 , 要由初值确定 , 通解代入初值 , 得到的 特解 , 才能唯一确定给定数列 ;






四、常系数线性齐次递推方程公式解法内容概要


递推方程公式解法内容概要 :


特征方程与特征根

递推方程的解与特征根关系

解的线性性质

无重根下通解结构

有重根下通解结构


目录
相关文章
|
6月前
高等数学II-知识点(3)——广义积分、定积分几何应用、定积分求曲线弧长、常微分方程、可分离变量的微分方程、一阶微分方程-齐次方程、一阶线性微分方程
高等数学II-知识点(3)——广义积分、定积分几何应用、定积分求曲线弧长、常微分方程、可分离变量的微分方程、一阶微分方程-齐次方程、一阶线性微分方程
69 0
|
机器学习/深度学习 算法
专题六数值微积分与方程求解-2
专题六数值微积分与方程求解
106 0
|
算法 Serverless
专题六数值微积分与方程求解-1
专题六数值微积分与方程求解
121 0
|
算法
秒懂算法 | 递推方程求解方法
时间复杂度和空间复杂度表示为递推方程的两种求解方法。
370 1
秒懂算法 | 递推方程求解方法
|
机器学习/深度学习
【组合数学】递推方程 ( 常系数线性非齐次递推方程 的 非齐次部分是 多项式 与 指数 组合方式 | 通解的四种情况 )
【组合数学】递推方程 ( 常系数线性非齐次递推方程 的 非齐次部分是 多项式 与 指数 组合方式 | 通解的四种情况 )
224 0
|
机器学习/深度学习
【组合数学】递推方程 ( 常系数线性非齐次递推方程求解 | 递推方程标准型及通解 | 递推方程通解证明 )
【组合数学】递推方程 ( 常系数线性非齐次递推方程求解 | 递推方程标准型及通解 | 递推方程通解证明 )
205 0
【组合数学】递推方程 ( 有重根递推方程求解问题 | 问题提出 )
【组合数学】递推方程 ( 有重根递推方程求解问题 | 问题提出 )
197 0