Some Studies On Reliable Computing

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))<min{m, n}. 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.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 <m) is defined by the solution of the following optimization problem Construct Lagrange function with Lagrange multipliers λ=(λ1,...,λm)T and new variables ω=(ω1ωm)T. If x is the minimal point of the optimization problem min{||f(x)||22x∈Rn}, then there exists ω∈Rm such that (x,ω,2ω)T is a stationary point for the Lagrange function l1(x,ω, λ). The system F(x,ω) is defined by with w=(w1,..., wTm). If Algorithm VSS is applicable to F (x, w)=0andyields inclusions for x∈Rn, w∈Rmsuch that F (x, w)=0. Then (x, w,2w)is the stationary point of the Lagrange function l1(x, w, λ), and Jf(x) is fullcolumn rank.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.