Existence verification for singular and nonsmooth zeros of real nonlinear systems

Authors:
Jianwei Dian and R. Baker Kearfott

Journal:
Math. Comp. **72** (2003), 757-766

MSC (2000):
Primary 65G20, 65G30, 65G40, 65H10

Published electronically:
March 5, 2002

MathSciNet review:
1954966

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Traditional computational fixed point theorems, such as the Kantorovich theorem (made rigorous with directed roundings), Krawczyk's meth- od, or interval Newton methods use a computer's floating-point hardware computations to mathematically prove existence and uniqueness of a solution to a nonlinear system of equations within a given region of -space. Such computations require the Jacobi matrix of the system to be nonsingular in a neighborhood of a solution. However, in previous work we showed how we could mathematically verify existence of singular solutions in a small region of complex -space containing an approximate real solution. We verified existence of such singular solutions by verifying that the topological degree of a small region is nonzero; a nonzero topological degree implies existence of a solution in the interior of the region. Here, we show that, when the actual topological degree in complex space is odd and the rank defect of the Jacobi matrix is one, the topological degree of a small region containing the singular solution can be verified to be plus or minus one in real space. The algorithm for verification in real space is significantly simpler and more efficient. We demonstrate this efficiency with numerical experiments.

Since our verification procedure uses only values on the surfaces of a bounding box that contains the solution, the method can also be applied to cases where the system is nonsmooth at the solution.

**1.**Götz Alefeld and Jürgen Herzberger,*Introduction to interval computations*, Computer Science and Applied Mathematics, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York, 1983. Translated from the German by Jon Rokne. MR**733988****2.**Paul Alexandroff and Heinz Hopf,*Topologie*, Erster Band. Grundbegriffe der mengentheoretischen Topologie, Topologie der Komplexe, topologische Invarianzsätze und anschliessende Begriffsbildunge n, Verschlingungen im n-dimensionalen euklidischen Raum, stetige Abbildungen vo n Polyedern, Chelsea Publishing Co., New York, 1965 (German). MR**0185557**

P. Alexandroff and H. Hopf,*Topologie. I*, Springer-Verlag, Berlin-New York, 1974. Berichtigter Reprint; Die Grundlehren der mathematischen Wissenschaften, Band 45. MR**0345087****3.**G. F. Corliss,*Globsol entry page*, 1998,`http://www.mscs.mu.edu/``globsol/`.**4.**Jane Cronin,*Fixed points and topological degree in nonlinear analysis*, Mathematical Surveys, No. 11, American Mathematical Society, Providence, R.I., 1964. MR**0164101****5.**K. J. Hunt, D. Sbarbaro, R. Żbikowski, and P. J. Gawthrop,*Neural networks for control systems—a survey*, Automatica J. IFAC**28**(1992), no. 6, 1083–1112. MR**1196775**, 10.1016/0005-1098(92)90053-I**6.**Hartmut Jürgens, Heinz-Otto Peitgen, and Dietmar Saupe,*Topological perturbations in the numerical study of nonlinear eigenvalue and bifurcation problems*, Analysis and computation of fixed points (Proc. Sympos., Math. Res. Center, Univ. Wisconsin, Madison, Wis., 1979) Publ. Math. Res. Center Univ. Wisconsin, vol. 43, Academic Press, New York-London, 1980, pp. 139–181. MR**592632****7.**R. B. Kearfott,*Computing the degree of maps and a generalized method of bisection*, Ph.D. thesis, University of Utah, Department of Mathematics, 1977.**8.**Baker Kearfott,*An efficient degree-computation method for a generalized method of bisection*, Numer. Math.**32**(1979), no. 2, 109–127. MR**529902**, 10.1007/BF01404868**9.**-,*A Fortran 90 environment for research and prototyping of enclosure algorithms for nonlinear equations and global optimization*, ACM Trans. Math. Software**21**(1995), no. 1, 63-78.**10.**R. Baker Kearfott,*Rigorous global search: continuous problems*, Nonconvex Optimization and its Applications, vol. 13, Kluwer Academic Publishers, Dordrecht, 1996. MR**1422659****11.**R. B. Kearfott and J. Dian,*Existence verification for higher-degree singular zeros of complex nonlinear systems*, 2000, Preprint, Department of Mathematics, Univ. of Louisiana at Lafayette, U.L. Box 4-1010, Lafayette, La 70504.**12.**R. B. Kearfott and J. Dian.,*Verifying topological indices for higher-order rank deficiencies*, 2000, Preprint, Department of Mathematics, Univ. of Louisiana at Lafayette, U.L. Box 4-1010, Lafayette, La 70504.**13.**R. Baker Kearfott, Jianwei Dian, and A. Neumaier,*Existence verification for singular zeros of complex nonlinear systems*, SIAM J. Numer. Anal.**38**(2000), no. 2, 360–379. MR**1770053**, 10.1137/S0036142999361074**14.**Arnold Neumaier,*Interval methods for systems of equations*, Encyclopedia of Mathematics and its Applications, vol. 37, Cambridge University Press, Cambridge, 1990. MR**1100928****15.**H. Ratschek and J. Rokne,*New computer methods for global optimization*, Ellis Horwood Series: Mathematics and its Applications, Ellis Horwood Ltd., Chichester; Halsted Press [John Wiley & Sons, Inc.], New York, 1988. MR**968440****16.**J. M. Ortega and W. C. Rheinboldt,*Iterative solution of nonlinear equations in several variables*, Academic Press, New York-London, 1970. MR**0273810****17.**Frank Stenger,*Computing the topological degree of a mapping in 𝑅ⁿ*, Numer. Math.**25**(1975/76), no. 1, 23–38. MR**0394639**

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
65G20,
65G30,
65G40,
65H10

Retrieve articles in all journals with MSC (2000): 65G20, 65G30, 65G40, 65H10

Additional Information

**Jianwei Dian**

Affiliation:
Hewlett-Packard Company, 3000 Waterview Parkway, Richardson, Texas 75080

Email:
jianwei_dian@hp.com

**R. Baker Kearfott**

Affiliation:
Department of Mathematics, University of Louisiana at Lafayette, Box 4-1010, Lafayette, Louisiana 70504-1010

Email:
rbk@louisiana.edu

DOI:
https://doi.org/10.1090/S0025-5718-02-01427-8

Received by editor(s):
May 8, 2001

Published electronically:
March 5, 2002

Additional Notes:
This work was supported in part by National Science Foundation grant DMS-9701540

Article copyright:
© Copyright 2002
American Mathematical Society