Mixing
遞迴關係式
在數學上，递推关系（recurrence relation），也就是差分方程（difference equation），是一種递推地定義一個序列的方程式：序列的每一項目是定義為前一項的函數。
像戶口調查映射（logistic map）即為递推关系
- xn+1=rxn(1−xn){displaystyle x_{n+1}=rx_{n}(1-x_{n}),}
某些簡單定義的遞迴關係式可能會表現出非常複雜的（混沌的）性質，他們屬於數學中的非線性分析領域。
所謂解一個遞迴關係式，也就是求其解析解，即關於n的非遞迴函數。
目录
1 遞迴關係式的例子
1.1 等差數列
1.2 等比數列
1.3 階乘
1.4 倒数和
2 常係數線性齊次遞迴關係式
3 解線性遞迴關係式
4 範例：斐波那契数（Fibonacci Number）
5 常系数非齐次线性递推关系
5.1 时域经典法求解
5.2 例子
6 與微分方程的關係
7 參考
8 外部連結
遞迴關係式的例子
等差數列
x0=1,xn+1=xn+2{displaystyle x_{0}=1,x_{n+1}=x_{n}+2}為等差數列1,3,5,7,.....{displaystyle 1,3,5,7,.....}
- 一般地，x0=a,xn+1=xn+d{displaystyle x_{0}=a,x_{n+1}=x_{n}+d}
為等差數列，其中a{displaystyle a}
為首項，d{displaystyle d}
為公差。
等比數列
x0=1,xn+1=2xn{displaystyle x_{0}=1,x_{n+1}=2x_{n}}為等比數列1,2,4,8,.....{displaystyle 1,2,4,8,.....}
- 一般地，a≠0{displaystyle aneq 0}
且r≠0{displaystyle rneq 0}
，x0=a,xn+1=rxn{displaystyle x_{0}=a,x_{n+1}=rx_{n}}
為等比數列，其中a{displaystyle a}
為公比。
階乘
- 0!=1{displaystyle 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−k{displaystyle x_{k}=x^{k}+x^{-k}}
，則
- x1=x1{displaystyle x_{1}=x_{1}}
- x2=(x1)2−2{displaystyle x_{2}=(x_{1})^{2}-2}
- x3=x1⋅x2−x1{displaystyle x_{3}=x_{1}cdot x_{2}-x_{1}}
- x4=(x2)2−2{displaystyle x_{4}=(x_{2})^{2}-2}
- x5=x2⋅x3−x1{displaystyle x_{5}=x_{2}cdot x_{3}-x_{1}}
- x6=(x3)2−2{displaystyle x_{6}=(x_{3})^{2}-2}
- x7=x3⋅x4−x1{displaystyle x_{7}=x_{3}cdot x_{4}-x_{1}}
- ⋯⋯{displaystyle cdots cdots }
- x2k=(xk)2−2{displaystyle x_{2k}=(x_{k})^{2}-2}
- x2k+1=xk⋅xk+1−x1{displaystyle x_{2k+1}=x_{k}cdot x_{k+1}-x_{1}}
常係數線性齊次遞迴關係式
線性字眼的意思是序列的每一項目是被定義為前一項的一種線性函數。係數和常數可能視n而定，甚至是非線性地。
一種特別的情況是當係數並不依照n而定。
齊次意思為关系的常數項為零。
為了要得到線性遞迴唯一的解，必須有一些起始條件，就是序列的第一個數字無法依照該序列的其他數字而定時，且必須設定為某些數值。
解線性遞迴關係式
遞迴關係式的解通常是由系統的方法中找出來，通常藉由使用生成函數（形式冪級數）或藉由觀察rn是一種對r的特定數值之解的事實。
二階遞迴關係式的形式：
- an=Aan−1+Ban−2{displaystyle a_{n}=Aa_{n-1}+Ba_{n-2},}
我們擁有解為rn：
- rn=Arn−1+Brn−2{displaystyle r^{n}=Ar^{n-1}+Br^{n-2},}
兩邊除以rn−2{displaystyle r^{n-2}}
- r2=Ar+B{displaystyle r^{2}=Ar+B,}
- r2−Ar−B=0{displaystyle r^{2}-Ar-B=0,}
這就是遞迴關係式的特徵方程。解出r可獲得兩個根（roots）λ1,λ2{displaystyle lambda _{1},lambda _{2}}
- an=Cλ1n+Dλ2n{displaystyle a_{n}=Clambda _{1}^{n}+Dlambda _{2}^{n},}
而如果兩個根是相同的（當A2+4B=0），我們得到
- an=Cλn+Dnλn{displaystyle a_{n}=Clambda ^{n}+Dnlambda ^{n},}
C和D都是常數。
換句話說，將這種an=Aan−1+B{displaystyle a_{n}=Aa_{n-1}+B}
範例：斐波那契数（Fibonacci Number）
斐波那契数是使用一種線性遞迴關係式來定義：
- F0=0{displaystyle F_{0}=0,}
- F1=1{displaystyle F_{1}=1,}
- Fn=Fn−1+Fn−2{displaystyle F_{n}=F_{n-1}+F_{n-2},}
設若：Fn/Fn−1{displaystyle F_{n}/F_{n-1},}
- Fn=Φn5−(1−Φ)n5{displaystyle F_{n}={Phi ^{n} over {sqrt {5}}}-{(1-Phi )^{n} over {sqrt {5}}}}
起始條件為：
- F0=0{displaystyle F_{0}=0,}
- F1=1{displaystyle F_{1}=1,}
因此，斐波那契数的序列為：
- 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ...
常系数非齐次线性递推关系
对于常系数非齐次线性递推关系，我们可以用待定系数法来求出它的一个特解，而它的通解就是这个特解与对应的齐次递推关系的通解的和。也可以使用迭代法求解，但只能得到确切的数值解，不能直接以解析式作答，该方法可利用计算机求解。
时域经典法求解
一般情况下，常系数线性差分方程可以写作：
- ∑k=0Naky(n−k)=∑r=0Mbrx(n−r){displaystyle sum _{k=0}^{N}a_{k}y(n-k)=sum _{r=0}^{M}b_{r}x(n-r)}
则对应的齐次方程形式为：
- ∑k=0Naky(n−k)=0{displaystyle sum _{k=0}^{N}a_{k}y(n-k)=0}
则特征方程为：
- ∑k=0NakαN−k=0{displaystyle sum _{k=0}^{N}a_{k}alpha ^{N-k}=0}
当特征根非重根时，齐次解为：
- yh(n)=∑i=1NCiαin{displaystyle y_{h}(n)=sum _{i=1}^{N}C_{i}alpha _{i}^{n}}
当特征根为重根时，若α1{displaystyle alpha _{1}}
- yh(n)=∑i=1KnK−iα1n{displaystyle y_{h}(n)=sum _{i=1}^{K}n^{K-i}alpha _{1}^{n}}
特解yp(n)=D(n){displaystyle y_{p}(n)=D(n)}
一般情况，当激励函数x(n)代入方程。
方程右方出现nk{displaystyle n^{k}}
- yp(n)=A0nk+A1nk−1+⋯+Ak{displaystyle y_{p}(n)=A_{0}n^{k}+A_{1}n^{k-1}+cdots +A_{k}}
当方程右方出现an{displaystyle a^{n}}
当a不是特征根时
- yp(n)=Aan{displaystyle y_{p}(n)=Aa^{n}}
当a是特征根时
- yp(n)=(A1n+A0)an{displaystyle y_{p}(n)=(A_{1}n+A_{0})a^{n}}
当a为r重根时
- yp(n)=(Arnr+Ar−1nr−1+⋯+A1n+A0)an{displaystyle y_{p}(n)=(A_{r}n^{r}+A_{r-1}n^{r-1}+cdots +A_{1}n+A_{0})a^{n}}
将特解带入原方程，求出待定系数。根据边界条件，可求出齐次节待定系数。
例子
我们用待定系数法来解以下的常系数非齐次线性递推关系：
- an+1=2an+3n+5n{displaystyle a_{n+1}=2a_{n}+3^{n}+5n,}
对应的齐次递推关系
- bn+1=2bn{displaystyle b_{n+1}=2b_{n},}
的齐次解是：
- bn=c12n{displaystyle b_{n}=c_{1}2^{n},}
我们猜测特解的形式为：
- an=c23n+c3n+c4{displaystyle a_{n}=c_{2}3^{n}+c_{3}n+c_{4},}
代入原递推关系中，我们便得到：
- c23n+1+c3(n+1)+c4=2(c23n+c3n+c4)+3n+5n{displaystyle c_{2}3^{n+1}+c_{3}(n+1)+c_{4}=2(c_{2}3^{n}+c_{3}n+c_{4})+3^{n}+5n,}
比较等式两端的3n{displaystyle 3^{n}}
- 3c2=2c2+1{displaystyle 3c_{2}=2c_{2}+1,}
- c2=1{displaystyle c_{2}=1,}
比较等式两端的n{displaystyle n}
- c3=2c3+5{displaystyle c_{3}=2c_{3}+5,}
- c3=−5{displaystyle c_{3}=-5,}
比较等式两端的常数项，可得：
- c3+c4=2c4{displaystyle c_{3}+c_{4}=2c_{4},}
- c4=c3=−5{displaystyle c_{4}=c_{3}=-5,}
因此原递推关系的通解为：
- an=c12n+3n−5n−5{displaystyle a_{n}=c_{1}2^{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})}
- 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.
|
Comments
Post a Comment