可信计算中若干问题的研究
|
摘要
可信计算是科学工程计算中的重要问题.而可信验证是其中一类基本问题.本文主要讨论非线性系统奇异解的可信验证与半实验点集的消逝理想的近似边界基问题.
非线性系统解的可信验证是应用广泛的一类问题.在火箭喷口受力分析,核磁共振机设计,数码机床控制等高风险应用领域中,很多问题最终都可以归结为非线性系统解的可信验证问题Rump于1983年给出了一种可信验证方法,解决了非线性系统单根存在性的验证问题.然而奇异解存在性的验证是一个病态问题,因为对非线性系统的系数作任意微小扰动,都可能导致一个孤立奇异解变成一族单根.因此研究奇异解存在性的验证具有重要的理论意义和应用价值.本文基于Rump的可信验证方法,研究了非线性系统奇异解的可信验证问题,得到了一系列结果,具体按章次介绍如下.
第二章研究了非线性系统f(x)=0的孤立奇异解和和一类非孤立奇异解的可信性验证方法,其中f:Rn→Rm,f=(f1,f2…,fm)T,f1,…,fm为解析函数.假设x为f(x)=0的解,如果存在包含x的某邻域,使得x为此邻域内的唯一解,则称x为孤立解;如果对任意包含x的邻域,都存在异于岔的其它解,则称岔为非孤立解；如果f的雅可比矩阵在岔处非满秩,则称x为奇异解.我们研究的一类非孤立奇异解x指的是f的雅可比矩阵在非孤立奇异解x处的秩小于在x邻域内其它任意点处的秩.
本章利用压缩技术,给出了一种正则化方法.利用f(x)=0,通过添加m-r个变量,n-r个方程,构造边界系统f1(x,y1)=0,使得(x,0)为f1(x,y1)=0的解,其中r为f的雅可比矩阵Jf(x)在f(x)=0的奇异解x处的秩.由f构造f1的过程称之为压缩.如果f1：Rm+n-r→Rm+n-r的雅可比矩阵Jf1(x)在解(x,0)处满秩,则可利用Rump的验证方法验证压缩系统f1(x,y1)=0的解的存在性与唯一性,从而可验证系统f(x)=0的奇异解或非孤立奇异解的存在性与唯一性.否则对f1(x,y1)=0按照上述方法继续压缩,构造新的边界系统.继续下去,如果Jk-1在其解处的秩亏度为q,则再添加q个变量,q个方程,得到新的系统fk(x,y1,...,yk)=0,使得(x,0,...,0)为其解.可以证明存在正整数σ,使得压缩σ次后,得到的Jfσ(x,y1,...,yσ)在其解处满秩.从而可以用Rump的可信验证方法验证其解,进而可验证系统f(x)=0的奇异解或非孤立奇异解的存在性与唯一性.
由于每一步都需计算雅可比阵,最后我们给出了计算雅可比矩阵的复杂度分析.
基于上述方法,本章提出了可信验证算法VSS,该算法输出原系统的解的一个区间,使得该区间内必定存在原系统的一个精确解.与其它正则化方法相比,我们的方法添加的方程个数较少,计算效率较高;不仅能验证孤立奇异解,而且也能验证雅可比矩阵在解处的秩小于在解邻域内除解之外任意点处的秩的非孤立奇异解；还可用来处理超定系统(nm)奇异解的可信验证;与其它验证雅可比矩阵秩亏为q的系统奇异解的方法相比,我们的方法不但能验证多项式系统的孤立奇异解,还能验证一般非线性函数系统奇异解.我们在Matlab中实现了算法VSS并且测试了大量的例子,数值实验表明,算法对于复的奇异解同样有效.
第三章介绍了欠定系统局部极小二范数解和超定系统局部极小二乘解的可信验证方法.设f：Rn→Rm,f=(f1,...,fm)T,f1,...fm在包含x的开集Ω内充分光滑.欠定系统f(x)=0(n>m)局部极小二范数解指的是约束优化问题的极小值点.通过引入Lagrange乘子λ=(λ1,...λm)T,构造Lagrange函数将条件极值问题化作无条件极值问题,使得l1(x,λ)的稳定点为条件极值的可能极值点.而求l1(x,λ)的稳定点问题可转化为求解非线性系统
可以利用算法VSS来求解此问题.如果VSS算法能够成功计算出区间向量(X,A)T,使得F(x,λ)=0的解(x,λ)T∈(X,A)T,则(x,λ)T为函数l1(x,λ)的稳定点.
超定系统f(x)=0局部极小二乘解指的是优化问题的极小值点.通过引入新变量w=(w1,...,wm)T和Lagrange乘子λ=(λ1,...,λm)T,构造Lagrange函数l1(x,w,λ)的稳定点求解问题转化为求解非线性系统
如果VSS算法能够成功计算出区间向量(X,W)T,使得F(x,w)=0的解(x,w)T∈(X,W)T,则(x,w,2w)为函数l1(χ,ω,λ)的稳定点.
基于上述理论方法,本章最后给出了算法VSU与算法VSO,分别输出区间,使得在该区间内必定存在l1的一个精确稳定点.
第四章研究了半实验点集的近似消逝理想边界基算法.在工业生产中,经常遇到这样的数据：一部分数据由观测所得,这些数据不可避免存在误差,称其为实验点；另一部分数据是通过多年生产实验所得,这些数据精确性较高,称其为精确点;由精确点与实验点组成的点集,称为半实验点集.由实验点集构成的近似消逝理想记作I,由精确点集构成的消逝理想记作J.为了使所得理想基中多项式次数尽可能低,没有必要要求所得的理想基在实验点集上严格取零值,对给定的精度,只要其在实验点上近似为零即可.本章我们给出了一种计算半实验点集的近似消逝理想I∩J的边界基算法SSOI.该算法输出I∩J的一组边界基,满足在实验点处近似消逝,在精确点处严格消逝,同时输出多项式环模I∩J的商环基.此外还给出了计算半实验点集近似消逝理想边界基的效率更高的算法SNBM,但是该算法仅输出一组在实验点处近似消逝,在精确点处严格消逝的边界基.
It is a challenge problem to verify the singular solution of nonlinear sys-tems. And reliable computing is widely applied across the high risk areas suchas rocket design, nuclear magnetic resonance (NMR) machine and digital ma-chine theory. In1983, Rump introduced the verification method which canbe used to compute verified error bounds for simple solutions of a nonlinearsystem. Since arbitrary small perturbations of coefcients may transform asingular solution into a cluster of simple roots, hence reliable computing thesingular solution of a nonlinear system is a singular problem. Therefore thecertification has the theoretical importance and practical value. Based on stan-dard verification methods for nonsingular solutions of nonlinear systems, westudy the reliable computing of singular solutions with the help of the intervalalgorithm and deflation techniques.
In the second chapter, we consider the problem of computing verified errorbounds for singular solutions of a nonlinear system. Let f:Rn→Rmwithf=(fT1, f2,..., fm), then a point x is called an isolated solution of f(x)=0if there is a neighborhood of x such that x is the only solution of f(x)=0in this neighborhood. Let Jf(x) denote the Jacobian matrix of f(x) at x. Asolution x of f(x)=0is a singular solution if rank(Jf(x)) Based on a depth-deflation method, we construct the border system f1(x, y1) =0by adding m r smoothing parameters and n r equations to f(x)=0,where r is the rank of the Jacobian matrix at the solution x. And (x,0) is thesolution of f1(x, y1)=0. If Jf1(x,0)=m+n r, then we can use the verifi-cation method to compute verified error bounds such that a system f(x)=0has a singular root within the computed bounds. Otherwise, we construct theborder system fk(x, y1,..., yk)=0by adding q smoothing parameters and qequations to fk1(x, y1,..., yk1)=0where q is the corank of the Jacobianmatrix Jfk1(x, y1,..., yk1). Let (x,0)Tbe an isolated singular solution off1(x, λ1)=0with depth δf1(x,0). Suppose that rank(Jfk(x,0,...,0))=rkfor each k, then there is an integer σ≤δf1(x,0) such that the deflation pro-cess terminates at the border system fσ(x, λ1,..., λσ)=0with a simple zero(x,0,...,0)T. Finally we can use the verification method to compute verifiederror bounds such that a system f(x)=0is proved to have a singular rootwithin the computed bounds.
Based on the above method, we propose a reliable computing algorithmwhich is called VSS. This algorithm computes verified error bounds of a non-linear system for singular solutions in terms of the approximation left and rightnullspace of the Jacobian matrix. Our algorithm is not only applicable to theisolated singular solution, but also to the non-isolated solution. Note that thenon-isolated solution has the property that the rank of the Jacobian matrix atthe solution is not equal to the rank of the Jacobian matrix of any point in aneighborhood of this solution. Moreover, this algorithm can verify the singularsolution of both overdetermined systems and underdetermined systems. Nu-merical experiments show the performance of our algorithm. Finally we givethe complexity of computing the Jacobian matrix.
In the third chapter, we introduc the verification method for certifying theminimum2-norm solution of the underdetermined system and the minimum2-norm solution of the overdetermined system. Assume that f:Rn→Rmwithf=(f1,..., fm)T, n> m, and f1,..., fmhave all second partial derivatives.The minimum2-norm solution of the underdetermined system f(x)=0is defined by the solution of the following constrained optimization problem min||x||22subject to f(x)=0. Construct Lagrange function with Lagrange multipliers λ=(λ1,..., λm)T. If x is the minimal point of the constrained optimization problem min||x||22, then there exists λ∈Rm such that (x,λ)T is a stationary point for the Lagrange function l1(x,λ). The system F(x,λ) is defined by with λ=(λ1,...,λm)T. If Algorithm VSS is applicable to F(x, λ)=0and yields inclusions for x∈Rn,λ∈Rm such that F(x, λ)=0, then (x,λ) is the stationary point of the Lagrange function l1(x,λ), and Jf(x) is full row rank.
The minimum2-norm solution of the overdetermined system f(x)0(n Based on the above method, we propose the reliable computing algorithmVSU and VSO which compute verified error bounds for the minimum2-normsolution of the underdetermined system and the minimum2-norm solution ofthe overdetermined system, respectively. And these error bounds have theproperty that exact solutions exist within these computed bounds.
In the fourth chapter, we study the border bases for ideals of semi-empirical points. A point set consisting of exact points and empirical pointsis called a semi-empirical point set. The coordinates of the empirical pointsis given with limited precision, typically up to a permitted tolerance ε. Wepresent an algorithm SSOI which computes stable border bases for the idealI∩J, where I is the approximately vanishing ideal of an empirical point set,and J is the vanishing ideal of an exact point set. And these border basesvanish ε-approximately at the empirical points and vanish exactly at the exactpoints. Moreover we give an algorithm called SNBM which outputs polyno-mials vanishing ε-approximately at the empirical points and vanishing exactlyat the exact points.
非线性系统解的可信验证是应用广泛的一类问题.在火箭喷口受力分析,核磁共振机设计,数码机床控制等高风险应用领域中,很多问题最终都可以归结为非线性系统解的可信验证问题Rump于1983年给出了一种可信验证方法,解决了非线性系统单根存在性的验证问题.然而奇异解存在性的验证是一个病态问题,因为对非线性系统的系数作任意微小扰动,都可能导致一个孤立奇异解变成一族单根.因此研究奇异解存在性的验证具有重要的理论意义和应用价值.本文基于Rump的可信验证方法,研究了非线性系统奇异解的可信验证问题,得到了一系列结果,具体按章次介绍如下.
第二章研究了非线性系统f(x)=0的孤立奇异解和和一类非孤立奇异解的可信性验证方法,其中f:Rn→Rm,f=(f1,f2…,fm)T,f1,…,fm为解析函数.假设x为f(x)=0的解,如果存在包含x的某邻域,使得x为此邻域内的唯一解,则称x为孤立解;如果对任意包含x的邻域,都存在异于岔的其它解,则称岔为非孤立解；如果f的雅可比矩阵在岔处非满秩,则称x为奇异解.我们研究的一类非孤立奇异解x指的是f的雅可比矩阵在非孤立奇异解x处的秩小于在x邻域内其它任意点处的秩.
本章利用压缩技术,给出了一种正则化方法.利用f(x)=0,通过添加m-r个变量,n-r个方程,构造边界系统f1(x,y1)=0,使得(x,0)为f1(x,y1)=0的解,其中r为f的雅可比矩阵Jf(x)在f(x)=0的奇异解x处的秩.由f构造f1的过程称之为压缩.如果f1：Rm+n-r→Rm+n-r的雅可比矩阵Jf1(x)在解(x,0)处满秩,则可利用Rump的验证方法验证压缩系统f1(x,y1)=0的解的存在性与唯一性,从而可验证系统f(x)=0的奇异解或非孤立奇异解的存在性与唯一性.否则对f1(x,y1)=0按照上述方法继续压缩,构造新的边界系统.继续下去,如果Jk-1在其解处的秩亏度为q,则再添加q个变量,q个方程,得到新的系统fk(x,y1,...,yk)=0,使得(x,0,...,0)为其解.可以证明存在正整数σ,使得压缩σ次后,得到的Jfσ(x,y1,...,yσ)在其解处满秩.从而可以用Rump的可信验证方法验证其解,进而可验证系统f(x)=0的奇异解或非孤立奇异解的存在性与唯一性.
由于每一步都需计算雅可比阵,最后我们给出了计算雅可比矩阵的复杂度分析.
基于上述方法,本章提出了可信验证算法VSS,该算法输出原系统的解的一个区间,使得该区间内必定存在原系统的一个精确解.与其它正则化方法相比,我们的方法添加的方程个数较少,计算效率较高;不仅能验证孤立奇异解,而且也能验证雅可比矩阵在解处的秩小于在解邻域内除解之外任意点处的秩的非孤立奇异解；还可用来处理超定系统(n
第三章介绍了欠定系统局部极小二范数解和超定系统局部极小二乘解的可信验证方法.设f：Rn→Rm,f=(f1,...,fm)T,f1,...fm在包含x的开集Ω内充分光滑.欠定系统f(x)=0(n>m)局部极小二范数解指的是约束优化问题的极小值点.通过引入Lagrange乘子λ=(λ1,...λm)T,构造Lagrange函数将条件极值问题化作无条件极值问题,使得l1(x,λ)的稳定点为条件极值的可能极值点.而求l1(x,λ)的稳定点问题可转化为求解非线性系统
可以利用算法VSS来求解此问题.如果VSS算法能够成功计算出区间向量(X,A)T,使得F(x,λ)=0的解(x,λ)T∈(X,A)T,则(x,λ)T为函数l1(x,λ)的稳定点.
超定系统f(x)=0局部极小二乘解指的是优化问题的极小值点.通过引入新变量w=(w1,...,wm)T和Lagrange乘子λ=(λ1,...,λm)T,构造Lagrange函数l1(x,w,λ)的稳定点求解问题转化为求解非线性系统
如果VSS算法能够成功计算出区间向量(X,W)T,使得F(x,w)=0的解(x,w)T∈(X,W)T,则(x,w,2w)为函数l1(χ,ω,λ)的稳定点.
基于上述理论方法,本章最后给出了算法VSU与算法VSO,分别输出区间,使得在该区间内必定存在l1的一个精确稳定点.
第四章研究了半实验点集的近似消逝理想边界基算法.在工业生产中,经常遇到这样的数据：一部分数据由观测所得,这些数据不可避免存在误差,称其为实验点；另一部分数据是通过多年生产实验所得,这些数据精确性较高,称其为精确点;由精确点与实验点组成的点集,称为半实验点集.由实验点集构成的近似消逝理想记作I,由精确点集构成的消逝理想记作J.为了使所得理想基中多项式次数尽可能低,没有必要要求所得的理想基在实验点集上严格取零值,对给定的精度,只要其在实验点上近似为零即可.本章我们给出了一种计算半实验点集的近似消逝理想I∩J的边界基算法SSOI.该算法输出I∩J的一组边界基,满足在实验点处近似消逝,在精确点处严格消逝,同时输出多项式环模I∩J的商环基.此外还给出了计算半实验点集近似消逝理想边界基的效率更高的算法SNBM,但是该算法仅输出一组在实验点处近似消逝,在精确点处严格消逝的边界基.
It is a challenge problem to verify the singular solution of nonlinear sys-tems. And reliable computing is widely applied across the high risk areas suchas rocket design, nuclear magnetic resonance (NMR) machine and digital ma-chine theory. In1983, Rump introduced the verification method which canbe used to compute verified error bounds for simple solutions of a nonlinearsystem. Since arbitrary small perturbations of coefcients may transform asingular solution into a cluster of simple roots, hence reliable computing thesingular solution of a nonlinear system is a singular problem. Therefore thecertification has the theoretical importance and practical value. Based on stan-dard verification methods for nonsingular solutions of nonlinear systems, westudy the reliable computing of singular solutions with the help of the intervalalgorithm and deflation techniques.
In the second chapter, we consider the problem of computing verified errorbounds for singular solutions of a nonlinear system. Let f:Rn→Rmwithf=(fT1, f2,..., fm), then a point x is called an isolated solution of f(x)=0if there is a neighborhood of x such that x is the only solution of f(x)=0in this neighborhood. Let Jf(x) denote the Jacobian matrix of f(x) at x. Asolution x of f(x)=0is a singular solution if rank(Jf(x))
Based on the above method, we propose a reliable computing algorithmwhich is called VSS. This algorithm computes verified error bounds of a non-linear system for singular solutions in terms of the approximation left and rightnullspace of the Jacobian matrix. Our algorithm is not only applicable to theisolated singular solution, but also to the non-isolated solution. Note that thenon-isolated solution has the property that the rank of the Jacobian matrix atthe solution is not equal to the rank of the Jacobian matrix of any point in aneighborhood of this solution. Moreover, this algorithm can verify the singularsolution of both overdetermined systems and underdetermined systems. Nu-merical experiments show the performance of our algorithm. Finally we givethe complexity of computing the Jacobian matrix.
In the third chapter, we introduc the verification method for certifying theminimum2-norm solution of the underdetermined system and the minimum2-norm solution of the overdetermined system. Assume that f:Rn→Rmwithf=(f1,..., fm)T, n> m, and f1,..., fmhave all second partial derivatives.The minimum2-norm solution of the underdetermined system f(x)=0is defined by the solution of the following constrained optimization problem min||x||22subject to f(x)=0. Construct Lagrange function with Lagrange multipliers λ=(λ1,..., λm)T. If x is the minimal point of the constrained optimization problem min||x||22, then there exists λ∈Rm such that (x,λ)T is a stationary point for the Lagrange function l1(x,λ). The system F(x,λ) is defined by with λ=(λ1,...,λm)T. If Algorithm VSS is applicable to F(x, λ)=0and yields inclusions for x∈Rn,λ∈Rm such that F(x, λ)=0, then (x,λ) is the stationary point of the Lagrange function l1(x,λ), and Jf(x) is full row rank.
The minimum2-norm solution of the overdetermined system f(x)0(n
In the fourth chapter, we study the border bases for ideals of semi-empirical points. A point set consisting of exact points and empirical pointsis called a semi-empirical point set. The coordinates of the empirical pointsis given with limited precision, typically up to a permitted tolerance ε. Wepresent an algorithm SSOI which computes stable border bases for the idealI∩J, where I is the approximately vanishing ideal of an empirical point set,and J is the vanishing ideal of an exact point set. And these border basesvanish ε-approximately at the empirical points and vanish exactly at the exactpoints. Moreover we give an algorithm called SNBM which outputs polyno-mials vanishing ε-approximately at the empirical points and vanishing exactlyat the exact points.
引文
[1] HADMARD J. Sur les problYmes aux dWrivWes partielles et leur significationphysique[J]. Princeton university bulletin,1902,28(13):49-52.
[2] YOUNG R C. The algebra of many-valued quantities[J]. Mathematische An-nalen,1931,104(1):260-290.
[3] DWYER P S. Linear computations[M]. New York: John Wiley and Sons,1951.
[4] WARMUS M. Calculus of approximations[J]. Bulletin de l’Academie Polonaisede Sciences,1956,4(5):253-257.
[5] SUNAGA T. Geometry of numerals[D]. Tokyo: University of Tokyo,1956.
[6] MOORE R E. Interval arithmetic and automatic error analysis in digital com-puting[D]. Stanford: University of Stanford,1962.
[7] HANSEN E, SMITH R. Interval arithmetic in matrix computations II[J].SIAM Journal on Numerical Analysis,1967,4(1):1-9.
[8] KRAWCZYK R. Newton-algorithmen zur bestimmung von nullstellen mitfehlerschranken[J]. Computing,1969,4(3):187-201.
[9] ALEFELD G, HERZBERGER J. Einfu¨hrung in die Intervallrechnung[M].Leipzig: Bibliogr. Inst.,1974.
[10] MOORE R E. A test for existence of solutions to nonlinear systems[J]. SIAMJournal on Numerical Analysis,1977,14(4):611-615.
[11] RUMP S M. Kleine Fehlerschranken bei Matrixproblemen[D]. Karlsruhe: Uni-versitat Karlsruhe,1980.
[12] RUMP S M. INTLAB)interval laboratory//Developments in Reliable Com-puting[M]. Dordrecht: Kluwer Academic Publishers,1999,77-104.
[13] MOORE R E. A computational test for convergence of iterative methods fornonlinear systems[J]. SIAM J. Numer. Anal.,1978,15(6):1194-1196.
[14] RUMP S M. Solving algebraic problems with high accuracy[C]. Proceedingsof the Symposium on a new Approach to Scientific Computation. AcademicPress,1983:51-120.
[15] KEARFOTT R B, DAWANDE M, DU K, et al. Algorithm737: Intlib)aportable fortran77interval standard-function library[J]. ACM Transactionson Mathematical Software,1994,20(4):447-459.
[16] BLEHER J H, ROEDER A E, RUMP S M. ACRITH: High-Accuracy Arith-metic an advanced tool for numerical computation[C]. Urbana: ComputerArithmetic (ARITH), IEEE7th Symposium,1985:318-321.
[17] DENNIS JR J E, SCHNABEL R B. Numerical methods for unconstrainedoptimization and nonlinear equations[M]. Philadelphia: SIAM,1996.
[18] KELLEY C T. Iterative methods for linear and nonlinear equations[M].Philadelphia: SIAM,1995.
[19] ORTEGA J M, RHEINBOLDT W C. Iterative solution of nonlinear equationsin several variables[M]. New York: Academic Press,1970.
[20] YPMA T J. Local convergence of inexact Newton methods[J]. SIAM J. Numer.Anal.,1984,21(3):583-590.
[21] YPMA T J. Historical development of the Newton Raphson method[J].SIAM Rev.,1995,37(4):531-551.
[22] RALL L B. Convergence of the Newton process to multiple solutions[J]. Nu-merische Mathematik,1966,9(1):23-37.
[23] DECKER D W, KELLEY C T. Newton’s method at singular points. I[J].SIAM Journal on Numerical Analysis,1980,17(1):66-70.
[24] DECKER D W, KELLEY C T. Newton’s method at singular points. II[J].SIAM Journal on Numerical Analysis,1980,17(3):465-471.
[25] DECKER D W, KELLEY C T. Convergence acceleration for Newton’smethod at singular points[J]. SIAM Journal on Numerical Analysis,1982,19(1):219-229.
[26] REDDIEN G W. On Newton’s method for singular problems[J]. SIAM Journalon Numerical Analysis,1978,15(5):993-996.
[27] GRIEWANK A O. Analysis and modification of Newton’s method at singu-larities[D]. Canberra: Australian National University,1980.
[28] GRIEWANK A, OSBORNE M R. Newton’s method for singular problemswhen the dimension of the null space is>1[J]. SIAM Journal on NumericalAnalysis,1981,18(1):145-149.
[29] GRIEWANK A. On solving nonlinear equations with simple singularities ornearly singular solutions[J]. SIAM review,1985,27(4):537-563.
[30] SHEN Y Q, YPMA T J. Newton’s method for singular nonlinear equationsusing approximate left and right nullspaces of the Jacobian[J]. Applied nu-merical mathematics,2005,54(2):256-265.
[31] OJIKA T, WATANABE S, MITSUI T. Deflation algorithm for the multipleroots of a system of nonlinear equations[J]. Journal of mathematical analysisand applications,1983,96(2):463-479.
[32] OJIKA T. Modified deflation algorithm for the solution of singular problems. I.A system of nonlinear algebraic equations[J]. Journal of mathematical analysisand applications,1987,123(1):199-221.
[33] YAMAMOTO N. Regularization of solutions of nonlinear equations with sin-gular Jacobian matrices[J]. Journal of information processing,1984,7(1):16-21.
[34] LEYKIN A, VERSCHELDE J, ZHAO A. Newton’s method with deflation forisolated singularities of polynomial systems[J]. Theoretical Computer Science,2006,359(1):111-122.
[35] LEYKIN A, VERSCHELDE J, ZHAO A. Higher-order deflation for polyno-mial systems with isolated singular solutions//Algorithms in algebraic geom-etry[M]. New York: Springer,2008,79-97.
[36] DAYTON B, LI T Y, ZENG Z. Multiple zeros of nonlinear systems[J]. Math-ematics of Computation,2011,80(276):2143-2168.
[37]o.‘aXú á é ê°zú&y[D].:￥I‰,2013.
[38] DAYTON B H, ZENG Z. Computing the multiplicity structure in solvingpolynomial systems[C]. Proceedings of the2005international symposium onSymbolic and algebraic computation. ACM,2005:116-123.
[39] LI N, ZHI L. Computing isolated singular solutions of polynomial systems:case of breadth one[J]. SIAM Journal on Numerical Analysis,2012,50(1):354-372.
[40] LI N, ZHI L. Computing the multiplicity structure of an isolated singularsolution: Case of breadth one[J]. Journal of Symbolic Computation,2012,47(6):700-710.
[41] RUMP S M. Verification methods: Rigorous results using floating-point arith-metic[J]. Acta Numerica,2010,19:287-449.
[42] SMALE S. The fundamental theorem of algebra and complexity theory[J].Bulletin of the American Mathematical Society,1981,4(1):1-36.
[43] SHUB M, SMALE S. Computational complexity: on the geometry of poly-nomials and a theory of cost. I[C]. Annales scientifiques de l’Ecole normalesupWrieure. Elsevier,1985,18(1):107-142.
[44] SHUB M, SMALE S. Computational complexity: on the geometry of polyno-mials and a theory of cost: II[J]. SIAM Journal on Computing,1986,15(1):145-161.
[45] GIUSTI M, LECERF G, SALVY B, et al. On location and approximationof clusters of zeros of analytic functions[J]. Foundations of ComputationalMathematics,2005,5(3):257-311.
[46] GIUSTI M, LECERF G, SALVY B, et al. On location and approximation ofclusters of zeros: Case of embedding dimension one[J]. Foundations of Com-putational Mathematics,2007,7(1):1-58.
[47] MOORE R E. Interval analysis[M]. Englewood Clifs: Prentice-Hall,1966.
[48] RUMP S M, GRAILLAT S. Verified error bounds for multiple roots of systemsof nonlinear equations[J]. Numerical Algorithms,2010,54(3):359-377.
[49] LI N, ZHI L. Verified error bounds for isolated singular solutions of polynomialsystems: case of breadth one[J]. Theoretical Computer Science,2013,479:163-173.
[50] LI N, ZHI L. Verified error bounds for isolated singular solutions of polynomialsystems[J].2012, Preprint, arxiv.org/pdf/1212.4699.
[51] MANTZAFLARIS A, MOURRAIN B. Deflation and certified isolation of sin-gular zeros of polynomial systems[C]. Proceedings of the36th internationalsymposium on Symbolic and algebraic computation. ACM,2011:249-256.
[52] YANG Z, ZHI L, ZHU Y. Verified error bounds for real solutions of positive-dimensional polynomial systems[C]. Proceedings of the38th internationalsymposium on International symposium on symbolic and algebraic compu-tation. ACM,2013:371-378.
[53] CHEN X, WOMERSLEY R S. Existence of solutions to systems of under-determined equations and spherical designs[J]. SIAM Journal on NumericalAnalysis,2006,44(6):2326-2341.
[54] CHEN X, FROMMER A, LANG B. Computational existence proofs for spher-ical t-designs[J]. Numerische Mathematik,2011,117(2):289-305.
[55]RUMP S M. Verified bounds for least squares problems and underdetermined linear systems [J]. SIAM Journal on Matrix Analysis and Applications,2012,33(1):130-148.
[56]MOORE R E, KEARFOTT R B, CLOUD M J. Introduction to interval anal-ysis[M]. Siam,2009.
[57]王德人,张连生,邓乃扬.非线性方程的区间算法[M].上海：上海科学技术出版社,1987.
[58]MOORE R E, JONES S T. Safe starting regions for iterative methods[J]. SIAM Journal on Numerical Analysis,1977,14(6):1051-1065.
[59]JONES S T. Locating safe starting regions for iterative methods:a heuristic algorithmp[M]. Academic Press, New York,1980.
[60]张树功,雷娜,刘停战.计算机代数基础[M].北京：科学出版社,2005.
[61]COX D, LITTLE J, O'SHEA D. Ideals, varieties, and algorithms[M].3rd ed. New York:Springer,2007.
[62]COX D, LITTLE J, O'SHEA D. Using algebraic geometry[M]. New York: Springer,1998.
[63]BECKER T, WEISPFENNING V. Grobner bases[M]. New York:Springer,1993.
[64]KUNZ E. Introduction to commutative algebra and algebraic geometry[M]. Berlin:Springer,2012.
[65]KREUZER M, ROBBIANO L. Computational commutative algebra[M]. Berlin:Springer,2005.
[66]GOLUB G H, VAN LOAN C F. Matrix computations[M]. Johns Hopkins University Press,2012.
[67]STEWART G W. Introduction to matrix computations[M]. New York:Aca-demic press,1973.
[68] GRIEWANK A, REDDIEN G W. The approximation of generalized turningpoints by projection methods with superconvergence to the critical parame-ter[J]. Numerische Mathematik,1986,48(5):591-606.
[69] GRIEWANK A, REDDIEN G W. The approximate solution of defining equa-tions for generalized turning points[J]. SIAM journal on numerical analysis,1996,33(5):1912-1920.
[70] SPENCE A, POULTON C. Photonic band structure calculations using nonlin-ear eigenvalue techniques[J]. Journal of Computational Physics,2005,204(1):65-81.
[71] STURMFELS B. Solving systems of polynomial equations[M]. AmericanMathematical Soc.,2002.
[72] MORITSUGU S, KURIYAMA K. On multiple zeros of systems of algebraicequations[C]. Proceedings of the1999international symposium on Symbolicand algebraic computation. ACM,1999:23-30.
[73] BJO¨RCK G, FRO¨BERG R. A faster way to count the solutions of inhomo-geneous systems of algebraic equations, with applications to cyclic n-roots[J].Journal of Symbolic Computation,1991,12(3):329-336.
[74] OJIKA T. A numerical method for branch points of a system of nonlinearalgebraic equations[J]. Applied numerical mathematics,1988,4(5):419-430.
[75] KOBAYASHI H, SUZUKI H, SAKAI Y. Numerical calculation of the multi-plicity of a solution to algebraic equations[J]. Mathematics of Computation ofthe American Mathematical Society,1998,67(221):257-270.
[76]êL2,p#.ê [M].:p,2005.
[77] SAUER T. Approximate varieties, approximate ideals and dimension reduc-tion[J]. Numerical Algorithms,2007,45(1-4):295-313.
[78] HELDT D, KREUZER M, POKUTTA S, et al. Approximate computationof zero-dimensional polynomial ideals[J]. Journal of Symbolic Computation,2009,44(11):1566-1591.
[79] ABBOTT J, FASSINO C, TORRENTE M L. Stable border bases for idealsof points[J]. Journal of Symbolic Computation,2008,43(12):883-894.
[80] FASSINO C. Almost vanishing polynomials for sets of limited precisionpoints[J]. Journal of symbolic computation,2010,45(1):19-37.
[81] KREUZER M, POULISSE H. Subideal border bases[J]. Mathematics of Com-putation,2011,80(274):1135-1154.
[82] The algebraic oil research project, see http://www.fim.uni-passau.de/alge-braic-oil.
[83] KREUZER M, POULISSE H, ROBBIANO L. From oil fields to Hilbertschemes//Approximate Commutative Algebra[M]. Springer Vienna,2010:1-54.
[84] STETTER H J. Numerical polynomial algebra[M]. Philadelphia: SIAM,2004.
[85] MO¨LLER H M, BUCHBERGER B. The construction of multivariate polyno-mials with preassigned zeros//Computer algebra[M]. Springer Berlin Heidel-berg,1982:24-31.
[86] ABBOTT J, BIGATTI A, KREUZER M, et al. Computing ideals of points[J].Journal of Symbolic Computation,2000,30(4):341-356.
[2] YOUNG R C. The algebra of many-valued quantities[J]. Mathematische An-nalen,1931,104(1):260-290.
[3] DWYER P S. Linear computations[M]. New York: John Wiley and Sons,1951.
[4] WARMUS M. Calculus of approximations[J]. Bulletin de l’Academie Polonaisede Sciences,1956,4(5):253-257.
[5] SUNAGA T. Geometry of numerals[D]. Tokyo: University of Tokyo,1956.
[6] MOORE R E. Interval arithmetic and automatic error analysis in digital com-puting[D]. Stanford: University of Stanford,1962.
[7] HANSEN E, SMITH R. Interval arithmetic in matrix computations II[J].SIAM Journal on Numerical Analysis,1967,4(1):1-9.
[8] KRAWCZYK R. Newton-algorithmen zur bestimmung von nullstellen mitfehlerschranken[J]. Computing,1969,4(3):187-201.
[9] ALEFELD G, HERZBERGER J. Einfu¨hrung in die Intervallrechnung[M].Leipzig: Bibliogr. Inst.,1974.
[10] MOORE R E. A test for existence of solutions to nonlinear systems[J]. SIAMJournal on Numerical Analysis,1977,14(4):611-615.
[11] RUMP S M. Kleine Fehlerschranken bei Matrixproblemen[D]. Karlsruhe: Uni-versitat Karlsruhe,1980.
[12] RUMP S M. INTLAB)interval laboratory//Developments in Reliable Com-puting[M]. Dordrecht: Kluwer Academic Publishers,1999,77-104.
[13] MOORE R E. A computational test for convergence of iterative methods fornonlinear systems[J]. SIAM J. Numer. Anal.,1978,15(6):1194-1196.
[14] RUMP S M. Solving algebraic problems with high accuracy[C]. Proceedingsof the Symposium on a new Approach to Scientific Computation. AcademicPress,1983:51-120.
[15] KEARFOTT R B, DAWANDE M, DU K, et al. Algorithm737: Intlib)aportable fortran77interval standard-function library[J]. ACM Transactionson Mathematical Software,1994,20(4):447-459.
[16] BLEHER J H, ROEDER A E, RUMP S M. ACRITH: High-Accuracy Arith-metic an advanced tool for numerical computation[C]. Urbana: ComputerArithmetic (ARITH), IEEE7th Symposium,1985:318-321.
[17] DENNIS JR J E, SCHNABEL R B. Numerical methods for unconstrainedoptimization and nonlinear equations[M]. Philadelphia: SIAM,1996.
[18] KELLEY C T. Iterative methods for linear and nonlinear equations[M].Philadelphia: SIAM,1995.
[19] ORTEGA J M, RHEINBOLDT W C. Iterative solution of nonlinear equationsin several variables[M]. New York: Academic Press,1970.
[20] YPMA T J. Local convergence of inexact Newton methods[J]. SIAM J. Numer.Anal.,1984,21(3):583-590.
[21] YPMA T J. Historical development of the Newton Raphson method[J].SIAM Rev.,1995,37(4):531-551.
[22] RALL L B. Convergence of the Newton process to multiple solutions[J]. Nu-merische Mathematik,1966,9(1):23-37.
[23] DECKER D W, KELLEY C T. Newton’s method at singular points. I[J].SIAM Journal on Numerical Analysis,1980,17(1):66-70.
[24] DECKER D W, KELLEY C T. Newton’s method at singular points. II[J].SIAM Journal on Numerical Analysis,1980,17(3):465-471.
[25] DECKER D W, KELLEY C T. Convergence acceleration for Newton’smethod at singular points[J]. SIAM Journal on Numerical Analysis,1982,19(1):219-229.
[26] REDDIEN G W. On Newton’s method for singular problems[J]. SIAM Journalon Numerical Analysis,1978,15(5):993-996.
[27] GRIEWANK A O. Analysis and modification of Newton’s method at singu-larities[D]. Canberra: Australian National University,1980.
[28] GRIEWANK A, OSBORNE M R. Newton’s method for singular problemswhen the dimension of the null space is>1[J]. SIAM Journal on NumericalAnalysis,1981,18(1):145-149.
[29] GRIEWANK A. On solving nonlinear equations with simple singularities ornearly singular solutions[J]. SIAM review,1985,27(4):537-563.
[30] SHEN Y Q, YPMA T J. Newton’s method for singular nonlinear equationsusing approximate left and right nullspaces of the Jacobian[J]. Applied nu-merical mathematics,2005,54(2):256-265.
[31] OJIKA T, WATANABE S, MITSUI T. Deflation algorithm for the multipleroots of a system of nonlinear equations[J]. Journal of mathematical analysisand applications,1983,96(2):463-479.
[32] OJIKA T. Modified deflation algorithm for the solution of singular problems. I.A system of nonlinear algebraic equations[J]. Journal of mathematical analysisand applications,1987,123(1):199-221.
[33] YAMAMOTO N. Regularization of solutions of nonlinear equations with sin-gular Jacobian matrices[J]. Journal of information processing,1984,7(1):16-21.
[34] LEYKIN A, VERSCHELDE J, ZHAO A. Newton’s method with deflation forisolated singularities of polynomial systems[J]. Theoretical Computer Science,2006,359(1):111-122.
[35] LEYKIN A, VERSCHELDE J, ZHAO A. Higher-order deflation for polyno-mial systems with isolated singular solutions//Algorithms in algebraic geom-etry[M]. New York: Springer,2008,79-97.
[36] DAYTON B, LI T Y, ZENG Z. Multiple zeros of nonlinear systems[J]. Math-ematics of Computation,2011,80(276):2143-2168.
[37]o.‘aXú á é ê°zú&y[D].:￥I‰,2013.
[38] DAYTON B H, ZENG Z. Computing the multiplicity structure in solvingpolynomial systems[C]. Proceedings of the2005international symposium onSymbolic and algebraic computation. ACM,2005:116-123.
[39] LI N, ZHI L. Computing isolated singular solutions of polynomial systems:case of breadth one[J]. SIAM Journal on Numerical Analysis,2012,50(1):354-372.
[40] LI N, ZHI L. Computing the multiplicity structure of an isolated singularsolution: Case of breadth one[J]. Journal of Symbolic Computation,2012,47(6):700-710.
[41] RUMP S M. Verification methods: Rigorous results using floating-point arith-metic[J]. Acta Numerica,2010,19:287-449.
[42] SMALE S. The fundamental theorem of algebra and complexity theory[J].Bulletin of the American Mathematical Society,1981,4(1):1-36.
[43] SHUB M, SMALE S. Computational complexity: on the geometry of poly-nomials and a theory of cost. I[C]. Annales scientifiques de l’Ecole normalesupWrieure. Elsevier,1985,18(1):107-142.
[44] SHUB M, SMALE S. Computational complexity: on the geometry of polyno-mials and a theory of cost: II[J]. SIAM Journal on Computing,1986,15(1):145-161.
[45] GIUSTI M, LECERF G, SALVY B, et al. On location and approximationof clusters of zeros of analytic functions[J]. Foundations of ComputationalMathematics,2005,5(3):257-311.
[46] GIUSTI M, LECERF G, SALVY B, et al. On location and approximation ofclusters of zeros: Case of embedding dimension one[J]. Foundations of Com-putational Mathematics,2007,7(1):1-58.
[47] MOORE R E. Interval analysis[M]. Englewood Clifs: Prentice-Hall,1966.
[48] RUMP S M, GRAILLAT S. Verified error bounds for multiple roots of systemsof nonlinear equations[J]. Numerical Algorithms,2010,54(3):359-377.
[49] LI N, ZHI L. Verified error bounds for isolated singular solutions of polynomialsystems: case of breadth one[J]. Theoretical Computer Science,2013,479:163-173.
[50] LI N, ZHI L. Verified error bounds for isolated singular solutions of polynomialsystems[J].2012, Preprint, arxiv.org/pdf/1212.4699.
[51] MANTZAFLARIS A, MOURRAIN B. Deflation and certified isolation of sin-gular zeros of polynomial systems[C]. Proceedings of the36th internationalsymposium on Symbolic and algebraic computation. ACM,2011:249-256.
[52] YANG Z, ZHI L, ZHU Y. Verified error bounds for real solutions of positive-dimensional polynomial systems[C]. Proceedings of the38th internationalsymposium on International symposium on symbolic and algebraic compu-tation. ACM,2013:371-378.
[53] CHEN X, WOMERSLEY R S. Existence of solutions to systems of under-determined equations and spherical designs[J]. SIAM Journal on NumericalAnalysis,2006,44(6):2326-2341.
[54] CHEN X, FROMMER A, LANG B. Computational existence proofs for spher-ical t-designs[J]. Numerische Mathematik,2011,117(2):289-305.
[55]RUMP S M. Verified bounds for least squares problems and underdetermined linear systems [J]. SIAM Journal on Matrix Analysis and Applications,2012,33(1):130-148.
[56]MOORE R E, KEARFOTT R B, CLOUD M J. Introduction to interval anal-ysis[M]. Siam,2009.
[57]王德人,张连生,邓乃扬.非线性方程的区间算法[M].上海：上海科学技术出版社,1987.
[58]MOORE R E, JONES S T. Safe starting regions for iterative methods[J]. SIAM Journal on Numerical Analysis,1977,14(6):1051-1065.
[59]JONES S T. Locating safe starting regions for iterative methods:a heuristic algorithmp[M]. Academic Press, New York,1980.
[60]张树功,雷娜,刘停战.计算机代数基础[M].北京：科学出版社,2005.
[61]COX D, LITTLE J, O'SHEA D. Ideals, varieties, and algorithms[M].3rd ed. New York:Springer,2007.
[62]COX D, LITTLE J, O'SHEA D. Using algebraic geometry[M]. New York: Springer,1998.
[63]BECKER T, WEISPFENNING V. Grobner bases[M]. New York:Springer,1993.
[64]KUNZ E. Introduction to commutative algebra and algebraic geometry[M]. Berlin:Springer,2012.
[65]KREUZER M, ROBBIANO L. Computational commutative algebra[M]. Berlin:Springer,2005.
[66]GOLUB G H, VAN LOAN C F. Matrix computations[M]. Johns Hopkins University Press,2012.
[67]STEWART G W. Introduction to matrix computations[M]. New York:Aca-demic press,1973.
[68] GRIEWANK A, REDDIEN G W. The approximation of generalized turningpoints by projection methods with superconvergence to the critical parame-ter[J]. Numerische Mathematik,1986,48(5):591-606.
[69] GRIEWANK A, REDDIEN G W. The approximate solution of defining equa-tions for generalized turning points[J]. SIAM journal on numerical analysis,1996,33(5):1912-1920.
[70] SPENCE A, POULTON C. Photonic band structure calculations using nonlin-ear eigenvalue techniques[J]. Journal of Computational Physics,2005,204(1):65-81.
[71] STURMFELS B. Solving systems of polynomial equations[M]. AmericanMathematical Soc.,2002.
[72] MORITSUGU S, KURIYAMA K. On multiple zeros of systems of algebraicequations[C]. Proceedings of the1999international symposium on Symbolicand algebraic computation. ACM,1999:23-30.
[73] BJO¨RCK G, FRO¨BERG R. A faster way to count the solutions of inhomo-geneous systems of algebraic equations, with applications to cyclic n-roots[J].Journal of Symbolic Computation,1991,12(3):329-336.
[74] OJIKA T. A numerical method for branch points of a system of nonlinearalgebraic equations[J]. Applied numerical mathematics,1988,4(5):419-430.
[75] KOBAYASHI H, SUZUKI H, SAKAI Y. Numerical calculation of the multi-plicity of a solution to algebraic equations[J]. Mathematics of Computation ofthe American Mathematical Society,1998,67(221):257-270.
[76]êL2,p#.ê [M].:p,2005.
[77] SAUER T. Approximate varieties, approximate ideals and dimension reduc-tion[J]. Numerical Algorithms,2007,45(1-4):295-313.
[78] HELDT D, KREUZER M, POKUTTA S, et al. Approximate computationof zero-dimensional polynomial ideals[J]. Journal of Symbolic Computation,2009,44(11):1566-1591.
[79] ABBOTT J, FASSINO C, TORRENTE M L. Stable border bases for idealsof points[J]. Journal of Symbolic Computation,2008,43(12):883-894.
[80] FASSINO C. Almost vanishing polynomials for sets of limited precisionpoints[J]. Journal of symbolic computation,2010,45(1):19-37.
[81] KREUZER M, POULISSE H. Subideal border bases[J]. Mathematics of Com-putation,2011,80(274):1135-1154.
[82] The algebraic oil research project, see http://www.fim.uni-passau.de/alge-braic-oil.
[83] KREUZER M, POULISSE H, ROBBIANO L. From oil fields to Hilbertschemes//Approximate Commutative Algebra[M]. Springer Vienna,2010:1-54.
[84] STETTER H J. Numerical polynomial algebra[M]. Philadelphia: SIAM,2004.
[85] MO¨LLER H M, BUCHBERGER B. The construction of multivariate polyno-mials with preassigned zeros//Computer algebra[M]. Springer Berlin Heidel-berg,1982:24-31.
[86] ABBOTT J, BIGATTI A, KREUZER M, et al. Computing ideals of points[J].Journal of Symbolic Computation,2000,30(4):341-356.