作者Vulpix (Sebastian)
看板Math
标题Re: [其他] 线性递回方程 解的行为(Solved)
时间Thu May 12 19:53:52 2022
虽然是已经结案的问题，不过也算有其他观点可以提供吧。
※ 引述《znmkhxrw (QQ)》之铭言：
: 想请问下列递回方程式是否有解的分类与规律:
: -------------------------------------------------------------
: 令 x_n为一实数列, n>=0
: y_(-1), y_(-2),..., y_(-N) 为N个初始值
: a_1, a_2,..., a_N 为N个实数, a_N != 0
: 定义递回关系式 y_n = (Σ_{k=1~N} a_k*y_(n-k) ) + x_n, n>=0
: 想请问有没有关於 怎样的a_k与x_n的条件
: 会导致 y_n有怎样的行为, 特别是n→∞时的行为
: 或是条件更强一点, 加入" x_n = 0 for n>=M, some M "
: 会有更好的结果吗?
: (我是做实验时发现n很大时感觉y_n会趋近周期函数, 不知道是特例还是怎样)
: -------------------------------------------------------------
: (A^t代表A的transpose, "*"只是乘法而已)
: 令 Y_n:=[y_n, y_(n-1),..., y_(n-N+1)]^t
: X_n:=[x_n, 0, ..., 0]^t
: [a_1, a_2, ..., a_(N-1), a_N]
: [ 1 , 0 , ..., 0 , 0 ]
: A :=[ 0 , 1 , ..., 0 , 0 ]
: [ ..........................]
: [ 0 , 0 , ..., 1, , 0 ]
: 则 Y_n = A*Y_(n-1) + X_n, n>=0
: 一直拆下去可以得到, Y_n = Σ_{k=0~n} A^(n-k)*X_k
: 之後把A对角化(只要a_N != 0都可以对角化)得到 A = P*D*P^(-1), P可逆
这个条件不对。
a_N != 0 只告诉你 A 可逆而已。
可逆与 eigenvalue 有没有重复是两回事，
而这种形状的矩阵是只要 eigenvalue 有重复就一定不能对角化的。
不过这也是小事，A 不可逆也好、不能对角化也罢，都不重要。
反正我们想找的 D 是 Jordan form。
你写出的 A 其实就是你的线性系统的 companion matrix。
当然这个问题就如同 LPH 大所述，只是一个标准的线性系统。
如果我们定义 F(t) = f_0 + f_1*t + f_2*t^2 + ...
其中 (F,f) = (Y,y), (A,a), (X,x)，还有 a_0 = 0。
那 Y(t) = I(t) + A(t)Y(t) + X(t)
其中 I(t) 是一个跟初始条件有关的 N-1 次多项式，
长相是 I(t) = Σ_{n=0}^{N-1} t^n*Σ_{n+1}^{N} a_k*y_{n-k}
从方程式上可以看到初始条件 y_(-1) 等数可以用某种形式并入 x_n 来计算。
解 Y(t) = (I+X)/(1-A)，最後这个分母 1-A(t) 就是关键了。
接下来的步骤就跟积分这种函数的标准步骤一样：部份分式。
分解完後，除了一个多项式部份外，每一项都是 p/(λ-t)^n 这种形式。
对於 n=1 的项来说，因为幂级数的系数会是 p*λ^(-k)，所以会贡献出等比项。
而等比项就是造成 y 很大或震荡的来源，如果λ很小则他的影响会越来越不重要。
至於当 n>1 的时候，系数会出现 p*C(n+k-1,n)*λ^(-k) 这种形式，
他们会压过 λ^(-k) 而更明显地表现出来，因为是 O((n/λ)^k)。
最後这段处理就跟直接用线性系统解出来的结论是一样的。
如果 X(t) 不是多项式的话，(I+X)/(1-A) 的处理上好像会比较复杂一点点？
反正就是要把围绕在 t=λ 附近的发散项抓出来，在每个点都泰勒展开一下。
例如 sin(t)/(1-t)^2 就要把 sin(1)/(1-t)^2 - cos(1)/(1-t) 抓出来扣掉。
（详细的状况应该更复杂，因为 X(t) 可能无法在 λ 展开。）
把所有发散项都扣掉之後，剩下的部份就是个幂级数了。
所以如果 λ 都不在单位圆外的话，y_n 会呈现出以那个无穷数列为中心振荡的样子。
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 163.13.112.58 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1652356435.A.AF6.html
※ 编辑: Vulpix (163.13.112.58 台湾), 05/12/2022 23:55:46
1F：推 znmkhxrw : 谢V大分享, 那边"对角化"确实是写错了 05/12 23:47
2F：→ znmkhxrw : 另外我不懂"(F,f) = (Y,y), (A,a), (X,x)"这行以及 05/12 23:48
Y(t) = y_0 + y_1*t + y_2*t^2 + ...
A(t) = a_0 + a_1*t + a_2*t^2 + ... + a_N*t^N, a_0=0
X(t) = x_0 + x_1*t + x_2*t^2 + ...
我只是懒得这样写三行。
3F：→ znmkhxrw : "Y(t) = I(t) + A(t)Y(t) + X(t)"这行是要补充什麽 05/12 23:48
4F：→ znmkhxrw : 是把离散型递回y_n改成连续型y(t)吗? 05/12 23:49
不是。Y(t) 就是那个「生成函数」，t^n 项系数 = y_n。
5F：→ znmkhxrw : ODE是 y'(t) = Ay(t), 递回是y_n = Ay_(n-1) 05/12 23:50
6F：→ znmkhxrw : 但是这里看起来怎麽像是 y(t) = Ay(t) 05/12 23:50
※ 编辑: Vulpix (163.13.112.58 台湾), 05/13/2022 00:00:52
7F：推 znmkhxrw : 了解~生成函数的理论我有空补完再来看後面, 谢啦! 05/13 00:59