利用奇異值分解的二階遞歸系統(tǒng)數(shù)值穩(wěn)定性方法

付波， 劉濟源， 趙熙臨， 徐光輝, 王子鵬

(湖北工業(yè)大學 電氣與電子工程學院， 湖北 武漢 430068)

利用奇異值分解的二階遞歸系統(tǒng)數(shù)值穩(wěn)定性方法

付波， 劉濟源， 趙熙臨， 徐光輝, 王子鵬

(湖北工業(yè)大學 電氣與電子工程學院， 湖北 武漢 430068)

為了簡便地解決二階遞歸系統(tǒng)的穩(wěn)定性問題，將二階遞歸系統(tǒng)轉(zhuǎn)變?yōu)槎A離散時變線性系統(tǒng)，并討論遞歸系統(tǒng)的穩(wěn)定性.在二階離散線性時變系統(tǒng)穩(wěn)定性分析的基礎上，利用奇異值分解(SVD)，將其轉(zhuǎn)化為參考信號(RS)系統(tǒng).提出一個新的離散時變線性系統(tǒng)不穩(wěn)定性的充分條件，并以離散正交Krawtchouk多項式與Jacobsthal數(shù)列遞歸式為主，討論并推導出其在Ⅱ,Ⅳ象限上的變化情況和新的不穩(wěn)定性判據(jù).仿真結果驗證了結論的準確性.

Krawtchouk多項式； Jacobsthal數(shù)列; 奇異值分解； 遞歸系統(tǒng)； 線性離散時變系統(tǒng)

遞歸是一種利用簡單操作實現(xiàn)復雜運算的有效方法，即通過簡單的問題來解決復雜的問題[1].其表現(xiàn)形式較典型的是二階遞歸，即數(shù)列的某一項是由其前兩項計算所得[2-3].Legendre多項式、Chebyshev多項式、Jacobi多項式、Hermite多項式、Tchebichef多項式和Krawtchouk多項式等經(jīng)典正交多項式[4-6]在圖像正交矩、曲線擬合、非線性電路計算，以及計算結構可靠性分析等技術都有應用[7-8].但由于正交多項式解析式過于復雜，所以在實際應用中一般采用其遞歸式求解多項式的值.Mukundan等[9]發(fā)現(xiàn)正交多項式的二階遞歸運算有可能導致數(shù)值發(fā)散，Gautschi[10-11]討論了離散正交多項式的遞歸收斂性，關軼峰等[12]針對二階離散線性時變系統(tǒng)的穩(wěn)定性也做了大量研究.由于離散多項式不存在離散誤差，其精度與高階數(shù)值的傳遞有關，隨著階數(shù)的增大，多項式的數(shù)值和誤差的增大更導致其不穩(wěn)定，從而影響圖像重構的精確性.Mukundan[13]利用x循環(huán)代替了n循環(huán)，同時，在一定程度上找到了高階多項式的誤差傳遞，解決了多項式高精度的算法問題.張海艷等[14]在圖像分割、重構的問題上利用算法的穩(wěn)定性，提出了概率密度函數(shù)在生物信息學上的研究.本文在二階離散線性時變系統(tǒng)穩(wěn)定性分析的基礎上，利用奇異值分解(singular value decomposition,SVD)方法將其轉(zhuǎn)化為參考信號(reference signal,RS)系統(tǒng)，提出一個新的離散時變線性系統(tǒng)不穩(wěn)定性的充分條件，并通過實驗驗證其結果.

1 遞歸系統(tǒng)數(shù)值穩(wěn)定性

1.1穩(wěn)定性定義

(a) 穩(wěn)定 (b) 不穩(wěn)定圖1 遞歸系統(tǒng)的穩(wěn)定性狀態(tài)Fig.1 Stability states of recursive systems

設系統(tǒng)初始狀態(tài)x0位于以平衡狀態(tài)xe為球心，半徑為ε的球域H(ε)內(nèi).如果對所考慮的整個時間區(qū)間內(nèi)，從H(ε)內(nèi)任一點x0出發(fā)的受擾運動φ(t，x0，xe)的軌跡都不超出H(ε)，則稱xe=0在李雅普諾夫下穩(wěn)定，如圖1(a)所示.對某個εgt;0，在所有半徑為τ的球域H(τ)內(nèi)的初始狀態(tài)，至少存在一個初始狀態(tài)，使得從它出發(fā)的解始終不會限制在以ε為半徑的球域H(ε)里，則稱平衡點在t0是不穩(wěn)定的，如圖1(b)所示.

1.2正交多項式

在矩函數(shù)集合中，分為連續(xù)正交多項式與離散正交多項式.Krawtchouk多項式是一種常見的離散正交多項式，更適合于對數(shù)字圖像的處理.n階Krawtchouk多項式的定義為

2 二階遞歸系統(tǒng)的SVD模型

2.1SVD方法

設2×2矩陣G∈C2×2，C為復數(shù)集，RankG=2，則存在2階酉矩陣U和2階酉矩陣V，使得

式(3)中：Σ=diag(σ1,σ2)，且σ1≥σ2≥0，而σi(i=1，2，)為矩陣G的正奇異值.

對狀態(tài)矩陣G(t)做SVD分解，可得G(t)=U(t)S(t)V(t)T.將U(t)，V(t)設定為單位旋轉(zhuǎn)矩陣，又因為X(t)=G(t)X(t-1)，則有

將式(4)展開可得

重新定義Y(t)=X(t)，R(t)=U(t)及R(t-1)=[V(t)TU(t-1)]，Y(1)=V(1)TX(1)，可得

令D(t)=R(t)S(t)，則式(6)改寫為

2.2RS系統(tǒng)的Ⅱ，Ⅳ象限穩(wěn)定性分析

2.2.1 Ⅱ，Ⅳ象限狀態(tài)變化 對于一個二階離散線性系統(tǒng)

在第Ⅱ象限的初始相量，當σ1(k)gt;σ2(k),σ2(k)lt;1，σ1(k)gt;1，且π/2lt;θ(k)lt;π，初始點位于Ⅱ象限時，建立一個點經(jīng)過一次RS變換后，角度與其反向角度的差值運動方程為

令f(κ(k))=0，可得

由此，特征根方程為

若能得斜率κ(k)經(jīng)一個R(k)S(k)變化后，斜率為κ(k+1)且位于第Ⅳ象限的(-∞，κ*(k+1))之間;而經(jīng)一次R(k+1)S(k+1)變化后，斜率為κ(k+2)且位于第Ⅱ象限的(-∞，κ1(k+2))之間，即

則可得該RS系統(tǒng)是不穩(wěn)定的.

3 實驗驗證

3.1Krawtchouk多項式遞歸式穩(wěn)定性分析

Krawtchouk多項式的三項遞歸迭代公式為

在x=390，p=0.1，0.3，0.9情況下，將Krawtchouk多項式整理為離散線性時變系統(tǒng)，其狀態(tài)矩陣分解為兩個旋轉(zhuǎn)矩陣和一個斜變換，經(jīng)SVD分解后可得:

圖2 Krawtchouk的RS系統(tǒng)在Ⅱ，Ⅳ象限跳變發(fā)散情況Fig.2 RS Krawtchouk system jumps in Ⅱ,Ⅳ quadrants

2) 對角陣S(k)的主對角線參數(shù)σ1(k)，σ2(k);

RS系統(tǒng)在Ⅱ，Ⅳ象限跳變發(fā)散，如圖2所示.各個SVD分解后的數(shù)值，如圖3所示.

(a) θ(k)的范圍 (b) 奇異值σ2(k) (c) 奇異值σ1(k)

(d) κ*(k) (e) κ1(k)圖3 Krawtchouk的RS系統(tǒng)參數(shù)計算值Fig.3 Krawtchouk′s RS system parameters calculated value

3.2Jacobsthal數(shù)列遞歸式穩(wěn)定性分析

Jacobsthal數(shù)列的三項遞歸迭代公式為

圖4 Jacobsthal的RS系統(tǒng)在Ⅱ象限跳變發(fā)散情況Fig.4 RS Jacobsthal system jumps in Ⅱ quadrant

在x=0.7，N=400的情況下，將Krawtchouk多項式整理為離散線性時變系統(tǒng)，其狀態(tài)矩陣分解為兩個旋轉(zhuǎn)矩陣和一個斜變換，經(jīng)SVD分解后可得

2) 對角陣S(k)的主對角線參數(shù)σ1(k)，σ2(k);

RS系統(tǒng)在Ⅱ象限發(fā)散，如圖4所示.各個SVD分解后的數(shù)值，如圖5所示.

(a) θ(k)的范圍 (b) 奇異值σ1，σ2 (c) κ′(k)與κ2(k)的關系圖5 Jacobsthal的RS系統(tǒng)參數(shù)計算值Fig.5 Jacobsthal′s RS system parameters calculated value

4 Krawtchouk多項式圖像重構

結合前面的實驗分析，在x=390，p=0.1，0.3，0.9的情況下，Krawtchouk多項式重構的圖像，如圖6所示.由圖6可知：當p=0.1時，Krawtchouk多項式的遞歸計算誤差已經(jīng)增大，只能重構圖像的部分；當p=0.3時，誤差依舊很大，導致也只能重構部分的圖像；當p=0.5時，Krawtchouk多項式遞歸計算的誤差慢慢減小，重構的效果慢慢變好；隨著階數(shù)的增加，當p=0.9時，重構圖像效果與p=0.1和p=0.3的圖基本一樣.

(a) p=0.1

(b) p=0.3

(c) p=0.5圖6 不同p值的Krawtchouk多項式圖像重構Fig.6 Image reconstruction of Krawtchouk polynomials with different p values

圖7 Krawtchouk峰值信噪比Fig.7 Krawtchouk peak signal to noise ratio

根據(jù)圖像評價標準，分別作出Krawtchouk的p值(Kp)為0.1，0.3，0.5的峰值信噪比(RPSN=10·log(2552/MSE)，MSE為均方差)，其值越高說明重構圖像效果越好，如圖7所示.由圖7可知：Krawtchouk多項式的峰值信噪比隨著階數(shù)的增加而增加，到一定程度時，其值迅速下降.說明高階的時候其誤差是變大的導致其發(fā)散,驗證了Krawtchouk正交多項式在Ⅱ,Ⅳ象限發(fā)散的情況.

5 結束語

分析和研究離散時變線性系統(tǒng)，將系統(tǒng)的狀態(tài)矩陣進行奇異值分解，得到新的等效狀態(tài)方程.通過分析Krawtchouk正交多項式與Jacobsthal數(shù)列遞歸式，計算時，通過不同的判據(jù)，說明了Krawtchouk矩陣在Ⅱ,Ⅳ象限跳變的原因，也說明了Jacobsthal數(shù)列在第Ⅱ象限發(fā)散的原因.所進行的只是初步討論了Ⅱ,Ⅳ象限的情況，其他象限情況還有待進一步研究.

[1] 王宏偉，趙國慶.遞歸算法的參數(shù)設置[J].電波科學學報，2010，25(6):1187-1192,1234.

[2] 鞠憲龍.二階對角遞歸神經(jīng)網(wǎng)絡的算法研究及應用[D].哈爾濱:哈爾濱工程大學，2011.

[3] 趙堅.一般二階線性常系數(shù)齊次遞歸方程在數(shù)論中的應用[J].哈爾濱工業(yè)大學學報，2000，32(6):132-135.

[4] YAP P T，PARMMESRAN R，ONG S H.Image analysis by Krawtchouk moments[J].IEEE Transactions on Image Processing，2003，12(11):1367-1377.

[5] 龍愛芳，胡軍浩.基于Hermite插值的高精度數(shù)值積分公式[J].華僑大學學報(自然科學版)，2013，34(3):349-352.DOI:10.11830/ISSN.1000-5013.2013.03.0349.

[6] 田萌，王文劍.基于正交多項式的核函數(shù)性質(zhì)研究[J].模式識別與人工能，2014，27(5):385-393.

[7] 李炳坤.切比雪夫逼近多項式在非線性電路中的應用[J].華僑大學學報(自然科學版)，1992，13(4):558-562.DOI:10.11830/ISSN.1000-5013.1992.04.0558.

[8] 宮鳳強，李夕兵.基于Legendre正交多項式逼近法的結構可靠性分析[J].工程力學，2008，25(6):225-229.

[9] MUKUNDAN R，ONG S H，LEE P A.Image analysis by tchebichef moments[J].IEEE Transactions on Image Processing a Publication of the IEEE Signal Processing Society，2001，10(9):1357-1364.DOI:10.1109/83.941859.

[10] GAUTSCHI W.Computational aspects of three-term recurrence relations[J].Siam Review，1967，9(1):24-82.

[11] GAUTSCHI W.Is the recurrence relation for orthogonal polynomials always stable?[J].BIT，1993，33(2):277-284.DOI:10.1007/BF01989750.

[12] 關軼峰，李鐵壽.二階離散線性時變系統(tǒng)的一種穩(wěn)定性判據(jù)[J].計算技術與自動化，2003，22(4):12-15.

[13] MUKUNDAN R.A comparative analysis of radial-tchebichef moments and zernike moments[C]∥Procedings of the British Machine Vision Conference.London:BMVA Press,2009:16(1-7).DOI:10.5244/C.23.16.

[14] 張海艷，高尚兵.圖像分割中改進空間約束貝葉斯網(wǎng)絡模型的應用[J].計算機應用，2017，37(3):823-826,831.DOI:10.11772/j.issn.1001-9081.2017.03.823.

(責任編輯： 陳志賢英文審校： 吳逢鐵)

NumericalStabilityMethodofSecondOrderRecursiveSystemUsingSingularValueDecomposition

FU Bo， LIU Jiyuan， ZHAO Xilin， XU Guanghui, WANG Zipeng

(School of Electrical and Electronic Engineering， Hubei University of Technology， Wuhan 430068， China)

In order to solve the problem of stability of second order recursive systemsimply， the second order recursive system is transformed into second order discrete time-varying linear system and the stability of recursive system is discussed. Based on the stability analysis of second-order discrete linear time-varying systems， converting it into a reference signal (RS) system by singular value decomposition (SVD). Based on discrete orthogonal Krawtchouk polynomials and the Jacobsthal series, a new sufficient condition for discrete time-varying linear instability is proposed. The changes and new instability codes in the second and fourth quadrants are discussed and deduced. The simulation results verify the conclusion accuracy.

Krawtchouk polynomials; Jacobsthal sequences; singular value decomposition; recursive systems; linear discrete time-varying systems

10.11830/ISSN.1000-5013.201703080

TP 391

A

1000-5013(2017)06-0886-06

2017-03-30

付波(1973-)，男，教授，博士，主要從事圖像處理與模式識別的研究.E-mail:fubofanxx@mail.hbut.edu.cn.

國家自然科學基金資助項目(61072130， 51309094， 61603127)； 國家教育部留學回國人員科研啟動基金資助項目(20141685)； 湖北省科技廳重大科技專項項目(2013AE001)