李 喆,桑海風(fēng),徐維華

(1.長春理工大學(xué) 理學(xué)院,長春 130022;2.自動(dòng)推理與認(rèn)知重慶市重點(diǎn)實(shí)驗(yàn)室,重慶 400714;3.符號計(jì)算與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室,長春 130012;4.北華大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,吉林 吉林 132013)

?

欠定非線性系統(tǒng)極小二范數(shù)解的可信誤差界

李 喆1,2,3,桑海風(fēng)4,徐維華1

(1.長春理工大學(xué) 理學(xué)院,長春 130022;2.自動(dòng)推理與認(rèn)知重慶市重點(diǎn)實(shí)驗(yàn)室,重慶 400714;3.符號計(jì)算與知識(shí)工程教育部重點(diǎn)實(shí)驗(yàn)室,長春 130012;4.北華大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,吉林 吉林 132013)

考慮欠定非線性系統(tǒng)極小二范數(shù)解的可信驗(yàn)證問題.欠定非線性系統(tǒng)的極小二范數(shù)解為解向量二范數(shù)的極小值點(diǎn),對給定的欠定非線性系統(tǒng),將方形非線性系統(tǒng)單根的可信驗(yàn)證方法與對稱正定矩陣的可信驗(yàn)證方法相結(jié)合,給出計(jì)算Jacobi矩陣為列滿秩欠定非線性系統(tǒng)極小二范數(shù)解的可信誤差界算法.

欠定系統(tǒng);極小二范數(shù)解;可信驗(yàn)證

0 引 言

所謂可信驗(yàn)證,就是對給定的非線性求解問題,給出該問題的一個(gè)近似解及其相應(yīng)的誤差界,使得在近似解的誤差界范圍內(nèi)一定存在一個(gè)精確解.Rump[1]給出了系數(shù)陣為一般稠密矩陣的線性方形系統(tǒng)求解的可信性驗(yàn)證方法.該算法寫入在MATLAB中的INTLAB軟件包中,命名為Verifylss函數(shù).對于系數(shù)陣為區(qū)間矩陣的線性系統(tǒng),Verifylss函數(shù)輸出一個(gè)區(qū)間向量,該區(qū)間向量包含該區(qū)間線性系統(tǒng)的所有可能解.對于欠定線性系統(tǒng),Rump[2]給出了計(jì)算極小二范數(shù)解的可信誤差界的算法.給定A∈n×m,n

‖A+b‖=min{‖x‖2:Ax=b},

其中A+為A的廣義逆矩陣.Rump通過計(jì)算增廣系統(tǒng)

零點(diǎn)的可信誤差界得到了欠定系統(tǒng)Ax=b極小二范數(shù)解的可信誤差界.Rump的方法不僅適用于系數(shù)陣稠密的線性系統(tǒng),對于系數(shù)陣稀疏的線性系統(tǒng)也有效.Miyajima[3]給出了欠定線性系統(tǒng)極小二范數(shù)解的算法,并證明了該算法得到的可信逐點(diǎn)誤差界每個(gè)分量都小于等于Rump[2]給出的算法.之后,Rump[4]又利用給定的近似值誤差界,改進(jìn)了Miyajima[3]的方法,該方法并未提高M(jìn)iyajima方法的精度,但給出了Miyajima方法一個(gè)很好的表示形式,這個(gè)表示形式適用于數(shù)值計(jì)算的可信驗(yàn)證.

Moore[5]給出了非線性系統(tǒng)單根存在的充分條件,在此基礎(chǔ)上,Krawczyk[6]將牛頓迭代法應(yīng)用于區(qū)間計(jì)算,以此驗(yàn)證非線性系統(tǒng)的單根.Rump[7]改善了區(qū)間牛頓迭代法使其能更好地實(shí)際應(yīng)用,提出了非線性系統(tǒng)單根的可信驗(yàn)證定理,并在INTLAB軟件中實(shí)現(xiàn),命名為Verifynlss函數(shù).

文獻(xiàn)[8-11]討論了欠定非線性系統(tǒng)零點(diǎn)的數(shù)值算法，文獻(xiàn)[12]通過將欠定非線性系統(tǒng)的某些變元特定化,給出了欠定非線性系統(tǒng)零點(diǎn)的可信驗(yàn)證算法.但目前還沒有針對欠定非線性系統(tǒng)極小二范數(shù)解的可信性驗(yàn)證算法.本文考慮欠定非線性系統(tǒng)極小二范數(shù)解的可信誤差界計(jì)算,將欠定非線性系統(tǒng)極小二范數(shù)解的計(jì)算轉(zhuǎn)化為優(yōu)化問題的穩(wěn)定點(diǎn)計(jì)算,利用方形非線性系統(tǒng)的單根可信驗(yàn)證方法計(jì)算優(yōu)化問題穩(wěn)定點(diǎn)的可信誤差界,利用對稱正定矩陣的可信驗(yàn)證方法判斷穩(wěn)定點(diǎn)是否為極值點(diǎn).

1 預(yù)備知識(shí)

設(shè)A為區(qū)間對稱矩陣,若對其中任意一個(gè)實(shí)對稱矩陣都正定,則稱區(qū)間對稱矩陣A正定.

引理1[13]給定對稱矩陣M,R∈n×n,令Σ=[M-R,M+R]∈In×n.如果存在c∈,使得‖R‖2≤c且M-cI為正定陣,則所有實(shí)對稱矩陣A∈Σ正定.

定理1[7]設(shè)函數(shù)f:n→n,其中f=(f1,…,fn)∈C1.給定初始近似解n,初始區(qū)間X∈In,且0∈X,R∈n×n.設(shè)區(qū)間矩陣M∈In×n滿足條件?Mi,:.若

2 主要結(jié)果

設(shè)f:n→m,f=(f1,…,fm)T,n>m,其中f1,…,fm具有二階連續(xù)偏導(dǎo)數(shù).欠定非線性系統(tǒng)f(x)=0的極小二范數(shù)解為約束優(yōu)化問題

(1)

的極小值點(diǎn).引入Lagrange乘子w=(w1,…,wm)T,構(gòu)造Lagrange函數(shù)

(2)

則L(x,w)的穩(wěn)定點(diǎn)為條件極值(1)的可能極值點(diǎn).L(x,w)的穩(wěn)定點(diǎn)為系統(tǒng)

(3)

的零點(diǎn),其中Jf(x)為系統(tǒng)f(x)=0的Jacobi矩陣.

命題1[1]設(shè)f:n→m,f=(f1,…,fm)T,n>m,其中f1,…,fm具有二階連續(xù)偏導(dǎo)數(shù).對于系統(tǒng)L(x,w)=0,給定其近似解若Verifynlss函數(shù)能成功計(jì)算出包含該系統(tǒng)真解的區(qū)間向量(X,W)T,則f(x)=0在的Jacobi矩陣行滿秩.

其中M(x,w)的第i行第j列元素為

(4)

因此,條件極值(1)的極小值點(diǎn)等價(jià)于函數(shù)

(5)

的極小值點(diǎn).

令Hg(x(1))表示g(x(1))的Hessian矩陣,則

(6)

下面計(jì)算Hg(x(1)).對非線性系統(tǒng)f(x(1),h(x(1)))=0關(guān)于每個(gè)自變量xi(1≤i≤n-m)求導(dǎo)可得

(7)

再對系統(tǒng)(7)關(guān)于每個(gè)自變量xj(1≤j≤n-m)求導(dǎo)可得

(8)

因此,令x=X,利用Verifylss函數(shù)求解線性系統(tǒng)(7),(8),可得區(qū)間向量U(i),U(i,j)(1≤i≤j≤n-m),使得

利用U(i),U(i,j)可得到區(qū)間對稱矩陣H,使得H?Hg(X(1)).

算法1

輸入:

1)f(x)=0(m個(gè)方程n個(gè)變元的具有二階連續(xù)偏導(dǎo)數(shù)的欠定非線性系統(tǒng));

2)數(shù)值秩容差ε1;

3)數(shù)值迭代容差ε2;

4)最大迭代次數(shù)N;

輸出:

2)或者“失敗”.

步驟:

1)初始iter=0.

3)初始iter=0.

4)區(qū)間牛頓迭代.

② 如果Verifynlss函數(shù)運(yùn)行不成功,則返回“失敗”,算法終止.

5)驗(yàn)證Hessian矩陣的正定性.

① 選取in-m+1<…

④ 利用Isspd函數(shù)驗(yàn)證Hg(X(1))的正定性,如果成功,則返回X=X1:n;否則,返回“失敗”.

3 數(shù)值算例

2)計(jì)算得

4)計(jì)算包含系統(tǒng)

的零點(diǎn)區(qū)間向量:

5)令X(1)=X1,X(2)=(X2,X3)T,則區(qū)間矩陣Jf(X):,2:3為可逆區(qū)間矩陣,根據(jù)式(6),計(jì)算Hessian陣為

Hg(X(1))=[5.999 999 999 999 99,6.000 000 000 000 01].

利用INTLAB軟件中的Isspd函數(shù)可驗(yàn)證Hg(X(1))為正定矩陣,故

為包含欠定系統(tǒng)f(x)=0極小二范數(shù)解的可信區(qū)間.

[1] Rump S M.Kleine Fehlerschranken Bei Matrixproblemen [D].Karlsruhe:Universit Karlsruhe,1980.

[2] Rump S M.Verified Bounds for Least Squares Problems and Underdetermined Linear Systems [J].SIAM J Matrix Anal Appl,2012,33(1):130-148.

[3] Miyajima S.Componentwise Enclosure for Solutions in Least Squares Problems and Underdetermined Systems [J].Linear Alger Appl,2014,444:28-41.

[4] Rump S M.Improved Componentwise Verified Error Bounds for Least Squares Problems and Underdetermined Linear Systems [J].Numer Algor,2014,66(2):309-322.

[5] Moore R E.A Test for Existence of Solutions to Nonlinear System [J].SIAM J Numer Anal,1977,14(4):611-615.

[6] Krawczyk R.Newton-Algorithmen Zur Bestimmung Von Nullstellen Mit Fehlerschranken [J].Computing,1969,4(3):187-201.

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

[8] Meyn K H.Solution of Underdetermined Nonlinear Equations by Stationary Iteration Methods [J].Numer Math,1983,42(2):161-172.

[9] Walker H F,Watson L T.Least-Change Secant Update Methods for Underdetermined Systems [J].SIAM J Numer Anal,1990,27(5):1227-1262.

[10] Martínez J M.Quasi-Newton Methods for Solving Underdetermined Nonlinear Simultaneous Equations [J].J Comput Appl Math,1991,34(2):171-190.

[11] CHEN Xiaojun,Yamamoto T.Newton-Like Methods for Solving Underdetermined Nonlinear Equations with Nondifferentiable Terms [J].J Comput Appl Math,1994,55(3):311-324.

[12] CHEN Xiaojun,Womersley R S.Existence of Solutions to Systems of Underdetermined Equations and Spherical Designs [J].SIAM J Numer Anal,2006,44(6):2326-2341.

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

(責(zé)任編輯：趙立芹)

VerifiedErrorBoundsforMinimum2-NormSolutionsofUnderdeterminedNonlinearSystems

LI Zhe1,2,3,SANG Haifeng4,XU Weihua1

(1.SchoolofScience,UniversityofScienceandTechnology,Changchun130022,China;2.AutomatedReasoningandCognitionKeyLaboratoryofChongqing,Chongqing400714,China;3.KeyLabofSymbolicComputationandKnowledgeEngineeringofMinistryofEducation,Changchun130012,China;4.CollegeofMathematicsandStatistics,BeihuaUniversity,Jilin132013,JilinProvince,China)

This paper deals with the verification for minimum 2-norm solutions of underdetermined nonlinear systems.The minimum 2-norm solution of underdetermined nonlinear system is the minimum point of the 2-norm of solution vectors.For the given undetermined nonlinear system,combining the verification for simple solutions of square systems with the verification for symmetric positive definite matrices presented an algorithm for verifying minimum 2-norm solutions of underdetermined nonlinear systems with full rank Jacobian matrices.

underdetermined system;minimum 2-norm solution;verification

10.13413/j.cnki.jdxblxb.2015.03.12

2014-10-13.

李 喆(1981—),女,漢族,博士，講師,從事計(jì)算機(jī)代數(shù)的研究,E-mail:zheli200809@163.com.通信作者:桑海風(fēng)(1982—),男,漢族,博士，講師,從事計(jì)算機(jī)代數(shù)的研究,E-mail:sanghaifeng2008@163.com.

國家自然科學(xué)基金(批準(zhǔn)號:11326209;11171133;91118001)和自動(dòng)推理與認(rèn)知重慶市重點(diǎn)實(shí)驗(yàn)室開放課題基金(批準(zhǔn)號:CARC2014002).

O241.3

：A

：1671-5489(2015)03-0414-05