超定非線(xiàn)性系統(tǒng)奇異解的可信驗(yàn)證

桑海風(fēng), 萬(wàn)保成

(1.北華大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 吉林 吉林 132013; 2.吉林大學(xué) 數(shù)學(xué)學(xué)院, 長(zhǎng)春 130012;3.吉林農(nóng)業(yè)大學(xué) 信息技術(shù)學(xué)院, 長(zhǎng)春 130118)

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

超定非線(xiàn)性系統(tǒng)奇異解的可信驗(yàn)證

桑海風(fēng)1,2, 萬(wàn)保成2,3

(1.北華大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院, 吉林 吉林 132013; 2.吉林大學(xué) 數(shù)學(xué)學(xué)院, 長(zhǎng)春 130012;
3.吉林農(nóng)業(yè)大學(xué) 信息技術(shù)學(xué)院, 長(zhǎng)春 130118)

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

超定非線(xiàn)性系統(tǒng); 可信誤差界; 奇異解

在密碼學(xué)、機(jī)器人學(xué)和校準(zhǔn)理論等領(lǐng)域中, 很多問(wèn)題最終都可歸結(jié)為超定非線(xiàn)性方程組的求解問(wèn)題[1].因此, 超定非線(xiàn)性方程組解的可信驗(yàn)證是應(yīng)用廣泛的可信驗(yàn)證問(wèn)題.Rump[2]首先給出了標(biāo)準(zhǔn)的可信驗(yàn)證方法, 該方法將浮點(diǎn)運(yùn)算用于嚴(yán)格證明, 解決了非奇異問(wèn)題的驗(yàn)證.對(duì)于奇異問(wèn)題, 如驗(yàn)證非線(xiàn)性系統(tǒng)奇異解的存在性, 首先要將該系統(tǒng)正則化, 得到一個(gè)新的系統(tǒng), 使得原來(lái)系統(tǒng)的奇異解成為新系統(tǒng)的解或者解的一部分, 然后再利用標(biāo)準(zhǔn)可信驗(yàn)證方法驗(yàn)證新系統(tǒng)的解.之后, Rump和Graillat[3]又提出了Jacobi矩陣秩虧為1的非線(xiàn)性系統(tǒng)二重根驗(yàn)證方法, 該方法通過(guò)將原方程組增加一個(gè)光滑變量, 并增加一個(gè)含n-1個(gè)變?cè)?、n個(gè)方程的方程組, 得到一個(gè)Jacobi矩陣非奇異的新系統(tǒng), 將驗(yàn)證原方程組二重根的奇異問(wèn)題轉(zhuǎn)化為驗(yàn)證新系統(tǒng)單根的非奇異問(wèn)題.Li等[4]研究了Jacobi矩陣秩虧為1的多項(xiàng)式系統(tǒng)孤立奇異解的可信驗(yàn)證, 通過(guò)將原方程組增加μ-1個(gè)光滑變量, 并增加μ-1個(gè)方程, 得到一個(gè)Jacobi矩陣非奇異的新系統(tǒng), 也將驗(yàn)證原方程組孤立奇異解的奇異問(wèn)題轉(zhuǎn)化為驗(yàn)證新方程組單根的非奇異問(wèn)題.

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

1 數(shù)值算法

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

本文假設(shè)所討論的超定系統(tǒng)f滿(mǎn)足下述條件:

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

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

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

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

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

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

基于上述符號(hào), 定義邊界系統(tǒng)

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

事實(shí)上,g′(x)可由求解下面線(xiàn)性方程組得到.任取j, 對(duì)式(2)關(guān)于變?cè)獂j求導(dǎo)得

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

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

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

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

基于上述理論, 設(shè)計(jì)如下數(shù)值算法.

算法1邊界系統(tǒng)的牛頓法.

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

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

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

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

8) 計(jì)算

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

2 可信驗(yàn)證算法

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

Moore[8]給出了非線(xiàn)性系統(tǒng)解存在性可驗(yàn)證的充分條件; Rump[9]進(jìn)一步提出了標(biāo)準(zhǔn)的可信驗(yàn)證定理.

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

基于上述理論, 設(shè)計(jì)如下算法.

算法2可信驗(yàn)證算法.

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

3 數(shù)值算例

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

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

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

[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.

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

國(guó)家自然科學(xué)基金(批準(zhǔn)號(hào): 11171133)和吉林省教育廳科學(xué)技術(shù)研究項(xiàng)目(批準(zhǔn)號(hào): 2014213).

O242.29

A

1671-5489(2014)06-1162-05

10.13413/j.cnki.jdxblxb.2014.06.10

趙立芹)