桑海風, 萬保成

(1.北華大學 數學與統計學院, 吉林 吉林 132013; 2.吉林大學 數學學院, 長春 130012;3.吉林農業(yè)大學 信息技術學院, 長春 130118)

(f′(x*) R())=0, (f′(x*) R())=0.

超定非線性系統奇異解的可信驗證

桑海風1,2, 萬保成2,3

(1.北華大學 數學與統計學院, 吉林 吉林 132013; 2.吉林大學 數學學院, 長春 130012;
3.吉林農業(yè)大學 信息技術學院, 長春 130118)

利用邊界矩陣和區(qū)間算法理論, 討論超定系統奇異解的數值解法及其可信驗證.提出一種新算法, 該算法輸出一個近似解及其相應的誤差界, 使得在近似解的誤差界范圍內必存在一個精確解.

超定非線性系統; 可信誤差界; 奇異解

在密碼學、機器人學和校準理論等領域中, 很多問題最終都可歸結為超定非線性方程組的求解問題[1].因此, 超定非線性方程組解的可信驗證是應用廣泛的可信驗證問題.Rump[2]首先給出了標準的可信驗證方法, 該方法將浮點運算用于嚴格證明, 解決了非奇異問題的驗證.對于奇異問題, 如驗證非線性系統奇異解的存在性, 首先要將該系統正則化, 得到一個新的系統, 使得原來系統的奇異解成為新系統的解或者解的一部分, 然后再利用標準可信驗證方法驗證新系統的解.之后, Rump和Graillat[3]又提出了Jacobi矩陣秩虧為1的非線性系統二重根驗證方法, 該方法通過將原方程組增加一個光滑變量, 并增加一個含n-1個變元、n個方程的方程組, 得到一個Jacobi矩陣非奇異的新系統, 將驗證原方程組二重根的奇異問題轉化為驗證新系統單根的非奇異問題.Li等[4]研究了Jacobi矩陣秩虧為1的多項式系統孤立奇異解的可信驗證, 通過將原方程組增加μ-1個光滑變量, 并增加μ-1個方程, 得到一個Jacobi矩陣非奇異的新系統, 也將驗證原方程組孤立奇異解的奇異問題轉化為驗證新方程組單根的非奇異問題.

本文利用邊界矩陣及區(qū)間算法理論, 討論秩虧為q的超定非線性系統奇異解的數值解法及其可信驗證, 給出了計算奇異解的一種數值算法和一種可信驗證算法.如果數值算法輸出超定系統的近似解, 則可信驗證算法輸出超定系統的一個近似解及其相應的誤差界, 使得在近似解的誤差界范圍內必存在超定系統的一個精確解.特別地, 該驗證算法不僅能驗證孤立奇異點, 而且也能驗證流形解上秩虧發(fā)生變化的點(即在該零點的任何一個小領域內, 相應Jacobi矩陣的秩都與該零點處Jacobi矩陣的秩不同).同時, 本文改進了文獻[5]中計算邊界系統Jacobi矩陣的方法, 使相應的計算量明顯降低.

1 數值算法

記矩陣A的第i行為Ai,:=(Ai,1,…,Ai,n),q階單位陣為Iq, 實數區(qū)間集合為I().令f:D?n→m(m>n)為超定非線性系統,x*∈n為f(x)=0的解,f′(x*)為f(x)在x*處的Jacobi矩陣.如果f′(x*)的秩為r=n-q, 則稱f′(x*)秩虧為q(1≤q≤n), 并稱x*為f(x)=0的奇異解.

本文假設所討論的超定系統f滿足下述條件:

(H1) 光滑性:f在x*的鄰域內滿足C2-Lipschitz條件;

(H2) 秩虧性:f′(x*)秩虧為q;

對足夠接近x*的x, 令η(x)與h(x)為

的唯一解, 令μ(x)與g(x)為

的唯一解, 其中α為隨機選取的m-n+q維向量.定義q×q階矩陣

B(x,α)=ηT(x)(μT(x)f″(x))η(x).

基于上述符號, 定義邊界系統

其中λ為m-n+q維光滑參數.顯然F(x,λ)的Jacobi矩陣為

事實上,g′(x)可由求解下面線性方程組得到.任取j, 對式(2)關于變元xj求導得

其中?g(x)/?xj為g′(x)的第j列,j=1,2,…,n.

注1根據式(2)與式(5)知, 計算g′(x)只需求解n+1個具有相同系數陣的線性方程組即可.而文獻[5]中g′(x)=ηT(x)(μT(x)f″(x)), 需計算q+1個方程組,q次3個矩陣乘積.故本文方法與文獻[5]中方法相比計算量明顯降低.特別地, 當矩陣為區(qū)間矩陣時, 計算量降低效果更顯著.

由上述討論及引理3, 可得:

證明: 由式(1)及條件(H3)(η*為Null(f′(x*))的一組基), 有

基于上述理論, 設計如下數值算法.

算法1邊界系統的牛頓法.

3) 隨機選取q維向量α;

4) 若k>N, 則返回“失敗”, 算法終止;

6) 利用式(3)及式(5), 分別計算g(xk)與g′(xk);

7) 利用式(3)及式(4), 分別計算F(xk,λk)與F′(xk,λk);

8) 計算

9) 若‖(Δxk,Δλk)‖2<ε2, 則返回(xk+1,λk+1)與q, 結束; 否則k∶=k+1, 返回步驟4).

2 可信驗證算法

實現線性方程組解的可信驗證函數是INTLAB中的Verifylss函數[7].對于系數陣為區(qū)間矩陣的線性方程組, Verifylss函數輸出區(qū)間向量, 該區(qū)間向量包含此區(qū)間線性方程組所有可能的解.

Moore[8]給出了非線性系統解存在性可驗證的充分條件; Rump[9]進一步提出了標準的可信驗證定理.

定理3[9]設函數f:D?n→n, 其中f=(f1,…,fn)∈C1.給定向量n, 區(qū)間向量n), 且以及矩陣T∈n×n, 且給定的區(qū)間矩陣n×n)滿足條件{?.如果

基于上述理論, 設計如下算法.

算法2可信驗證算法.

由定理3, 可得下述命題.

3 數值算例

下面的數值實驗基于Windows 7操作系統, 軟件分別是MAPLE 15(Digits∶=14)與MATLAB R2011a(INTLAB V6).對下列多項式系統執(zhí)行上述隱式版可信驗證算法, 可計算出非線性系統的近似解及相應的誤差界.

例1的解集為{x|x1-x2=0}, 奇異解x*=(0,0)嵌入流形x1=x2, 且f′(x)在點x*秩虧度比在其他解處的秩虧度高.

例2的解x*=(0,0)為孤立奇異點.

[1]Bardet M, Faugere J C, Salvy B.On the Complexity of Gr?bner Basis Computation of Semi-regular Overdetermined Algebraic Equations [C]//Proceedings of the International Conference on Polynomial System Solving.Paris: University of Paris Press, 2004: 71-74.

[2]Rump S M.Kleine Fehlerschranken bei Matrixproblemen [D].Karlsruhe, German: Institut Fur Angewandte Mathematik, Universitat Karlsruhe, 1980.

[3]Rump S M, Graillat S.Verified Error Bounds for Multiple Roots of Systems of Nonlinear Equations [J].Numerical Algorithms, 2010, 54(3): 359-377.

[4]LI Nan, ZHI Lihong.Verified Error Bounds for Isolated Singular Solutions of Polynomial Systems: Case of Breadth One [J].Theoret Comput Sci, 2013, 479: 163-173.

[5]SHEN Yunqiu, Ypma T J.Newton’s Method for Singular Nonlinear Equations Using Approximate Left and Right Nullspaces of the Jacobian [J].Appl Numer Math, 2005, 54(2): 256-265.

[6]Moore R E, Cloud M J, Kearfott R B.Introduction to Interval Analysis [M].Philadelphia: SIAM Press, 2009.

[7]Rump S M.Verification Methods: Rigorous Results Using Floating-Point Arithmetic [J].Acta Numer, 2010, 19: 287-449.

[8]Moore R E.A Computational Test for Convergence of Iterative Methods for Nonlinear Systems [J].SIAM J Numer Anal, 1978, 15(6): 1194-1196.

[9]Rump S M.Solving Algebraic Problems with High Accuracy [C]//Proceedings of the Symposium on a New Approach to Scientific Computation.San Diego: Academic Press, 1983: 51-120.

VerifiedMethodsofSingularSolutionsofOverdeterminedNonlinearSystems

SANG Haifeng1,2, WAN Baocheng2,3
(1.CollegeofMathematicsandStatistics,BeihuaUniversity,Jilin132013,JilinProvince,China;
2.CollegeofMathematics,JilinUniversity,Changchun130012,China;
3.CollegeofInformationTechnology,JilinAgriculturalUniversity,Changchun130118,China)

We studied the numerical method and verification for singular points of overdetermined nonlinear equations.And we proposed an algorithm on the basis of the bordered system and interval theory.It outputs an approximate solution and its error bound so as to make an exact solution exist within this computed bounds.

overdetermined nonlinear system; verified error bound; singular solution

2014-02-07.

桑海風(1982—), 男, 漢族, 博士研究生, 講師, 從事計算機代數的研究, E-mail: sanghaifeng2008@163.com.通信作者: 萬保成(1977—), 男, 漢族, 博士研究生, 副教授, 從事計算機代數的研究, E-mail: wanbaocheng@163.com.

國家自然科學基金(批準號: 11171133)和吉林省教育廳科學技術研究項目(批準號: 2014213).

O242.29

A

1671-5489(2014)06-1162-05

10.13413/j.cnki.jdxblxb.2014.06.10

趙立芹)