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

李 喆,桑海風,徐維華

(1.長春理工大學 理學院,長春 130022;2.自動推理與認知重慶市重點實驗室,重慶 400714;3.符號計算與知識工程教育部重點實驗室,長春 130012;4.北華大學 數(shù)學與統(tǒng)計學院,吉林 吉林 132013)

?

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

李 喆1,2,3,桑海風4,徐維華1

(1.長春理工大學 理學院,長春 130022;2.自動推理與認知重慶市重點實驗室,重慶 400714;3.符號計算與知識工程教育部重點實驗室,長春 130012;4.北華大學 數(shù)學與統(tǒng)計學院,吉林 吉林 132013)

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

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

0 引 言

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

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

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

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

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

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

1 預備知識

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

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

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

2 主要結(jié)果

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

(1)

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

(2)

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

(3)

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

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

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

(4)

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

(5)

的極小值點.

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

(6)

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

(7)

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

(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個方程n個變元的具有二階連續(xù)偏導數(shù)的欠定非線性系統(tǒng));

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

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

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

輸出:

2)或者“失敗”.

步驟:

1)初始iter=0.

3)初始iter=0.

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

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

5)驗證Hessian矩陣的正定性.

① 選取in-m+1<…

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

3 數(shù)值算例

2)計算得

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

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

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

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

利用INTLAB軟件中的Isspd函數(shù)可驗證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.

(責任編輯：趙立芹)

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—),女,漢族,博士，講師,從事計算機代數(shù)的研究,E-mail:zheli200809@163.com.通信作者:桑海風(1982—),男,漢族,博士，講師,從事計算機代數(shù)的研究,E-mail:sanghaifeng2008@163.com.

國家自然科學基金(批準號:11326209;11171133;91118001)和自動推理與認知重慶市重點實驗室開放課題基金(批準號:CARC2014002).

O241.3

：A

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