在
数学上,递推关系(recurrence relation),也就是差分方程(difference equation),是一种递推地定义一个序列的方程式:序列的每一项目是定义为前一项的函数。
定义
递推关系(recurrence relation),也就是差分方程(difference equation),是一种递推地定义一个序列的方程式:序列的每一项目是定义为前一项的函数。
举个例子(户口调查映射(logistic map)):
某些简单定义的递推关系式可能会表现出非常复杂的(混沌的)性质,他们属于数学中的非线性分析领域。
所谓解一个递推关系式,也就是求其
解析解,即关于n的非递归函数。
常系数线性齐次递推关系式
线性字眼的意思是序列的每一项目是被定义为前一项的一种线性函数。系数和常数可能视n而定,甚至是非线性地。
一种特别的情况是当系数并不依照n而定。
为了要得到线性递归唯一的解,必须有一些起始条件,就是序列的第一个数字无法依照该序列的其他数字而定时,且必须设定为某些数值。
性质
(1)常系数线性齐次递推关系式
线性字眼的意思是序列的每一项目是被定义为前一项的一种线性函数。系数和常数可能视 n 而定,甚至是非线性地。
一种特别的情况是当系数并不依照 n 而定。
为了要得到线性递归唯一的解,必须有一些起始条件,就是序列的第一个数字无法依照该序列的其他数字而定时,且必须设定为某些数值。
解线性递推关系式
递推关系式的解通常是由系统的方法中找出来,通常借由使用
生成函数(
形式幂级数)或借由观察r是一种对r的特定数值之解的事实。
二阶递推关系式的形式:
我们拥有解为r:
两边除以我们可以得到:
这就是递推关系式的特征方程。解出r可获得两个根(roots),且如果两个根是不同的,我们可得到解为
而如果两个根是相同的(当A+4B=0),我们得到
C和D都是常数。
(2)常系数线性齐次递推关系式
对于常系数非齐次线性递推关系,我们可以用
待定系数法来求出它的一个特解,而它的通解就是这个特解与对应的齐次递推关系的通解的和。也可以使用
迭代法求解,但只能得到确切的数值解,不能直接以解析式作答,该方法可利用计算机求解。
时域经典法求解:
一般情况下,常系数线性差分方程可以写作:
则对应的齐次方程形式为:
则特征方程为:
当特征根非重根时,齐次解为:
当特征根为重根时,若为特征方程的重根,齐次解为:
特解的形式由激励函数的形式决定。
一般情况,当激励函数x(n)代入方程。
方程右方出现的形式,则特解选择
当方程右方出现的形式,则特解选择
当a不是特征根时
当a是特征根时
当a为r重根时
将特解带入原方程,求出待定系数。根据边界条件,可求出齐次节待定系数。
(3)与差分方程的关系
数值求解
常微分方程时,经常会遇到递归关系。例如,求解如下
初值问题时
线性一阶微分方程组可以用
离散化条目中介绍的方法解析地精确离散化。
应用
解线性递推关系式范例
斐波那契数(Fibonacci Number)
设若:当n趋于无限大之极限值存在,则其值为恰为
黄金分割值,1.618....,另一值则为0.618....,两值互为倒数,也就是说1.618....分之1=0.618....,反之亦然。
起始条件为:
因此,斐波那契数的序列为: