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

2023-03-28 18:28:46 浏览数 (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) = b_k end{cases}

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

a_1 , a_2 , cdots , a_k

都是常数 ,

a_k not=0

;

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

0

;

上述称为

k

阶 常系数线性齐次递推方程 ;

b_0 , b_1, b_2 , cdots , b_k

是 递推方程的

k

个初值 ;

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

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

1 . 常系数概念 : 常系数指的是

T(n) , T(n-1)

这些 项之前的系数 , 都是常数 , 如

2 T(n-1)

,

T(n-1)

项前的系数是 常数

2

;

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

  • 汉诺塔递推方程
T(n) =2 T(n-1) 1
  • 插入排序递推方程
W(n) = W(n-1) n-1

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

2 . 线性概念 : 第

n

项是前面若干项

n-1

的 线性组合 , 没有指数等关系 , 因此成为线性 ;

3 . 齐次概念 : 在

T(n)

项之外没有其它元素 , 只有项 , 上述

T(n) =2 T(n-1) 1

在项之外还有一个常数

1

, 该递推方程就不是齐次的 ; 如果改成

T(n) =2 T(n-1)

, 该递推方程就是齐次的 ;

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

1 . 特征根、通解、特解

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

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

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

2 . 通解与特解的关系 :

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

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

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

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

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

  • 特征方程与特征根
  • 递推方程的解与特征根关系
  • 解的线性性质
  • 无重根下通解结构
  • 有重根下通解结构
数学

0 人点赞