计算机科学

首页 > 计算机科学

递推关系式

2018-08-30 09:59:37     所属分类:计算理论

在数学上,递推关系(recurrence relation),也就是差分方程(difference equation),是一种递推地定义一个序列的方程:序列的每一项目是定义为前一项的函数。

像户口调查映射(logistic map)即为递推关系

某些简单定义的递推关系式可能会表现出非常复杂的(混沌的)性质,他们属于数学中的非线性分析领域。

所谓解一个递推关系式,也就是求其解析解,即关于n的非递归函数。

目录

  • 1 递推关系式的例子
    • 1.1 等差数列
    • 1.2 等比数列
    • 1.3 阶乘
    • 1.4 倒数和
  • 2 常系数线性齐次递推关系式
  • 3 解线性递推关系式
  • 4 范例:斐波那契数(Fibonacci Number)
  • 5 常系数非齐次线性递推关系
    • 5.1 时域经典法求解
    • 5.2 例子
  • 6 与微分方程的关系
  • 7 参考
  • 8 外部链接

递推关系式的例子

等差数列

为等差数列
一般地,为等差数列,其中为首项,为公差。

等比数列

为等比数列
一般地,为等比数列,其中为首项,为公比。

阶乘

因此最小的几个阶乘为

倒数和

,则

常系数线性齐次递推关系式

线性字眼的意思是序列的每一项目是被定义为前一项的一种线性函数。系数和常数可能视n而定,甚至是非线性地。

一种特别的情况是当系数并不依照n而定。

齐次意思为关系的常数项为零。

为了要得到线性递归唯一的解,必须有一些起始条件,就是序列的第一个数字无法依照该序列的其他数字而定时,且必须设定为某些数值。

解线性递推关系式

递推关系式的解通常是由系统的方法中找出来,通常借由使用生成函数(形式幂级数)或借由观察rn是一种对r的特定数值之解的事实。

二阶递推关系式的形式:

我们拥有解为rn

两边除以我们可以得到:

这就是递推关系式的特征方程。解出r可获得两个根(roots),且如果两个根是不同的,我们可得到解为

而如果两个根是相同的(当A2+4B=0),我们得到

CD都是常数。

换句话说,将这种形式的方程,用2代入n后,就得到上述的。常数"C"和"D"可以从"边界条件(side conditions)"中得到,通常会像是“已知, ”。

范例:斐波那契数(Fibonacci Number)

斐波那契数是使用一种线性递推关系式来定义:

设若:当n趋于无限大之极限值存在,则其值为 恰为黄金分割值,1.618....,另一值则为0.618....,两值互为倒数,也就是说1.618....分之1=0.618....,反之亦然。

起始条件为:

因此,斐波那契数的序列为:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ...

常系数非齐次线性递推关系

对于常系数非齐次线性递推关系,我们可以用待定系数法英语Method of undetermined coefficients来求出它的一个特解,而它的通解就是这个特解与对应的齐次递推关系的通解的和。也可以使用迭代法求解,但只能得到确切的数值解,不能直接以解析式作答,该方法可利用计算机求解。

时域经典法求解

一般情况下,常系数线性差分方程可以写作:

则对应的齐次方程形式为:

则特征方程为:

当特征根非重根时,齐次解为:

当特征根为重根时,若为特征方程的重根,齐次解为:

特解的形式由激励函数的形式决定。

一般情况,当激励函数x(n)代入方程。

方程右方出现的形式,则特解选择

当方程右方出现的形式,则特解选择

当a不是特征根时

当a是特征根时

当a为r重根时

将特解带入原方程,求出待定系数。根据边界条件,可求出齐次节待定系数。

例子

我们用待定系数法来解以下的常系数非齐次线性递推关系:

对应的齐次递推关系

的齐次解是:

我们猜测特解的形式为:

代入原递推关系中,我们便得到:

比较等式两端的项的系数,可得:

比较等式两端的项的系数,可得:

比较等式两端的常数项,可得:

因此原递推关系的通解为:

与微分方程的关系

数值求解常微分方程时,经常会遇到递归关系。例如,求解如下初值问题时

如采用欧拉法和步长h,可以通过如下递归关系计算,

线性一阶微分方程组可以用离散化条目中介绍的方法解析地精确离散化。

参考

  • 递归
  • 差分
  • 主定理
  • 圆点段证明(Circle points segments proof)

外部链接

  • Difference and Functional Equations: Exact Solutions at EqWorld - The World of Mathematical Equations.
  • Difference and Functional Equations: Methods at EqWorld - The World of Mathematical Equations.

下一篇:自指
相关推荐