Re: [分析] 遞迴關係式的分析方法

[eminem2003 (強森)]

※ 引述《xxxx9659 (嘎嘎嘎嘎嘎)》之銘言：
: ※ 引述《Desperato (肥鵝)》之銘言：
: : 代回去就好了
: :                        n-2
: : A(n-1) = 1 + 1/(n-1) * sum A(i)
: :                        i=1
: : n-2
: : sum A(i) = (n-1) (A(n-1) - 1)
: : i=1
: : n-1
: : sum A(i) = n A(n-1) - (n-1)
: : i=1
: :                  n-1
: : A(n) = 1 + 1/n * sum A(i) = A(n-1) + 1/n
: :                  i=1
: 感謝回答～我的問題是這樣的
: 如果看到一個遞迴關係式 長得像這樣
: A(1) = 2
: A(2) = 4
: A(n) = A(n-1) + 2 A(n-2)
: 把數列一一列出來 2, 4, 8, 16, 32, 64, ...
: 一眼就了解 A(n) = 2^n
: 那稍為把題目改一下
: A(1) = 1
: A(2) = 1
: A(n) = A(n-1) + 2 A(n-2)
: 把數列一一列出來 1, 1, 3, 5, 11, 21, ...
: 我眼睛要看到脫窗才知道 A(n) = ( 2^n - (-1)^n ) / 3
: 原本的那題遞迴關係式 是把他列出來後
: 發現是調合級數 我去才動手把算式簡化
: 要簡化的遞迴方法 我就只有嘗試代參數猜答案
: 那如果題目難一點看不出來 我就沒招了
: 不知道沒有什麼通用方法或步驟 可以分析這種問題？
: 還是有網站或書在教這類的分析的？


這種常係數線性差分方程很多地方可以查閱，最有名例子就是費波那契數列

也有線性代數的解法，常常用費波那契數列舉例，不過有點冗長而且不好打字

所以只說明一下一般書上提到的， 猜答案(我也不知道他是叫甚麼)


線性就是 每一個n 你的A(n)項 沒有被動手腳 變成別種東西

譬如說 A(n)^2, 根號A(n), 1/A(n), sin(A(n)), 任何f(A(n))

注意是每一個n=1,2,3,4,5.....

再來A(n) 前面的係數只能是n的函數 f(n)
這裡討論的是係數是常數情形

所以方程式一定長這樣 cn * A(n) + cn-1 *A(n-1) +......cn-k * A(n-k)=0
c1, c2, ....cn-k都是常數，此例總共k+1項，所以為k階差分方程

你的例子
: A(1) = 1
: A(2) = 1
: A(n) = A(n-1) - 2 A(n-2)

可以移項 A(n) - A(n-1) + 2 A(n-2)=0 就是k=2, cn=1, cn-1=(-1), cn-2=2

用你的例子示範，猜答案，答案的形式猜 A(n)=a^n， a是一個待解的常數

直接代進去方程式:

     a^n     -    a^(n-1) + 2a^(n-2) = 0
(a^2)a^(n-2) - (a)a^(n-2) + 2a^(n-2) = 0

兩邊消掉a_^(n-2)

     a^2-a+2=0 ,解出a即可 , 你會發現a有兩解, 因為兩個都是解
假設a=a1, a2

根據線性差分方程式的性質，若A1(n), A2(n)都是解，則

x1 * A1(n) + x2 * A2(n) 均為此差分方程式的解，你可以直接代代看就知道了

此處x1 , x2為任意常數

所以你會發現二階差分方程，就會需要兩個初始條件，

就是你當初的
: A(1) = 1
: A(2) = 1

所以此提解出a1,a2後，答案即為A(n)= x1 * a1^n + x2 * a2^n
x1和x2則代入 A(1)=1 和 A(2)=1去解出來


所有的常係數線性差方方程都可以這樣解出通解
再代入初始條件，得到題目給出的特解
此種解法可以用矩陣表示，用解eigenvalue問題解決，在線性代數的書會提到

最後一個問題就是，為何兩個解足以作為2階差分的通解
這個是線性代數的問題，以後有興趣再討論。

結論是k階常係數線性差方方程的解空間為一k維項量空間。































--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.137.169.178
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1553598371.A.43E.html
推 xxxx9659    : 哇這篇講的好清楚詳細 感謝大大!!!
推 xxxx9659    : 移項的地方稍微寫錯 A(n) - A(n-1) - 2 A(n-2) = 0
                                     3Q
→ xxxx9659    : 剛剛照你教的算 的確可以解齊次常係數線性遞迴!
→ xxxx9659    : 剛剛上網看其他類型的遞迴解法 好難好崩潰...
※ 編輯: eminem2003 (101.137.234.6), 03/26/2019 23:53:41
→ eminem2003  : 非齊次的也可以，把通解加上特解，特解一樣要猜
→ eminem2003  : 猜的範圍就很複雜了，書上會整理一些常見的