遞迴關係式

在數學上，递推关系（recurrence relation），也就是差分方程（difference equation），是一種递推地定義一個序列的方程式：序列的每一項目是定義為前一項的函數。

像戶口調查映射（logistic map）即為递推关系

$x_{n+1}=rx_{n}(1-x_{n})\,$

某些簡單定義的遞迴關係式可能會表現出非常複雜的（混沌的）性質，他們屬於數學中的非線性分析領域。

所謂解一個遞迴關係式，也就是求其解析解，即關於n的非遞迴函數。

遞迴關係式的例子

等差數列

$x_{0}=1,x_{n+1}=x_{n}+2$為等差數列$1,3,5,7,.....$

一般地，$x_{0}=a,x_{n+1}=x_{n}+d$為等差數列，其中$a$為首項，$d$為公差。

等比數列

$x_{0}=1,x_{n+1}=2x_{n}$為等比數列$1,2,4,8,.....$

一般地，$a\neq 0$且$r\neq 0$，$x_{0}=a,x_{n+1}=rx_{n}$為等比數列，其中$a$為首項，$r$為公比。

階乘

$0!=1$

$n!=n\times (n-1)!$

因此最小的幾個階乘為$1,1,2,6,24,120,720,5040,.....$、

平方和

已知$x+{\frac {1}{x}}=5$，求$x^{10}+{\frac {1}{x^{10}}}=$?

$x^{2}+x^{-2}=(x+x^{-1})^{2}-2\cdot x\cdot x^{-1}=5^{2}-2=23$

$x^{3}+x^{-3}=(x+x^{-1})^{3}-3\cdot x\cdot x^{-1}(x+x^{-1})=5^{3}-3\cdot 5=110$

$x^{5}+x^{-5}=(x^{2}+x^{-2})\cdot (x^{3}+x^{-3})-(x+x^{-1})=23\cdot 210-5=2525$

$x^{10}+x^{-10}=(x^{5}+x^{-5})^{2}-2=2525^{2}-2=6375623$

遞迴關係

若$x_{k}=x^{k}+x^{-k}$，則

$x_{1}=x_{1}$，$x_{2}=(x_{1})^{2}-2$

$x_{3}=x_{1}\cdot x_{2}-x_{1}$，$x_{4}=(x_{2})^{2}-2$

$x_{5}=x_{2}\cdot x_{3}-x_{1}$，$x_{6}=(x_{3})^{2}-2$

$x_{7}=x_{3}\cdot x_{4}-x_{1}.....$

常係數線性齊次遞迴關係式

線性字眼的意思是序列的每一項目是被定義為前一項的一種線性函數。係數和常數可能視n而定，甚至是非線性地。

一種特別的情況是當係數並不依照n而定。

齊次意思為关系的常數項為零。

為了要得到線性遞迴唯一的解，必須有一些起始條件，就是序列的第一個數字無法依照該序列的其他數字而定時，且必須設定為某些數值。

解線性遞迴關係式

遞迴關係式的解通常是由系統的方法中找出來，通常藉由使用生成函數（形式冪級數）或藉由觀察rⁿ是一種對r的特定數值之解的事實。

二階遞迴關係式的形式：

$a_{n}=Aa_{n-1}+Ba_{n-2}\,$

我們擁有解為rⁿ：

$r^{n}=Ar^{n-1}+Br^{n-2}\,$

兩邊除以$r^{n-2}$我們可以得到：

$r^{2}=Ar+B\,$

$r^{2}-Ar-B=0\,$

這就是遞迴關係式的特徵方程。解出r可獲得兩個根（roots）$\lambda _{1},\lambda _{2}$，且如果兩個根是不同的，我們可得到解為

$a_{n}=C\lambda _{1}^{n}+D\lambda _{2}^{n}\,$

而如果兩個根是相同的（當A²+4B=0），我們得到

$a_{n}=C\lambda ^{n}+Dn\lambda ^{n}\,$

C和D都是常數。

換句話說，將這種$a_{n}=Aa_{n-1}+B$形式的方程式，用2代入n後，就得到上述的$r^{2}=Ar+B$。常數"C"和"D"可以從"邊界條件（side conditions）"中得到，通常會像是「已知$a_{0}=c_{1}$, $a_{1}=c_{2}$」。

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

斐波那契数是使用一種線性遞迴關係式來定義：

$F_{0}=0\,$

$F_{1}=1\,$

$F_{n}=F_{n-1}+F_{n-2}\,$

設若：$F_{n}/F_{n-1}\,$當n趨於無限大之極限值存在，則其值為$1+{\sqrt {5}} \over 2\,$ $=\Phi$恰為黃金分割值，1.618....，另一值則為0.618....，兩值互為倒數，也就是說1.618....分之1=0.618....，反之亦然。

$F_{n}={\Phi ^{n} \over {\sqrt {5}}}-{(1-\Phi )^{n} \over {\sqrt {5}}}$

起始條件為：

$F_{0}=0\,$

$F_{1}=1\,$

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

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

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

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

时域经典法求解

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

$\sum _{k=0}^{N}a_{k}y(n-k)=\sum _{r=0}^{M}b_{r}x(n-r)$

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

$\sum _{k=0}^{N}a_{k}y(n-k)=0$

则特征方程为：

$\sum _{k=0}^{N}a_{k}\alpha ^{N-k}=0$

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

$y_{h}(n)=\sum _{i=1}^{N}C_{i}\alpha _{i}^{n}$

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

$y_{h}(n)=\sum _{i=1}^{K}n^{K-i}\alpha _{1}^{n}$

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

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

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

$y_{p}(n)=A_{0}n^{k}+A_{1}n^{k-1}+\cdots +A_{k}$

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

当a不是特征根时

$y_{p}(n)=Aa^{n}$

当a是特征根时

$y_{p}(n)=(A_{1}n+A_{0})a^{n}$

当a为r重根时

$y_{p}(n)=(A_{r}n^{r}+A_{r-1}n^{r-1}+\cdots +A_{1}n+A_{0})a^{n}$

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

例子

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

$a_{n+1}=2a_{n}+3^{n}+5n\,$

对应的齐次递推关系

$b_{n+1}=2b_{n}\,$

的齐次解是：

$b_{n}=c_{1}2^{n}\,$

我们猜测特解的形式为：

$a_{n}=c_{2}3^{n}+c_{3}n+c_{4}\,$

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

$c_{2}3^{n+1}+c_{3}(n+1)+c_{4}=2(c_{2}3^{n}+c_{3}n+c_{4})+3^{n}+5n\,$

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

$3c_{2}=2c_{2}+1\,$

$c_{2}=1\,$

比较等式两端的$n$项的系数，可得：

$c_{3}=2c_{3}+5\,$

$c_{3}=-5\,$

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

$c_{3}+c_{4}=2c_{4}\,$

$c_{4}=c_{3}=-5\,$

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

$a_{n}=c_{1}2^{n}+3^{n}-5n-5\,$

與微分方程的關係

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

$y'(t)=f(t,y(t)),\qquad y(t_{0})=y_{0},\qquad \qquad$

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

$y_{n+1}=y_{n}+hf(t_{n},y_{n})$

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

參考

• 递归
• 差分
• 主定理
• 圆点段证明（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.