[分析] 雙向遞迴數列的推導問題(1000p)

[znmkhxrw (QQ)]

想請問有關雙向遞迴函數的綜合性跟推導問題
每個問題我都會下一個標題, 之後再進行詳細陳述, 最後加一些自己的猜測

順帶一提, 【問題三】是基於【問題二】的猜測是成立的
也是我主要想問的問題, 不過要先把【問題一、二】釐清才能講得清楚
-------------------------------------------------------------------

【問題一】雙向遞迴函數是否給定初始值後就存在唯一

我們知道單向遞迴函數的(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
推 LPH66       : 雖然我不太懂訊息處理, 不過單論線性遞迴的話
針對這句額外提一下, 我很難找我這些問題的資料就是在於一般純數學根本只會討論單向
遞迴, 而雙向遞迴是在差分方程才遇到, 而這個關鍵字用大多用在工程上, 嚴謹性好像就
沒那麼高

只要有差分方程, 起手式就Z轉換灌下去...

純數上考慮單向遞迴方程時, 用生成函數的做法就是冪級數化, 解出的解確實還保留著初
始值任意變動

可是雙向用Z轉換後就把初始值吃掉...我一直找不到這方面的討論

→ LPH66       : 指數函數拿去做 Z 轉換好像也會變成 0
→ LPH66       : 而線性遞迴的解很大一部份是指數函數的線性組合
→ LPH66       : 這可能可以做為問題二的一個破口?
推 LPH66       : 噢等等, 我好像直接去拿形式運算了, 指數函數似乎
→ LPH66       : 不能做這種求和的樣子 (兩個方向總有一個會發散)
沒錯! L大你試的這些基本的我試過, 不可能雙邊都收斂(除非初始值=0, 那整串都0), 即
Z轉換不收斂, 這個結果也跟"Z轉換只解出整串都0"相呼應

→ LPH66       : 那是不是有可能這個發散的解被 Z 轉換給忽略了?
→ LPH66       : 我把它切兩半求和然後以為可以加, 但這不行
→ LPH66       : 也就是說, 做 Z 轉換表示我只討論這個雙向無窮級數
→ LPH66       : 收斂而有一個形式出來的解, 並不是「所有解」
你猜測的應該跟我問題二的(a)~(c)一致, 就是Z轉換解出來的解前提是要讓(a)~(c)能過,
 而就結果論來說能讓(a)~(c)都過的解只有唯一一組

推 Vulpix      : 我覺得一次只能收掉一邊。2-sided 就是要切開成兩個
→ Vulpix      : 數列來看。
嗨V大~切開的話我覺得對於【問題一】可以有很明確的答案
即雙向遞迴是單向個別唯一存在

可是硬要和在一起就是因為訊號處理/轉移函數/頻率響應/IIR/Z轉換...這些東西
都是直接看合在一起的, 但是沒看到在討論我詢問的這些嚴謹性問題

總之, 分開的話, 只看數學很好解決, 但是無法應付轉移函數/Z轉換那些東西
      合一起的話, 不在乎嚴謹性很OK, 但是在乎的話就導致我這篇的問題...

推 RicciCurvatu: 問題一基本上就是否定的 例如g 這個函數就是個零函
→ RicciCurvatu: 數 那反方向是不可能有的 微分方程的一些唯一解性跟
→ RicciCurvatu: 可逆性跟discrete 是有些共通的 但沒有很廣泛的定理
→ RicciCurvatu: 可以解決這些性質 你要明確寫下你的遞迴式 才能去解
→ RicciCurvatu: 存在唯一性
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的反函數

推 Vulpix      : https://youtu.be/m-hTWznOZu4 雖然我也知道可以做
→ Vulpix      : 出這種ROC非空的雙向級數。也可以湊出適當的g（反正
→ Vulpix      : g可以與n有關，那就每個n都換一個長相就好），但是
不太懂這三句表達什麼, 這連結的雙向級數不就是Laurent series?
還是V大是指"極限一起跑(n=-∞~∞)"不一定能拆成影片的極限分開跑?

→ Vulpix      : 這樣作是不是會變成必須限縮數列（訊號）的空間？
→ Vulpix      : 而且我有點懷疑這樣做的必要性。X(z)和Y(z)的ROC互
→ Vulpix      : 斥的時候怎麼辦？禁止兩個訊號相加嗎……
如同我【問題二】所述, 要達成 https://imgur.com/7HPYRPT.jpg 的推導
我覺得需要加入很多條件, 諸如我所述的: (a) 是否存在收斂圓環
                                      (b) 解析函數的相除
                                      (c) Z與反Z轉換的條件
像是x_n是零數列的話, X(z)=0, 連除都不能除
所以如果要加入很多限制(包含你說的限縮空間、Z domain訊號相加要well-defined)
這一點都不意外, 也呼應了" 明明解無窮多, 但是Z轉換解出的解卻唯一 "

只是查詢"轉移函數"的相關資料, 不管是離散型差分方程做Z轉換,
還是連續型微分方程做拉式轉換, 幾乎說轉就轉, 沒什麼在乎嚴謹性

綜合以上, 我就是想知道在條件不嚴謹的情況下, Z轉換解出來的唯一解到底是哪一個解
所以我才會覺得唯有把這些嚴謹化才能有答案...

推 Vulpix      : 那方面，我同意LPH大大說的。就是因為總有一側發散
→ Vulpix      : 導致能加起來的Y(z)只剩0這一個。
齊次線性方程的話用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轉換兩邊都收斂吧!?

→ recorriendo : 考慮你的y(n)例子 如果用two-sided z-transform解
→ recorriendo :   當然隱含假設解的two-sided z-transform存在 如
→ recorriendo : 上面推文說的 這只有y(n)=0符合
→ recorriendo : one-sided z-transform用在difference會需要代入i
→ recorriendo : nitial value
嗨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)那組解囉?

→ recorriendo : 用two-sided z-transform來解→代表已額外假定y(n
→ recorriendo : )的two-sided z-transform存在
→ recorriendo : 用right-sided z-transform來解→代表已額外假定y
→ recorriendo : (n)的right-sided z-transform存在
→ recorriendo : left-sided依此類推 就這麼簡單！
→ recorriendo : 而使用用right-sided z-transform來解 的確就會根
→ recorriendo : 據不同initial value而給出不同解  (left-sided z
→ recorriendo : -transform自然就對應final value)
定義: (a) "解"都是定義在雙向的
      (b) 右Z轉換存在表示級數收斂|z|>r, for some r>=0
      (c) 左Z轉換存在表示級數收斂|z|<R, for some R>0 or +∞
      (d) 雙Z轉換存在表示級數收斂r<|z|<R, for some 0=<r<R<=+∞

所以給定一個差分方程, 則:
(1) 若解的右向Z轉換存在, 則解會無限多組, 由初始值決定
    (但解的左向未定義)
(2) 若解的左向Z轉換存在, 則解會無限多組, 由初始值決定
    (但解的右向未定義)
(3) 若解的雙向Z轉換存在, 則並不是(1)+(2)拼湊成無限多組解, 反而是只有唯一一組解
    (但是無法預測這個解釋對應到哪個初始值)

其中綠色的部分我還沒證明, 只是依照結果論去做猜測而已
r大的意思是如此嗎?

→ recorriendo : General case嚴謹討論要慢慢想... 大致是這個方向
→ recorriendo : 跟Laplace transform解微方類比也可以
→ recorriendo : 回你的新發文 如果y(n)=(h＊x)(n)必須對-∞~+∞所
→ recorriendo : 有n都成立   two-sided z-transform才會有Y(z)=H(
→ recorriendo : z)X(x)
→ recorriendo : 把後者級數展開就知道了
y(n)=(h＊x)(n) <=> Y(z)=H(z)X(z) 這個我了解~

推 recorriendo : (1)+(2)拼湊出來 不會讓y(n)=(h＊x)(n)必須對-∞~
→ recorriendo : +∞都成立啊 所以根本不是雙向的"解"
→ recorriendo : *不會讓y(n)=(h＊x)(n)對-∞~+∞都成立
對對! (1)+(2)拼湊出來會是差分方程的解,
但是不一定會存在h使得y(n)=(h＊x)(n)對-∞~+∞都成立

→ recorriendo : 嚴謹討論 應該可以如此進行：寫出此遞迴方程的解空
→ recorriendo : 間 (常係數遞迴方程寫成矩陣形式就可以得到解空間
→ recorriendo : ) 然後討論其中哪些雙向z轉換存在
→ recorriendo : 事實上這樣討論解空間 跟討論微方的Laplace trans
→ recorriendo : form已經很像了
→ recorriendo : 我猜測如果解空間中雙向z-transform存在者不唯一
→ recorriendo : 那麼逆轉換時會有問題
了解~謝謝r大分享, 我再梳理一下

→ recorriendo : 囧 發現維基百科根本沒寫到one-sided z-transform
→ recorriendo : 解LCCDE initial value problem 難怪會搞混
→ recorriendo : 雖然它上面的表有寫difference後轉換會帶x(0)項
→ recorriendo : initial value problem範例一般工數課本應該有 網
→ recorriendo : 路上也到處有教學
單純單向線性遞迴跟雙向線性遞迴的解, 這個在數學很清楚也不會有問題
只是工程數學加入了: (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不就相同效果?

謝謝幫忙~

→ recorriendo : 目前沒時間仔細想 sorry~
→ recorriendo : 不過 你這樣的問題似乎不限於z-transform  也就是
→ recorriendo : 說問題是：
→ recorriendo : 表示成遞迴形式y(n)+a1 y(n-1)+a2 y(n-2)+...=x(n
→ recorriendo : )+b1 x(n-1)+b2 x(n-2)+...的話y(n)解似乎不唯一
→ recorriendo :  但是表示為y=h＊x則似乎唯一 (在給定h(n), x(n)的
→ recorriendo : 情況下)
→ recorriendo : 我猜想跟LTI表示條件如BIBO等有關
嗨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
========================================================================

→ Vulpix      : 三階差分方程要給三個初值，可以決定三項各自的係
→ Vulpix      : 數啊。
→ Vulpix      : 畢竟你要的h是那三個h的線性組合。
嗨V大, 這三句在回應哪一點呢?

推 Vulpix      : h其實跟微分方程的積分因子概念一樣（是Green's fu
→ Vulpix      : nction），所以跟x無關。
喔喔!! 蠻像的耶!!
所以可以這樣劃分:
(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中積分因子只會有一個(吧?

推 Vulpix      : 積分因子很多個啊，降階一次就要一個。所以我剛剛
→ Vulpix      : 寫得怪怪的，可能還要改一下:P
了解XD

→ recorriendo : 一些想法on the top of my head
→ recorriendo : (1) 原差分方程確實給定不同'初始值'可得不同解 但
→ recorriendo : BIBO或雙邊z-transform存在之類條件應會大大限制解
→ recorriendo : 的數量
→ recorriendo : (2) 若討論頻率響應 看的是單位圓 所以至少ROC要包
→ recorriendo : 含單位圓 這就限制h的選擇
→ recorriendo : (3) 話說回來 不同filter有同樣頻率響應也不怪 例
→ recorriendo : 如可以有相同響應的causal filter和acausal filte
→ recorriendo : r
(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而改變

推 Vulpix      : 你那個是二階差分方程，應該只要兩個初值就好。
→ Vulpix      : 三個h有多餘的吧？作為數列，h應該只有公比2和公比
→ Vulpix      : -1/2兩個。不過他們的z-transform都不能收斂。
那個例子的轉移函數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
推 Vulpix      : 我現在才驗算你的三個h，寫錯了啦……
推 Vulpix      : 不過causal,acausal這些跟Green's fx.是一致的。所
→ Vulpix      : 以是同一件事沒錯。