遞迴關係式

遞推關係（英語：Recurrence relation），在數學上也就是差分方程（英語：Difference equation），是一種遞推地定義一個序列的方程式：序列的每一項目是定義為前若干項的函數。

像斐波那契數即為遞推關係

$x_{n+2}=x_{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_{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}$

$\cdots \cdots$

$x_{2k}=(x_{k})^{2}-2$

$x_{2k+1}=x_{k}\cdot x_{k+1}-x_{1}$

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

線性（英語：Linear）的意思是序列的每一項目是被定義為前一項的一種線性函數。係數和常數可能視$n$而定，甚至是非線性地。

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

齊次（英語：Homogenous）的意思為關係的常數項為零。

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

解線性遞迴關係式

線性遞迴關係式的解通常是由系統的方法中找出來，通常藉由使用生成函數（形式冪級數）或藉由觀察$r^{n}$是一種對$r$的特定數值之解的事實。且因關係式為線性方程，另一種方法是以矩陣表示此一遞迴關係式，並透過矩陣對角化等技巧求出關係式的通項。

二階遞迴關係式的形式：

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

我們擁有解為$r^{n}$：

$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^{2}+4B=0$），我們得到

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

$C$和$D$都是常數。以上結果皆可由直接代入得證，或以矩陣對角化的技巧推導出。

換句話說，將這種$a_{n}=Aa_{n-1}+Ba_{n-2}$形式的方程式，用$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....$，兩值互為倒數，也就是說${\frac {1}{1.618....}}=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.