[離散] 遞迴特徵根小於1的解行為證明

[znmkhxrw (QQ)]

請問一下, 我想證明:

  線性實數常係數齊次遞迴方程如果其每個特徵根的絕對值都小於1
  則解都趨近於0

我知道有個證明是找到解空間的基底的長相, 然後就得證

但是這個證法要完整地寫出來很複雜, 因為特徵多項式的解有很多case要討論:

(1) 重根/無重根, 重根的話又要看general eigenspace大小

(2) 實根/虛根

粗糙的來說, 如果根是實根λ, 解會是λ^n*(c_0+c_1*n+c_2*n^2+...)這種形式
                根是虛根λ, 解會是|λ|^n(cos+sin...)這種形式

最複雜的大概是同時是虛根而且又有重根

而只要|λ|<1, 上述的解都會趨近於0 as n→+∞

---------------------------------------------------

有鑑於以上, 我才好奇有沒有比較簡短的證法

因為有些其他性質我確實用方程式本身就能證出來, 不用透過解的長相

我才覺得這篇的問題應該有機會有其他證法

以下補充嚴格的數學描述:
==================================================================
令 a_1~a_N€R, a_N !=0
   y_n 滿足 y_n + a_1*y_(n-1) + ... + a_N*y(n-N) = 0, for all n >= N
   p(x):= x^N + a_1*x^(N-1) + ... + a_N 為特徵多項式

若 over C來看, p(x)所有的根的絕對值都小於1

則 lim_{n→+∞} y_n = 0
==================================================================

謝謝幫忙~

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 59.102.225.191 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1670079252.A.C4B.html
推 Vulpix      : 可是特徵根都比1小這件事，你也很難用原方程寫啊。
嗨V大~是的, 我就是自己試了一些方向都沒辦法用到特徵根
甚至我直接假設y_n極限存在為L, 也只是得到(1+a_1+...+a_N)*L = 0
完全沒有特徵根資訊

因此我才想問是不是有其他方式

→ Vulpix      : 直接用通解的公式可行，而且沒有你說的那麼複雜。
有不複雜的討論方式可以分享嗎!?
我記得之前線性ODE時, 2x2是最簡單的, 3x3就要討論幾種case了
而老師跟課本舉例也只到3x3, 因為general的NxN有太多根的情形了...

如果有簡單寫出通解的證明我也想知道, 謝謝!

推 Vulpix      : 每一項也就λ^n乘上n的多項式而已。都會收斂到0。
→ Vulpix      : 其實重數、虛實都不用顧慮，全部一起做就好。
"每一項也就λ^n乘上n的多項式" 這結論對我來說就是要分析每個λ的重數才能得到
還是V大你意思是, 只要λ是特徵多項式的m重根,
那就存在m個數列 y_k_n = (λ^n)*(n^(k-1)), k=1~m 是線性獨立的
如果λ是虛數再換成cos, sin即可?

如果是這樣的話確實很快耶! 我文中說要討論general eigenspace說很複雜的意思是
我把線性方程轉成矩陣形式來看 Y_n = A*Y_(n-1), 其中A是矩陣
而A的特徵多項式就跟差分方程的特徵多項式一樣
因此接下來要對A做Jordan form時就會需要討論每個λ的情形

看來直接用原差分方程做會避開很多矩陣會遇到的麻煩耶!

推 wohtp       : y_n = A y_(n-1) + x_n   這是你的遞迴式？
→ wohtp       : 有 x 在怎麼會收斂？
w大是說我上面回V大的那串吧 那我筆誤了 我這篇都是討論齊次的 我改一下 謝謝

推 Vulpix      : 並不須要真的知道重數，反正這只是some function of
→ Vulpix      : A and λ。
推 Vulpix      : 這種矩陣已經是自己的rational canonical form了。
→ Vulpix      : 所以每個eigenvalue只有一個Jordan block。
→ Vulpix      : 然後回你回應第一段：是。理由就是上面這段。
嗨V大, 非常謝謝你~了解了!
聽你的解釋確實給了【原本我在乎A的Jordan form還要討論很多】一個不用討論的理由
A因為長相的關係, 導致其Jordan form很簡單(每個eigenvalue只有一個Jordan block)
所以不管直接證線性獨立, 或是真的找A的Jordan form, 都是簡單的事

再次感謝~

推 alan23273850: 我想借串問為何一元高次遞迴式可以用 ODE 通解，二
→ alan23273850: 元一次遞迴式可以用 power series 去解 ~
嗨a大, 你的一元高次跟二元一次分別是?
線性遞迴的 y_n = a_1*y_(n-1) + ... + a_N*y_(n-N) + x_n 就是你的一元高次嗎?
如果是的話, 我是不知道如何解釋"為什麼"
單純就是令 Y_n:=[y_n y_(n-1)...y_(n-N)]^t, X_n = [x_n 0...0] 的話
原方程很容易證明等價於Y_n = A*Y_(n-1) + X_n

推 alan23273850: 所以他跟 ODE 是有關係的嗎？？？
是很常聽到一階線性常係數ODE的離散型就是差分方程啦
不過細節上還是有差, 但是也是有相似的地方

比如這篇的差分方程寫成矩陣: Y_n   = A*Y_(n-1) + X_n
而一階線性ODE:              Y(t)' = A*Y(t)    + X(t)
通解表達式都會跟求A的eigenvalue有關
不過ODE的A是任意矩陣, 差分方程的A是很多0的矩陣
所以差分方程的A解起來不像ODE那樣要討論一堆A的eigenvalue的重數問題
※ 編輯: znmkhxrw (59.102.225.191 臺灣), 12/05/2022 18:03:12
推 wohtp       : 微分也是線性算子，很多結果可以直接套在ODE上面用
→ wohtp       : 其實就是向量空間維度變成無限這樣
推 alan23273850: 感謝樓上的開導！