范數度量下的三項遞歸式數值穩定性判據

付 波，胡 什，趙熙臨，徐光輝

范數度量下的三項遞歸式數值穩定性判據

付 波，胡 什，趙熙臨，徐光輝

（湖北工業大學電氣與電子工程學院，湖北武漢430068）

正交矩的數值穩定性分析是近年來圖像處理中研究的熱點。研究對象是正交矩解析式中最為常用的三項遞歸公式，介紹正交矩的三項遞歸公式及數值穩定性的概念；然后以歐幾里得范數作為恒量其穩定性的標準提出一種基于其計算系數極限存在與否判斷其數值穩定性的判據，并給予詳盡證明；最后運用兩個實例證明此判據的可行性。

正交矩三項遞歸式；歐幾里得范數；計算系數極限；數值穩定性

作為正交矩計算基礎的三項遞歸公式在進行高階計算時存在數值不穩定的問題。R.Mukundan在研究Tchebichef矩時提出了隨著正交矩分析的圖像越來越大，高階矩的計算過程中各種誤差會造成矩數值計算不穩定［1］，最終導致圖像重構時模糊。G.R.Amayeh等［2］試圖采用提高正交矩計算精度的方法來抑制其傳遞誤差，但僅僅只是對其作出了抑制，無法從根源上解決問題。郭［3］指出其誤差根源在于計算機系統本身產生的截斷誤差和舍入誤差，所提出的一種將三項遞歸式轉化為離散狀態方程來研究其穩定性的方法，是目前較令人信服的方法，然而其隨后提出來的利用李亞普洛夫方法解決系統穩定性的方法適用范圍過窄，只能判斷Legendre矩以及Tchebichef矩等少量矩的穩定性。

筆者在總結上述學者工作的同時，也對常見的幾種正交矩三項遞歸式進行了細致的研究，得出了一個規律：系數極限存在的正交矩基函數一般具有數值穩定性，而系數極限為無窮的正交矩基函數則不具有數值穩定性。立足于上述規律，筆者提出了判斷正交矩三項遞歸公式穩定性的一個充分條件和判斷其不穩定性的一個充分條件，并從歐幾里得范數和距離空間的角度對其進行了嚴謹的證明。最后利用此判據分別驗證了極限存在的Legendre矩的數值穩定性以及極限為無窮的Tchebichef矩的不穩定性，證明了其可行性。

1 正交矩三項遞歸公式

在正交矩的解析方法中，利用三項遞歸公式進行解析是最常使用的方法：

若需要計算較高階數上述公式的數值，則需要計算機等手段的幫助。然而在計算機的計算過程中，系統本身產生的計算誤差會使觀測值異于實際值。上述計算誤差有可能會在計算過程中被放大，最終影響計算所得的終值。因此分析計算誤差的傳遞過程和三項遞歸算法的數值穩定性勢在必行。在這里采用郭［3］的做法將其化為狀態方程來進行研究，設三相遞歸公式的觀測值為Pk，其真實值為P＊k，計算誤差為ek，起始二項為P0和P1，P0和P1的誤差為e0和e1，可以將式（1）變為：

易得，計算真值滿足：

將上式化為矩陣形式，即：

計算誤差滿足：

將上式化為矩陣形式，即：

在實際計算過程中，三項遞歸算法的數值穩定性涉及兩個方面：1）真值計算系統（即式（4））本身的穩定性；2）觀測誤差系統（即式（6））的穩定性。當且僅當式（4）和式（6）所代表的系統均收斂，即代表觀測值的系統與代表遞歸誤差的系統均收斂時，整個三項算法才具有數值穩定性。而上述兩個系統的傳遞函數均為：，是一類系統，因此只需研究上述任一系統的穩定性即可。由此將算法數值穩定性本質轉化為研究基于式（6）的二階系統的穩定性。若式（6）所代表的系統是穩定的，則說明遞歸誤差不會在計算中被逐步放大，仍然是可以抑制的，它代表的遞歸算法具有數值穩定性；反之則是發散的，其遞歸算法不具有數值穩定性。因此只需判斷系統（6）的穩定性即可判斷遞歸算法的數值穩定性。

正交矩三項遞歸公式的計算系數A與B會隨階數的增加而變化，故其形成的系統（6）為離散線性時變系統，該類系統的穩定性較難判斷，目前學術界仍無一定論。在這里文獻［4］的方法是利用較為常見的李雅普洛夫第二法［4］來判斷，然而值得注意的是：李亞普洛夫定義下的穩定性與三相遞歸式的數值穩定性還是有細微區別的，無法一概而論；且李雅普洛夫方法過于復雜，對于每一個不同的正交矩多項式需尋求不同的李雅普洛夫函數來進行對應，大大增加了判斷的難度。筆者在下節中的研究將回歸誤差傳遞的本質，直接從系統（6）的傳遞函數矩陣入手，以歐幾里得范數作為恒量其三項遞歸式數值穩定性的標準，提出兩個較為簡潔的穩定性判據，并佐以詳細的證明。

2 范數度量下數值穩定性判據

判據1：正交矩三項遞歸公式（1）數值穩定的充分條件是：其計算系數A或B極限都存在且不為無窮。

判據2：正交矩三項遞歸公式（1）數值不穩定的充分條件是：其計算系數A或B至少有一者極限為無窮。

證明：由上文分析得，三項遞歸公式（1）的數值穩定性大致等價于二階系統（6）的穩定性，系統（6）的傳遞函數矩陣為：

設M2×2（C）是數域C上的方陣，按照通常矩陣的加法與數乘構成的2×2維線性空間［5］，對于冪級數常項矩陣G（k）＝（a（k）ij）2×2∈M2×2（C），定義以下范數：

則（Mn×n（C），‖.‖2）是賦范線性空間。在此賦范線性空間下G（k）的范數為：

當計算系數A（k）與B（k）均極限都存在且不為無窮時，上述范數G（k）的極限‖G（k）‖存在且不為無窮。這表明代表的遞歸誤差不會在進行高階計算時放大，即使在計算至無窮階時誤差仍然是有界的，根據上文的推論可以判斷此種計算系數下的三項遞歸公式具有數值穩定性，判據1充分性得證。

當計算系數A（k）與B（k）至少有一為無窮時，上述范數的極限‖G（k）‖為無窮，此時其代表的遞歸誤差會在進行高階計算時被無限放大，最終會使計算值大幅度偏離真值。由上文的討論可知：此種計算系數下的三項遞歸公式不具有數值穩定性，判據2充分性得證。

3 實例驗證

本章將利用上文的判據分別對Legendre矩三項遞歸公式和Krawtchouk矩三項遞歸公式進行數值穩定性判斷。

3.1 Legendre矩三項遞歸公式

Legendre矩三項遞歸公式為：得到其計算系數為：

取L（0）＝1，L（1）＝0.5；x∈［－1，1］，在c＋＋大數庫中計算0至400階的Legendre矩三項遞歸公式的誤差。圖1代表計算誤差隨計算階數的增加的變化情況，其中圖1a代表絕對誤差的變化，圖1b代表相對誤差的變化情況，單位用Arbitrary Precision Arithmetic［6，7］對數形式表示。由圖1可知：在0至400階的計算過程中其絕對誤差L（k）逐漸趨于穩定，相對誤差E（k）除了在150階和220階左右較大之外其余均小于e－12，說明整個傳遞誤差的遞歸過程是收斂［8］的，Legendre矩三項遞歸公式具有數值穩定性，這與筆者利用判據1得出來的結論一致，說明了判據1的有效性。

圖1 Legendre多項式迭代計算誤差隨階數k變化圖

3.2 Krawtchouk三項遞歸公式

Krawtchouk矩三項遞歸公式為：

其計算系數為：此時，由于系數N，p的數值不確定性，求得：由判據2可知：Krawtchouk矩三項遞歸公式在相對意義上不具有數值穩定性。

與Legendre矩不同的是，Krawtchouk多項式計算系數中含有變量參數p。因此取x＝398時，p＝0.1，p＝0.3，p＝0.5，p＝0.7，p＝0.9五組數據對Krawtchouk多項式進行迭代計算測試。其相對誤差如圖2a所示，絕對誤差如圖2b所示。

圖2 Krawtchouk多項式迭代計算誤差隨階數k變化圖

由圖2可知：當p取以上五個數據時其絕對誤差和相對誤差均是發散的，其遞歸誤差在一定范圍內無法得到抑制，因此Krawtchouk矩三項遞歸公式不具有數值穩定性，這與判據2所得出的結論完全相同，證明了判據2的可行性。

4 結論

本文從一個新的角度對正交矩三相遞歸式的穩定性做出了分析，給出了一種根據極限判斷其數值穩定性的判據。對比文獻［3］所提出的判據，該判據僅需判斷三相遞歸式的計算系數極限存在與否即可判斷其數值穩定性，因此可以更為靈活快捷地應用于正交矩穩定性分析中。目前僅有一類極限不存在但是不為無窮的三項多項式無法利用該判據判斷穩定性，如何判斷這一類三項多項式的穩定性也是筆者下一步研究的焦點問題。

［1］ Mukundan R，Ramakrishnan K R.Fast computation of legendre and zernike moments［J］.Pattern Recognition，1995，28（9）：1433－1442.

［2］ Amayeh G，Erol A，Bebis G，et al.Accurate and efficient computation of high order zernike moments［C］.ISVC 2005：462－469.

［3］ 郭浩，范秀香，付波，等.三項遞歸公式的數值穩定性分析［J］.湖北工業大學學報，2016（2）：58－61.

［4］ Mukundan R，Ong S H，Lee P A.Image analysis by tchebichef moments［J］.IEEE Transactions on Image Processing.2001，10（9）：1357－1364.

［5］ 程曹宗.應用泛函分析［M］.北京：機械工業出版社，2008.

［6］ Xiao B，Ma J F，Wang X.Image analysis by bessel–fourier moments［J］.Pattern Recognition，2010，43（8）：2620－2629.

［7］ Ziliang P，Rigeng W，Yunlong S.Image description with chebyshev－fourier moments.［J］.Journal of the Optical Society of America A Optics Image Science ＆Vision，2002，19（9）：1748－54.

［8］ Zhu H Q，Shu H Z，Liang L，et al.Image analysis by discrete orthogonal dual－hahn moments［J］.Pattern Recognition Letters.2007，28：1688－1794.

Numerical Stability Criterion of the Three Recursion Relations Based on Norm Measurement

FU Bo，HU Shi，ZHAO Xilin，，XU Guanghui
（School of Electrical and Electronic Engineering，Hubei Univ.of Tech.，Wuhan 430068，China）

Numerical stability analysis of orthogonal moments is one of the hot topics in the field of image analysis in recent years.This paper studies the most commonly used three recursive formulas among the orthogonal moments analytic ones.First，the concepts of three recursion formulas and numerical stability of orthogonal moments were introduced；Then a new stability criterion was proposed to judge the stability of three recursion relations based on Euclidean norm standard，which was proofed in detail；Finally，two examples were used to demonstrate the feasibility of this criterion.

three recursion relations of orthogonal moments；euclidean norm；limit of calculation factors；numerical stability

TP13

A

［責任編校：張巖芳］

1003－4684（2017）04－0035－04

2016－06－27

國家自然科學基金（61072130；51109088）；武漢市科技攻關計劃項目（2013012401010845）；湖北工業大學科研基金項目（BSQD12107）；廣東省工業攻關項目（2011B010100037）

付 波（1975－），男，湖北武漢人，工學博士，湖北工業大學教授，研究方向為圖像處理