递推关系式的例子

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

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

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

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

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

解线性递推关系式

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

二阶递推关系式的形式：

我们拥有解为r：

两边除以rn− − -->2{\displaystyle r^{n-2}}我们可以得到：

这就是递推关系式的特征方程。解出r可获得两个根（roots）λ λ -->1,λ λ -->2{\displaystyle \lambda _{1},\lambda _{2}}，且如果两个根是不同的，我们可得到解为

而如果两个根是相同的（当A+4B=0），我们得到

C和D都是常数。

换句话说，将这种an=Aan− − -->1+B{\displaystyle a_{n}=Aa_{n-1}+B}形式的方程式，用2代入n后，就得到上述的r2=Ar+B{\displaystyle r^{2}=Ar+B}。常数"C"和"D"可以从"边界条件（side conditions）"中得到，通常会像是“已知a0=c1{\displaystyle a_{0}=c_{1}}, a1=c2{\displaystyle a_{1}=c_{2}}”。

范例：斐波那契数（Fibonacci Number）

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

设若：Fn/Fn− − -->1{\displaystyle F_{n}/F_{n-1}\,}当n趋于无限大之极限值存在，则其值为1+52{\displaystyle 1+{\sqrt {5}} \over 2\,}=Φ Φ -->{\displaystyle =\Phi }恰为黄金分割值，1.618....，另一值则为0.618....，两值互为倒数，也就是说1.618....分之1=0.618....，反之亦然。

起始条件为：

因此，斐波那契数的序列为：

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

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

时域经典法求解

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

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

则特征方程为：

当特征根非重根时，齐次解为：

当特征根为重根时，若α α -->1{\displaystyle \alpha _{1}}为特征方程的K{\displaystyle K}重根，齐次解为：

特解yp(n)=D(n){\displaystyle y_{p}(n)=D(n)}的形式由激励函数x(n){\displaystyle x(n)}的形式决定。

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

方程右方出现nk{\displaystyle n_{k}}的形式，则特解选择

当方程右方出现an{\displaystyle a^{n}}的形式，则特解选择

当a不是特征根时

当a是特征根时

当a为r重根时

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

例子

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

对应的齐次递推关系

的齐次解是：

我们猜测特解的形式为：

代入原递推关系中，我们便得到：

比较等式两端的3n{\displaystyle 3^{n}}项的系数，可得：

比较等式两端的n{\displaystyle n}项的系数，可得：

比较等式两端的常数项，可得：

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

与微分方程的关系

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

如采用欧拉法和步长h，可以通过如下递归关系计算y0=y(t0){\displaystyle y_{0}=y(t_{0})}, y1=y(t0+h),{\displaystyle y_{1}=y(t_{0}+h),}y2=y(t0+2h),...{\displaystyle y_{2}=y(t_{0}+2h),...}

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

参考

递归

差分

主定理

圆点段证明（Circle points segments proof）

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。