查看“︁遞迴關係式”︁的源代码

{{NoteTA
|T=zh-hans:递推关系式; zh-hant:遞迴關係式;
|G1=Math}}
'''递推关系'''（{{lang-en|Recurrence relation}}），是一種[[遞迴|递推地]]定義一個序列的[[方程|方程式]]：序列的每一項目是定義為前若干項的[[函数|函數]]。

像[[斐波那契数列|斐波那契数]]即為递推关系
:<math>x_{n+2} = x_{n+1} + x_{n}</math>

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

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

==遞迴關係式的例子==
===[[等差數列]]===
:<math>x_0=1,x_{n+1}=x_n+2</math>為等差數列<math>1,3,5,7,.....</math>
:一般地，<math>x_0=a,\ x_{n+1}=x_n+d</math>為等差數列，其中<math>a</math>為首項，<math>d</math>為公差。
===[[等比數列]]===
:<math>x_0=1,x_{n+1}=2x_n</math>為等比數列<math>1,2,4,8,.....</math>
:一般地，<math>a \ne 0</math>且<math>r \ne 0</math>，<math>x_0=a,\ x_{n+1}=rx_n</math>為等比數列，其中<math>a</math>為首項，<math>r</math>為公比。
===[[階乘]]===
:<math>0!=1</math>
:<math>n!=n \times (n-1)!</math>
:因此最小的幾個階乘為<math>1,1,2,6,24,120,720,5040,.....</math>、
===[[倒数]]和===
:設<math>x_k=x^k+x^{-k}</math>,<math>x_1=x_1</math>，則：
:<math>x_2=(x_1)^2-2</math>
:<math>x_3=x_1 \cdot x_2-x_1</math>
:<math>x_4=(x_2)^2-2</math>
:<math>x_5=x_2 \cdot x_3-x_1</math>
:<math>x_6=(x_3)^2-2</math>
:<math>x_7=x_3 \cdot x_4-x_1</math>
:<math>\cdots \cdots</math>
:<math>x_{2k}=(x_k)^2-2</math>
:<math>x_{2k+1}=x_k \cdot x_{k+1}-x_1</math>

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

[[線性關係|線性]]（{{lang-en|Linear}}）的意思是序列的每一項目是被定義為前一項的一種線性函數。係數和常數可能視<math>n</math>而定，甚至是非線性地。

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

[[齊次多項式|齊次]]（{{lang-en|Homogenous}}）的意思為关系的常數項為零。

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

== 解線性遞迴關係式 ==

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

二階遞迴關係式的形式：

:<math>a_{n}=Aa_{n-1}+Ba_{n-2} \,</math>

其解為<math>r^n</math>：

:<math>r^{n}=Ar^{n-1}+Br^{n-2} \,</math>

兩邊除以<math>r^{n-2}</math>可以得到：

:<math>r^2=Ar+B \,</math>
:<math>r^2-Ar-B=0 \,</math>

這就是遞迴關係式的'''特徵方程'''。解出<math>r</math>可獲得兩個根（{{lang-en|Roots}}）<math>\lambda_1, \lambda_2 </math>，且如果兩個根是不同的，可得到解為

:<math>a_n = C\lambda_1^n+D\lambda_2^n \,</math>

而如果兩個根是相同的（當<math>A^2+4B=0</math>），得到

:<math>a_n = C\lambda^n+Dn\lambda^n \,</math>

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

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

== 範例：斐波那契数==

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

:<math>F_{0} = 0 \,</math>
:<math>F_{1} = 1 \,</math>
:<math>F_{n} = F_{n-1}+F_{n-2} \,</math>

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

:<math>F_n = {\Phi^n \over \sqrt{5}} - {(1-\Phi)^n \over \sqrt{5}}</math>

起始條件為：

:<math>F_{0} = 0 \,</math>
:<math>F_{1} = 1 \,</math>

因此，斐波那契数的序列為：
:<math>0,1,1,2,3,5,8,13,21,34,55,89...</math>

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

===时域经典法求解===<!--此为信号与系统中的名词-->
一般情况下，常系数线性差分方程可以写作：

:<math>\sum_{k=0}^N a_k y(n-k)=\sum_{r=0}^M b_r x(n-r)</math>

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

:<math>\sum_{k=0}^N a_k y(n-k)=0</math>

则特征方程为：

:<math>\sum_{k=0}^N a_k \alpha^{N-k}=0</math>

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

:<math>y_h(n)=\sum_{i=1}^N C_i \alpha_i^n</math>

当特征根为重根时，若<math>\alpha_1</math>为特征方程的<math>K</math>重根，齐次解为：

:<math>y_h(n)=\sum_{i=1}^K n^{K-i} \alpha_1^n</math>

特解<math>y_p(n)=D(n)</math>的形式由激励函数<math>x(n)</math>的形式决定。

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

方程右方出现<math>n^k</math>的形式，则特解选择

:<math>y_p(n)=A_0 n^k + A_1 n^{k-1} + \cdots + A_k</math>

当方程右方出现<math>a^n</math>的形式，则特解选择

当<math>a</math>不是特征根时

:<math> y_p(n)=Aa^n </math>

当<math>a</math>是特征根时

:<math> y_p(n)=(A_1n + A_0)a^n </math>

当<math>a</math>为<math>r</math>重根时

:<math>y_p(n)=(A_r n^r + A_{r-1} n^{r-1} + \cdots + A_1 n + A_0)a^n</math>

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

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

:<math>a_{n+1} = 2a_n + 3^n + 5n\,</math>

对应的齐次递推关系

:<math>b_{n+1} = 2b_n\,</math>

的齐次解是：

:<math>b_n = c_1 2^n\,</math>

我们猜测特解的形式为：

:<math>a_n = c_2 3^n + c_3 n + c_4\,</math>

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

:<math>c_2 3^{n+1} + c_3 (n+1) + c_4 = 2(c_2 3^n + c_3 n + c_4) + 3^n + 5n\,</math>

比较等式两端的<math>3^n</math>项的系数，可得：

:<math>3c_2 = 2c_2 + 1\,</math>

:<math>c_2 = 1\,</math>

比较等式两端的<math>n</math>项的系数，可得：

:<math>c_3 = 2c_3 + 5\,</math>

:<math>c_3 = -5\,</math>

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

:<math>c_3 + c_4 = 2c_4\,</math>

:<math>c_4 = c_3 = -5\,</math>

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

:<math>a_n = c_1 2^n + 3^n - 5n - 5\,</math>

== 與微分方程的關係 ==

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

:<math>y'(t) = f(t,y(t)), \qquad y(t_0)=y_0, \qquad\qquad</math> 

如采用[[欧拉法]]和步长''h''，可以通过如下递归关系计算<math>y_0=y(t_0)</math>, <math>y_1=y(t_0+h),</math> <math>y_2=y(t_0+2h),...</math>
:<math> y_{n+1} = y_n + hf(t_n,y_n)</math>

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

== 參考 ==

* [[递归]]
* [[差分]]
* {{鏈解|主定理}}
* [[圆点段证明]]（{{lang-en|Circle points segments proof}}）
* {{鏈解|母函数}}

== 外部連結 ==
* [http://eqworld.ipmnet.ru/en/solutions/fe.htm Difference and Functional Equations: Exact Solutions] {{Wayback|url=http://eqworld.ipmnet.ru/en/solutions/fe.htm |date=20050623013031 }} at EqWorld - The World of Mathematical Equations.
* [http://eqworld.ipmnet.ru/en/education/edu-fe.htm Difference and Functional Equations: Methods] {{Wayback|url=http://eqworld.ipmnet.ru/en/education/edu-fe.htm |date=20070630081433 }} at EqWorld - The World of Mathematical Equations.

{{Authority control}}
[[Category:計算理論|D]]
[[Category:代数|D]]
[[Category:方程]]