Verified error bounds for isolated singular solutions of polynomial systems
algorithmdeflationerror boundsisolated singular solutionsmultiplicity structureNewton methodpolynomial systemsquadratic convergenceverification
Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Polynomials and rational functions of one complex variable (30C10) General theory of numerical methods in complex analysis (potential theory, etc.) (65E05) Algorithms with automatic result verification (65G20) Numerical computation of roots of polynomial equations (65H04) Numerical computation of solutions to systems of equations (65H10) Symbolic computation and algebraic computation (68W30)
The article deals with the numerical approximation of isolated singular solutions of polynomial systems over the complex numbers.NEWLINENEWLINELet \(f_1,\dots,f_n\) be polynomials of \(\mathbb{C}[\mathbf{x}]:=\mathbb{C}[x_1,\dots,x_n]\), let \(F:=\{f_1,\dots,f_n\}\) and consider the system \(F(\mathbf{x})=\mathbf{0}\). Usually, isolated nonsingular solutions to the system \(F(\mathbf{x})=\mathbf{0}\) are approximated by means of the Newton method. On the other hand, there is a number of articles devoted to describe variants of the Newton method which restore quadratic convergence for the approximation of an isolated singular solution \(\hat{\mathbf{x}}\) of the system \(F(\mathbf{x})=\mathbf{0}\) (see, e.g., [\textit{A. Griewank}, SIAM Rev. 27, 537--563 (1985; Zbl 0598.65026)]). Algorithms which use certain regularized Newton iterations, based on the computation of differentials at a given approximation of an isolated singular solution, allow one to approximate the solution under consideration to the full machine precision (see, e.g., [\textit{B. H. Dayton} et al., Math. Comput. 80, No. 276, 2143--2168 (2011; Zbl 1242.65102)]). The general idea of adding differentials at the given approximation is called a deflation method.NEWLINENEWLINESince isolated singular solutions may be transformed into clusters of regular solutions by means of arbitrarily small perturbations, it is more difficult to verify that a polynomial system has a multiple root. In [Theor. Comput. Sci. 479, 163--173 (2013; Zbl 1291.65161)], the authors developed a verification method which permits to compute guaranteed error bounds for certain isolated singular solutions.NEWLINENEWLINEIn the paper under review, a further deflation method is proposed for the numerical approximation of isolated singular solutions of a system \(F(\mathbf{x})=\mathbf{0}\) as above. This variant is a modification of a method due to \textit{N. Yamamoto} [J. Inf. Process. 7, 16--21 (1984; Zbl 0564.65036)]. The new deflation method returns a regular and square augmented system in a number of steps which is bounded in terms of the local structure of the ideal generated by \(f_1,\dots, f_n\) at the isolated singular solution \(\hat{\mathbf{x}}\) under consideration. Then an algorithm for computing verified error bounds for a given isolated solution is described. If successful, the algorithm produces a ``slightly perturbed polynomial system having an isolated singular solution within the computed bounds.NEWLINENEWLINEThe paper ends by presenting examples which illustrate the performance of the proposed methods to deal with singular solutions of a few polynomial systems previously considered in the literature.
- Newton's method with deflation for isolated singularities of polynomial systems
- On deflation and multiplicity structure
- Singular Zeros of Polynomial Systems
- A new deflation method for verifying the isolated singular zeros of polynomial systems
- scientific article; zbMATH DE number 5245181
- Computing singular solutions to polynomial systems
- Certifying isolated singular points and their multiplicity structure
- Computing isolated singular solutions of polynomial systems: case of breadth one
- Multiplicity hunting and approximating multiple roots of polynomial systems
- Verified error bounds for isolated singular solutions of polynomial systems: case of breadth one
- Computing singular solutions to polynomial systems
- A heuristic method for certifying isolated zeros of polynomial systems
- Efficient computation of dual space and directional multiplicity of an isolated point
- A new deflation method for verifying the isolated singular zeros of polynomial systems
- Locating the closest singularity in a polynomial homotopy
- Numerical approximation of multiple isolated roots of analytical systems
- An improved verification algorithm for nonlinear systems of equations based on Krawczyk operator
- Certifying solutions to overdetermined and singular polynomial systems over \(\mathbb{Q}\)
- Newton's method with deflation for isolated singularities of polynomial systems
- On deflation and multiplicity structure
- Verified inclusions for a nearest matrix of specified rank deficiency via a generalization of Wedin's \(\sin (\theta)\) theorem
- A certified iterative method for isolated singular roots
- Computing isolated singular solutions of polynomial systems: case of breadth one
- Verified error bounds for real solutions of positive-dimensional polynomial systems
- Verified error bounds for isolated singular solutions of polynomial systems: case of breadth one
- On isolation of simple multiple zeros and clusters of zeros of polynomial systems
- Deflation and certified isolation of singular zeros of polynomial systems
- A verified method of singular solutions of overdetermined nonlinear systems
- scientific article; zbMATH DE number 2231504 (Why is no real title available?)
- Verified error bounds for multiple roots of systems of nonlinear equations
- VerifyRealRoots: a Matlab package for computing verified real solutions of polynomials systems of equations and inequalities
- Verified error bounds for singular solutions of nonlinear systems
- Inflation of poorly conditioned zeros of systems of analytic functions
This page was built for publication: Verified error bounds for isolated singular solutions of polynomial systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2927825)
