njtynhj

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

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

xn+1=rxn(1−xn)displaystyle x_n+1=rx_n(1-x_n),

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

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

遞迴關係式的例子

等差數列

x0=1,xn+1=xn+2displaystyle x_0=1,x_n+1=x_n+2為等差數列1,3,5,7,.....displaystyle 1,3,5,7,.....

一般地，x0=a,xn+1=xn+ddisplaystyle x_0=a,x_n+1=x_n+d為等差數列，其中adisplaystyle a為首項，ddisplaystyle d為公差。

等比數列

x0=1,xn+1=2xndisplaystyle x_0=1,x_n+1=2x_n為等比數列1,2,4,8,.....displaystyle 1,2,4,8,.....

一般地，a≠0displaystyle aneq 0且r≠0displaystyle rneq 0，x0=a,xn+1=rxndisplaystyle x_0=a,x_n+1=rx_n為等比數列，其中adisplaystyle a為首項，rdisplaystyle r為公比。

階乘

0!=1displaystyle 0!=1

n!=n×(n−1)!displaystyle n!=ntimes (n-1)!

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

倒数和

設xk=xk+x−kdisplaystyle x_k=x^k+x^-k，則

x1=x1displaystyle x_1=x_1

x2=(x1)2−2displaystyle x_2=(x_1)^2-2

x3=x1⋅x2−x1displaystyle x_3=x_1cdot x_2-x_1

x4=(x2)2−2displaystyle x_4=(x_2)^2-2

x5=x2⋅x3−x1displaystyle x_5=x_2cdot x_3-x_1

x6=(x3)2−2displaystyle x_6=(x_3)^2-2

x7=x3⋅x4−x1displaystyle x_7=x_3cdot x_4-x_1

⋯⋯displaystyle cdots cdots

x2k=(xk)2−2displaystyle x_2k=(x_k)^2-2

x2k+1=xk⋅xk+1−x1displaystyle x_2k+1=x_kcdot x_k+1-x_1

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

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

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

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

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

解線性遞迴關係式

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

二階遞迴關係式的形式：

an=Aan−1+Ban−2displaystyle a_n=Aa_n-1+Ba_n-2,

我們擁有解為rⁿ：

rn=Arn−1+Brn−2displaystyle r^n=Ar^n-1+Br^n-2,

兩邊除以rn−2displaystyle r^n-2我們可以得到：

r2=Ar+Bdisplaystyle r^2=Ar+B,

r2−Ar−B=0displaystyle r^2-Ar-B=0,

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

an=Cλ1n+Dλ2ndisplaystyle a_n=Clambda _1^n+Dlambda _2^n,

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

an=Cλn+Dnλndisplaystyle a_n=Clambda ^n+Dnlambda ^n,

C和D都是常數。

換句話說，將這種an=Aan−1+Bdisplaystyle a_n=Aa_n-1+B形式的方程式，用2代入n後，就得到上述的r2=Ar+Bdisplaystyle r^2=Ar+B。常數"C"和"D"可以從"邊界條件（side conditions）"中得到，通常會像是「已知a0=c1displaystyle a_0=c_1, a1=c2displaystyle a_1=c_2」。

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

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

F0=0displaystyle F_0=0,

F1=1displaystyle F_1=1,

Fn=Fn−1+Fn−2displaystyle F_n=F_n-1+F_n-2,

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

Fn=Φn5−(1−Φ)n5displaystyle F_n=Phi ^n over sqrt 5-(1-Phi )^n over sqrt 5

起始條件為：

F0=0displaystyle F_0=0,

F1=1displaystyle F_1=1,

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

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

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

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

时域经典法求解

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

∑k=0Naky(n−k)=∑r=0Mbrx(n−r)displaystyle sum _k=0^Na_ky(n-k)=sum _r=0^Mb_rx(n-r)

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

∑k=0Naky(n−k)=0{displaystyle sum _k=0^Na_ky(n-k)=0

则特征方程为：

∑k=0NakαN−k=0displaystyle sum _k=0^Na_kalpha ^N-k=0

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

yh(n)=∑i=1NCiαindisplaystyle y_h(n)=sum _i=1^NC_ialpha _i^n

当特征根为重根时，若α1displaystyle alpha _1为特征方程的Kdisplaystyle K重根，齐次解为：

yh(n)=∑i=1KnK−iα1ndisplaystyle y_h(n)=sum _i=1^Kn^K-ialpha _1^n

特解yp(n)=D(n)displaystyle y_p(n)=D(n)的形式由激励函数x(n)displaystyle x(n)的形式决定。

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

方程右方出现nkdisplaystyle n^k的形式，则特解选择

yp(n)=A0nk+A1nk−1+⋯+Akdisplaystyle y_p(n)=A_0n^k+A_1n^k-1+cdots +A_k

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

当a不是特征根时

yp(n)=Aandisplaystyle y_p(n)=Aa^n

当a是特征根时

yp(n)=(A1n+A0)andisplaystyle y_p(n)=(A_1n+A_0)a^n

当a为r重根时

yp(n)=(Arnr+Ar−1nr−1+⋯+A1n+A0)andisplaystyle y_p(n)=(A_rn^r+A_r-1n^r-1+cdots +A_1n+A_0)a^n

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

例子

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

an+1=2an+3n+5ndisplaystyle a_n+1=2a_n+3^n+5n,

对应的齐次递推关系

bn+1=2bndisplaystyle b_n+1=2b_n,

的齐次解是：

bn=c12ndisplaystyle b_n=c_12^n,

我们猜测特解的形式为：

an=c23n+c3n+c4displaystyle a_n=c_23^n+c_3n+c_4,

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

c23n+1+c3(n+1)+c4=2(c23n+c3n+c4)+3n+5ndisplaystyle c_23^n+1+c_3(n+1)+c_4=2(c_23^n+c_3n+c_4)+3^n+5n,

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

3c2=2c2+1displaystyle 3c_2=2c_2+1,

c2=1displaystyle c_2=1,

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

c3=2c3+5displaystyle c_3=2c_3+5,

c3=−5displaystyle c_3=-5,

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

c3+c4=2c4displaystyle c_3+c_4=2c_4,

c4=c3=−5displaystyle c_4=c_3=-5,

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

an=c12n+3n−5n−5displaystyle a_n=c_12^n+3^n-5n-5,

與微分方程的關係

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

y′(t)=f(t,y(t)),y(t0)=y0,displaystyle y'(t)=f(t,y(t)),qquad y(t_0)=y_0,qquad qquad

如采用欧拉法和步长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),...

yn+1=yn+hf(tn,yn)displaystyle 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.