欠定非線性系統極小二范數解的可信誤差界

李 喆,桑海風,徐維華

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

?

欠定非線性系統極小二范數解的可信誤差界

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

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

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

欠定系統;極小二范數解;可信驗證

0 引 言

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

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

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

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

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

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

1 預備知識

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

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

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

2 主要結果

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

(1)

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

(2)

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

(3)

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

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

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

(4)

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

(5)

的極小值點.

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

(6)

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

(7)

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

(8)

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

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

算法1

輸入:

1)f(x)=0(m個方程n個變元的具有二階連續偏導數的欠定非線性系統);

2)數值秩容差ε1;

3)數值迭代容差ε2;

4)最大迭代次數N;

輸出:

2)或者“失敗”.

步驟:

1)初始iter=0.

3)初始iter=0.

4)區間牛頓迭代.

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

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

① 選取in-m+1<…

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

3 數值算例

2)計算得

4)計算包含系統

的零點區間向量:

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

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

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

為包含欠定系統f(x)=0極小二范數解的可信區間.

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

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

O241.3

：A

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