遞迴關係式

维基百科,自由的百科全书
跳转至: 导航搜索

數學上,递推关系(recurrence relation),也就是差分方程(difference equation),是一種递推地定義一個序列的方程式:序列的每一項目是定義為前一項的函數。

舉個例子(戶口調查映射(logistic map)):

x_{n+1} = r x_n (1 - x_n) \,

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

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

常係數線性齊次遞迴關係式[编辑]

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

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

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

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

解線性遞迴關係式[编辑]

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

二階遞迴關係式的形式:

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

我們擁有解為rn

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 \,

而如果兩個根是相同的(當A2+4B=0),我們得到

a_n = C\lambda^n+Dn\lambda^n \,

CD 都是常數。

換句話說,將這種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_1n + 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).

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

參考[编辑]

外部連結[编辑]