[分析] 雙向遞迴數列的推導問題(1000p)
想請問有關雙向遞迴函數的綜合性跟推導問題
每個問題我都會下一個標題, 之後再進行詳細陳述, 最後加一些自己的猜測
順帶一提, 【問題三】是基於【問題二】的猜測是成立的
也是我主要想問的問題, 不過要先把【問題一、二】釐清才能講得清楚
-------------------------------------------------------------------
【問題一】雙向遞迴函數是否給定初始值後就存在唯一
我們知道單向遞迴函數的(a) 存在性: by遞迴定理的變形
(b) 唯一性: by數學歸納法
嚴格敘述即是: 令f:R^k X N→R為一函數, N是正整數集合, R是實數集合
則任給k個實數y_0~y_(k-1)
存在唯一的數列y_n:N→R
使得y_n = f(y_(n-1),...,y_(n-k),n) for all n>=k
= y_i for n=0~k-1
以上是k階遞迴方程的一般式, 我為了跟雙向做比較, 稱上面叫作單向
而現在我們考慮雙向k階遞迴方程:
令g:R^k X Z→R為一函數, Z是整數集合, R是實數集合
則任給k個實數y_0~y_(k-1)
是否存在唯一的數列y_n:Z→R
使得y_n = g(y_(n-1),...,y_(n-k),n) for all n != 0~k-1
= y_i for n=0~k-1
我先不在乎存在性, 光是唯一性就讓我覺得有顧慮了
假設有兩個數列y_n, Y_n滿足上式, 則數學歸納法只告訴我y_n = Y_n for n>=0
n<0的部分完全無從檢驗, 因為整體的定義方向是正向的, 負向沒有g的反函數
這部分我有幾個猜測:
(1) 我對雙向遞迴函數的定義有誤?
(我一定要討論雙向, 因為涉及到後面訊號處理的數學問題)
(2) 確實雙向遞迴函數不一定有唯一性, 而如果g是線性的, 就可以導出存在唯一性
例如: y_n = y_(n-1) + y_(n-3) + x_n
y_0, y_1, y_2 given
則y_(n-3) = -y_(n-1) + y_n- x_n
因此就可以獲得負向傳播的資訊
【問題二】訊號處理中使用Z轉換解差分方程是唯一解
wiki跟書本幾乎對於下列名詞一起討論:
(a) Z轉換(Laurent級數的變數取倒數)
(b) LTI, 線性差分方程, FIR, IIR
(c) 轉移函數(transfer function)
(d) 頻率響應
舉個例子: 考慮差分方程y_n = y_(n-1) + y_(n-2)
則同取Z轉換得到 Y(z) = Y(z)/z + Y(z)/z^2
因此得到Y(z) = 0
然後反Z轉換得到y_n = 0, 零數列, 確實是解
參考 https://imgur.com/7HPYRPT.jpg
再來敘述我所遇到的問題:
假設線性差分方程具有【問題一】的存在唯一性
即k階線性差分方程只是k階雙向遞迴方程的一種
並且任給k個初始值就會唯一決定整條數列
那不難知道:
(1) 任給兩個滿足同一條k階線性差分方程的數列y_n, Y_n:Z→R
如果存在連續k個整數使得函數值相同, 那y_n = Y_n for all n€Z
(存在唯一性定理的立即結論)
(2) 同一條k階線性差分方程, 存在無窮多組解
但是！上面的結論跟Z轉換解差分方程是唯一解是矛盾的
因為如同我的舉例或是圖片, 取Z轉換後再反Z轉換回來, 得到的是唯一的y_n
沒有給你選擇k個初始值的地方
而我個人對於解釋矛盾的猜測如下:
矛盾來自於Z轉換解線性差分方程的嚴謹性
因為涉及: (a) 是否存在收斂圓環
(b) 解析函數的相除
(c) Z與反Z轉換的條件
所以綜合起來的解釋就是:
《線性差分方程有無窮多組解, 但是能讓(a),(b),(c)都過的解只有唯一一組》
也就是說: (A) Z轉換得到的解只是其中一組初始值所得到的解
(B) 只有唯一一組初始值可以讓Z轉換解法well-defined
(C) 線性差分方程中, 只有唯一一組初始值能寫成y_n = (h＊x)_n的形式
(這個推論是來自於Z轉換的性質, 數列摺積的Z轉換等於各自Z轉換相乘
這也是為什麼轉移函數是定義成y的Z轉換除以x的Z轉換)
(D) 只有唯一一組初始值才是LTI系統
(如果(C)對, 這個就對)
如果我以上的解釋是對的, 那我採用這些解釋當已知, 詢問下面的問題
【問題三】如果以上解釋是對的, 那如何解釋下面這些問題
(1) 如何知道Z轉換解法的唯一解是由哪一組唯一的初始值得到的?
還是就是結果論去用Z轉換解出解, 自然就得到所有的值了
(2) 工程實作上對於線性差分方程的處理如下:
(a) 使用Z轉換得到轉移函數(如上面連結的H(z))
如果想要得到頻域響應, 就考慮|H(exp(iw)|
(b) 實作時就是令初始值為0, 讓電腦去跑線性差分方程
那矛盾就來了, 用轉移函數得到的分析結果, 不就是默認你考慮的解y_n是唯一那組
可以用Z轉換解得的解, 那組解有那麼剛好初始值都是0?
我目前只能對這矛盾的猜測是:
(1)《假設初始值為0的解就是Z轉換解得的解》
當然我如果是這假設還蠻不舒服的, 應該有其他道理
(2) 不用假設, 初始值為0的解縱然跟Z轉換解得的解不同也沒關係
(注意，如此一來就不是LTI系統, 因為只有Z轉換那組解才能寫成摺積)
因為會存在某種工程上可以接受的近似關係(那是什麼?)
---------------------------------------------------------
完全解決以上聯貫問題的1000p奉上
其他有幫助到我的idea也會p幣感謝
謝謝幫忙~做訊號處理以來卡最久的邏輯問題就是這塊了
終於整理出一個好詢問的脈絡了...
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 59.102.225.191 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1661013967.A.773.html
推
08/21 00:57,
3年前
, 1F
08/21 00:57, 1F
針對這句額外提一下, 我很難找我這些問題的資料就是在於一般純數學根本只會討論單向
遞迴, 而雙向遞迴是在差分方程才遇到, 而這個關鍵字用大多用在工程上, 嚴謹性好像就
沒那麼高
只要有差分方程, 起手式就Z轉換灌下去...
純數上考慮單向遞迴方程時, 用生成函數的做法就是冪級數化, 解出的解確實還保留著初
始值任意變動
可是雙向用Z轉換後就把初始值吃掉...我一直找不到這方面的討論
→
08/21 00:57,
3年前
, 2F
08/21 00:57, 2F
→
08/21 00:58,
3年前
, 3F
08/21 00:58, 3F
→
08/21 00:59,
3年前
, 4F
08/21 00:59, 4F
推
08/21 01:00,
3年前
, 5F
08/21 01:00, 5F
→
08/21 01:01,
3年前
, 6F
08/21 01:01, 6F
沒錯! L大你試的這些基本的我試過, 不可能雙邊都收斂(除非初始值=0, 那整串都0), 即
Z轉換不收斂, 這個結果也跟"Z轉換只解出整串都0"相呼應
→
08/21 01:01,
3年前
, 7F
08/21 01:01, 7F
→
08/21 01:02,
3年前
, 8F
08/21 01:02, 8F
→
08/21 01:03,
3年前
, 9F
08/21 01:03, 9F
→
08/21 01:03,
3年前
, 10F
08/21 01:03, 10F
你猜測的應該跟我問題二的(a)~(c)一致, 就是Z轉換解出來的解前提是要讓(a)~(c)能過,
而就結果論來說能讓(a)~(c)都過的解只有唯一一組
推
08/21 20:02,
3年前
, 11F
08/21 20:02, 11F
→
08/21 20:02,
3年前
, 12F
08/21 20:02, 12F
嗨V大~切開的話我覺得對於【問題一】可以有很明確的答案
即雙向遞迴是單向個別唯一存在
可是硬要和在一起就是因為訊號處理/轉移函數/頻率響應/IIR/Z轉換...這些東西
都是直接看合在一起的, 但是沒看到在討論我詢問的這些嚴謹性問題
總之, 分開的話, 只看數學很好解決, 但是無法應付轉移函數/Z轉換那些東西
合一起的話, 不在乎嚴謹性很OK, 但是在乎的話就導致我這篇的問題...
推
08/22 00:44,
3年前
, 13F
08/22 00:44, 13F
→
08/22 00:44,
3年前
, 14F
08/22 00:44, 14F
→
08/22 00:44,
3年前
, 15F
08/22 00:44, 15F
→
08/22 00:44,
3年前
, 16F
08/22 00:44, 16F
→
08/22 00:44,
3年前
, 17F
08/22 00:44, 17F
g是零函數反倒是給出y_n的解, 就是y_n = 0 for all n!=0~k-1
不過如同我【問題一】所說, 如果g不可逆, 幾乎沒辦法推負向的y_n
所以我為了可以進行【問題二、三】, 就假設: (1) g是線性的
(2) g讓解有存在唯一性(取決於初始值)
另外針對跟微分方程的比較關係, 我蠻認同的, 有好多東西不一樣
像是一階微分方程x'(t) = f(t,x(t)) 就直接是雙向了
(給定x(t_0)=x_0, f夠好的話, 存在唯一解定義在包含t_0的maximal open interval)
但是一階差分方程y_n = g(y_(n-1), n)卻很容易只有單向...因為沒有g的反函數
推
08/22 01:06,
3年前
, 18F
08/22 01:06, 18F
→
08/22 01:07,
3年前
, 19F
08/22 01:07, 19F
→
08/22 01:08,
3年前
, 20F
08/22 01:08, 20F
不太懂這三句表達什麼, 這連結的雙向級數不就是Laurent series?
還是V大是指"極限一起跑(n=-∞~∞)"不一定能拆成影片的極限分開跑?
→
08/22 01:09,
3年前
, 21F
08/22 01:09, 21F
→
08/22 01:18,
3年前
, 22F
08/22 01:18, 22F
→
08/22 01:19,
3年前
, 23F
08/22 01:19, 23F
如同我【問題二】所述, 要達成 https://imgur.com/7HPYRPT.jpg
的推導
我覺得需要加入很多條件, 諸如我所述的: (a) 是否存在收斂圓環
(b) 解析函數的相除
(c) Z與反Z轉換的條件
像是x_n是零數列的話, X(z)=0, 連除都不能除
所以如果要加入很多限制(包含你說的限縮空間、Z domain訊號相加要well-defined)
這一點都不意外, 也呼應了" 明明解無窮多, 但是Z轉換解出的解卻唯一 "
只是查詢"轉移函數"的相關資料, 不管是離散型差分方程做Z轉換,
還是連續型微分方程做拉式轉換, 幾乎說轉就轉, 沒什麼在乎嚴謹性
綜合以上, 我就是想知道在條件不嚴謹的情況下, Z轉換解出來的唯一解到底是哪一個解
所以我才會覺得唯有把這些嚴謹化才能有答案...
推
08/22 03:26,
3年前
, 24F
08/22 03:26, 24F
→
08/22 03:27,
3年前
, 25F
08/22 03:27, 25F
齊次線性方程的話用Z轉換確實如此, 可是非齊次解y_n的話寫成齊次解(y_h)加特解(y_p)
時, y_n = y_h_n + y_p_n, 同取Z轉換得到Y(z) = Y_h(z) + Y_p(z), 而我們知道Y_h(z)
=0
所以Y(z)=Y_p(z), 所以還是有可能存在雙向x_n使得Z轉換兩邊都收斂吧!?
→
08/22 18:08,
3年前
, 26F
08/22 18:08, 26F
→
08/22 18:08,
3年前
, 27F
08/22 18:08, 27F
→
08/22 18:08,
3年前
, 28F
08/22 18:08, 28F
→
08/22 18:11,
3年前
, 29F
08/22 18:11, 29F
→
08/22 18:11,
3年前
, 30F
08/22 18:11, 30F
嗨r大, 如果硬生生把 https://imgur.com/7HPYRPT.jpg
的差分方程加入初始值
並且只允許單向的遞迴定義, 另外一個方向直接強迫變成0
那整個系統又變回初始值唯一決定的單向遞迴函數
我還是想考慮雙向的原因來自於嚴謹推導下列訊號處理詞彙的關係:
(我下面所述的Z轉換都是指雙向)
(1) y_n = (h＊x)_n, 如果h數列沒有緊緻支撐則稱作IIR系統
(2) Y(z) = H(z)X(z), H為轉移函數
(3) https://imgur.com/7HPYRPT.jpg
雙向差分方程
可以發現(1)~(3)都是跟y_n的初始值無關的
而目前整理沒矛盾的說法是:
(a) 若y_n = (h＊x)_n
則Y(z) = H(z)X(z), 其中大寫為小寫的Z轉換(假設Z轉換都存在)
(b) 若Y(z) = H(z)X(z)
則y_n = (h＊x)_n, 其中小寫為大寫的反Z轉換(假設反Z轉換都存在並且有交集ROC)
(c) 任給一個差分方程(x_n跟係數), 有無窮多組解滿足此差分方程
但是只有唯一一組解可以表達成y_n = (h＊x)_n
如果以上r大都同意的話, 就剩【問題三】, 我如何知道上面(c)的那組唯一解的初始值?
不考慮直接把解解出來的情況, 這樣我整條y_n都知道了
換句話說, 我想要知道怎樣的初始值才能得到上面(c)那組唯一解
如果答案是沒辦法的話, 直接設初始值為0幾乎不可能是上面(c)那組解囉?
還有 26 則推文
還有 4 段內文
→
08/23 20:50,
3年前
, 57F
08/23 20:50, 57F
→
08/23 20:51,
3年前
, 58F
08/23 20:51, 58F
→
08/23 20:51,
3年前
, 59F
08/23 20:51, 59F
單純單向線性遞迴跟雙向線性遞迴的解, 這個在數學很清楚也不會有問題
只是工程數學加入了: (1) LTI<=>表示成摺積
(2) 雙向Z轉換
(3) 轉移函數
(4) causal, anticausal, noncausal
等等這些定義後, 對雙向線性遞迴的解空間產生的怎樣的分類
我覺得問題應該是在這些的關係吧~
--------------------------------------------
嗨r大, 最後問個實作與理論結合性的問題:
考慮 y_n - (3/2)*y_(n-1) - y_(n-2) = 2*x_n - x_(n-1) 這個差分方程
使用雙向Z轉換的話, 可以找到三個h_n使得y_n = (h＊x)_n, 分別是:
h1_n = (-1/2)^n*u_n - (-1/2)^n*u_(-n-1)
h2_n = (-1/2)^n*u_n - 2^(n+1)*u_(-n-1)
h3_n = (-1/2)^n*u_n + 2^(n+1)*u_n
其中u_n := 1 , n>=0
0 , n<0
接著有兩個實作上的問題:
(1) 單純考慮差分方程有無窮多組解(初始值決定)
我怎麼知道要怎麼設初始值, 才是我要的對應到的h_n的y_n?
例如取怎樣的x跟y的初始值則會有解y_n會等於(h1＊x)_n
(2) 假設(1)的問題完美解決, 即針對我要的h我都可以找到我要的初始值
那選哪個h重要嗎? 因為這三個h的H(z)都一樣(只是不同ROC)
所以頻率響應 H(exp(iw))也是一樣的(甚至相位都一樣),
那我隨便選一個h來當filter不就相同效果?
謝謝幫忙~
→
08/24 19:49,
3年前
, 60F
08/24 19:49, 60F
→
08/24 19:51,
3年前
, 61F
08/24 19:51, 61F
→
08/24 19:51,
3年前
, 62F
08/24 19:51, 62F
→
08/24 19:58,
3年前
, 63F
08/24 19:58, 63F
→
08/24 19:58,
3年前
, 64F
08/24 19:58, 64F
→
08/24 19:58,
3年前
, 65F
08/24 19:58, 65F
→
08/24 19:58,
3年前
, 66F
08/24 19:58, 66F
→
08/24 19:59,
3年前
, 67F
08/24 19:59, 67F
嗨r大, 你們幫忙看就很謝謝了, 對我來說先釐清是我搞複雜了還是真的沒那麼簡單
就已經是往前一大步了
另外關於你上面回的跟我目前的小結不太一致, 我再次敘述如下:
給定一個k階線性差分方程:
y_n = a_1*y_(n-1)+...+a_k*y_(k-1)+b_0*x_n+...+b_k*x_(n-k)
其中x_n是一個給定的數列
則: (1) 給定初始值y_0~y_(k-1)
則存在唯一的解y_n滿足初始值與方程
(2) 令y_n為此方程的一個解, 則不一定存在h_n使得y=h＊x
(3) 令y_n為此方程的一個解且y=h＊x for some h
則h也不一定唯一
(像是我舉實例的差分方程, 可以用雙向Z轉換解出三種h, 來自於ROC的不同
所得到的反Z轉換的數列也不一樣)
而最後問題再次重複: (a) 如果多條h都有同樣的Z轉換(選取不同ROC), 都滿足y = h＊x
那任意選一條h不都有一樣的頻率響應?(感覺不太合邏輯)
(b) 我該如何選定初始值來知道這個初始值所得出的唯一解y_n
跟某條h所導致的y = h＊x是同一個y?
(c) 補充一個新發現的問題...在討論某個解y_n是否存在h_n
使得y = h＊x時, 如果存在的話, 那就邏輯來說h會跟x有關
可是Z轉換解出來的h卻跟x無關...所有x都能用
我怎麼越來越混亂了@@
大致上是這樣~
=======================================================================
P幣答謝到此結束, 有後續討論就無酬答謝了~
LPH66 200p
Vulpix 200p
RicciCurvatu 200p
recorriendo 1000p
========================================================================
→
08/25 00:46,
3年前
, 68F
08/25 00:46, 68F
→
08/25 00:46,
3年前
, 69F
08/25 00:46, 69F
→
08/25 00:47,
3年前
, 70F
08/25 00:47, 70F
嗨V大, 這三句在回應哪一點呢?
推
08/25 00:55,
3年前
, 71F
08/25 00:55, 71F
→
08/25 00:55,
3年前
, 72F
08/25 00:55, 72F
喔喔!! 蠻像的耶!!
所以可以這樣劃分:
(1) 給定線性差分方程, 解空間當然跟方程裡面的x_n有關
而任給初始值就得到唯一解
(2) 給定線性差分方程與其中一個解y_n, 考慮y能不能寫成摺積的形式
當然可以硬湊出h使得 y_n = (h＊x)_n, 但是如果這個h跟x有關就是為湊而湊
(3) 承(2), 如果h跟x無關, 就像是V大說的那種積分因子的味道, Z轉換就是在解出這個
如果(3)同意的話, 那我的舉例中, 同一個H(z)依照不同的ROC解出三種不同的
h是代表什麼意思? 在ODE中積分因子只會有一個(吧?
推
08/25 01:14,
3年前
, 73F
08/25 01:14, 73F
→
08/25 01:14,
3年前
, 74F
08/25 01:14, 74F
了解XD
→
08/25 09:23,
3年前
, 75F
08/25 09:23, 75F
→
08/25 09:27,
3年前
, 76F
08/25 09:27, 76F
→
08/25 09:27,
3年前
, 77F
08/25 09:27, 77F
→
08/25 09:27,
3年前
, 78F
08/25 09:27, 78F
→
08/25 09:28,
3年前
, 79F
08/25 09:28, 79F
→
08/25 09:28,
3年前
, 80F
08/25 09:28, 80F
→
08/25 09:30,
3年前
, 81F
08/25 09:30, 81F
→
08/25 09:30,
3年前
, 82F
08/25 09:30, 82F
→
08/25 09:30,
3年前
, 83F
08/25 09:30, 83F
(1),(2),(3)都同意!
而(2)+(3)感覺是解掉我問題的關鍵耶!
因為反Z轉換要唯一需要有交集的ROC, 不同的ROC會反Z出不同的數列
所以只會最多只會有一個h_n的Z轉換的ROC是蓋住單位圓
而我最後要的輸出y_n就是在這個ROC上的反逆轉換而已
即y_n = Z^-1(Y(z))_n = Z^-1(H(z)X(z))_n, 其中z€蓋住單位圓的ROC
也就是說, h,H,y,Y都要依照ROC而改變
推
08/25 16:19,
3年前
, 84F
08/25 16:19, 84F
→
08/25 16:21,
3年前
, 85F
08/25 16:21, 85F
→
08/25 16:24,
3年前
, 86F
08/25 16:24, 86F
那個例子的轉移函數H(z)有2個pole(分母是看x的階數), p = -1/2, 2
所以複平面可以分成三塊ROC, |z|<1/2, 1/2<|z|<2, |z|>2
所以才反Z轉換得到三個h_n
由此可知有幾個h_n是看pole的位置跟數量, 也就是跟x的階數有關
(當然如果y的階數提供的zeros可以跟pole消掉也會減少pole)
所以我不認為h_n的數量跟y的階數是一樣的
但是V大你提了初始值的數量就是h_n的數量, 我才覺得怪怪的
※ 編輯: znmkhxrw (114.25.68.68 臺灣), 08/25/2022 16:56:33
推
09/08 07:01, , 87F
09/08 07:01, 87F
推
09/08 07:19, , 88F
09/08 07:19, 88F
→
09/08 07:19, , 89F
09/08 07:19, 89F