Existence verification for singular and nonsmooth zeros of real nonlinear systems
Authors:
Jianwei Dian and R. Baker Kearfott
Journal:
Math. Comp. 72 (2003), 757766
MSC (2000):
Primary 65G20, 65G30, 65G40, 65H10
Published electronically:
March 5, 2002
MathSciNet review:
1954966
Fulltext 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 floatingpoint 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 (85d:65001)
 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 ndimensionalen euklidischen Raum, stetige Abbildungen vo n Polyedern,
Chelsea Publishing Co., New York, 1965 (German). MR 0185557
(32 #3023)
P.
Alexandroff and H.
Hopf, Topologie. I, SpringerVerlag, BerlinNew York, 1974.
Berichtigter Reprint; Die Grundlehren der mathematischen Wissenschaften,
Band 45. MR
0345087 (49 #9826)
 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
(29 #1400)
 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
(93i:93002), http://dx.doi.org/10.1016/00051098(92)90053I
 6.
Hartmut
Jürgens, HeinzOtto
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 YorkLondon, 1980,
pp. 139–181. MR 592632
(82e:65063)
 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 degreecomputation method for a generalized
method of bisection, Numer. Math. 32 (1979),
no. 2, 109–127. MR 529902
(80g:65062), http://dx.doi.org/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, 6378.
 10.
R.
Baker Kearfott, Rigorous global search: continuous problems,
Nonconvex Optimization and its Applications, vol. 13, Kluwer Academic
Publishers, Dordrecht, 1996. MR 1422659
(97i:90003)
 11.
R. B. Kearfott and J. Dian, Existence verification for higherdegree singular zeros of complex nonlinear systems, 2000, Preprint, Department of Mathematics, Univ. of Louisiana at Lafayette, U.L. Box 41010, Lafayette, La 70504.
 12.
R. B. Kearfott and J. Dian., Verifying topological indices for higherorder rank deficiencies, 2000, Preprint, Department of Mathematics, Univ. of Louisiana at Lafayette, U.L. Box 41010, 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
(2001e:65078), http://dx.doi.org/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
(92b:65004)
 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
(90b:90123)
 16.
J.
M. Ortega and W.
C. Rheinboldt, Iterative solution of nonlinear equations in several
variables, Academic Press, New YorkLondon, 1970. MR 0273810
(42 #8686)
 17.
Frank
Stenger, Computing the topological degree of a mapping in
𝑅ⁿ, Numer. Math. 25 (1975/76),
no. 1, 23–38. MR 0394639
(52 #15440)
 1.
 G. Alefeld and J. Herzberger, Introduction to interval computations, Academic Press, New York, 1983. MR 85d:65001
 2.
 P. Alexandroff and H. Hopf, Topologie, Chelsea, 1935. MR 32:3023; MR 49:9826 (reprints).
 3.
 G. F. Corliss, Globsol entry page, 1998, http://www.mscs.mu.edu/globsol/.
 4.
 J. Cronin, Fixed points and topological degree in nonlinear analysis, American Mathematical Society, Providence, RI, 1964. MR 29:1400
 5.
 E. R. Hansen, Global optimization using interval analysis, Marcel Dekker, Inc., New York, 1992. MR 93i:93002
 6.
 H. Jürgens, H.O. Peitgen, and D. Saupe, Topological perturbations in the numerical nonlinear eigenvalue and bifurcation problems, Analysis and Computation of Fixed Points (New York) (S. M. Robinson, ed.), Academic Press, 1980, pp. 139181. MR 82e:65063
 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.
 , An efficient degreecomputation method for a generalized method of bisection, Numer. Math. 32 (1979), 109127. MR 80g:65062
 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, 6378.
 10.
 , Rigorous global search: Continuous problems, Kluwer, Dordrecht, Netherlands, 1996. MR 97i:90003
 11.
 R. B. Kearfott and J. Dian, Existence verification for higherdegree singular zeros of complex nonlinear systems, 2000, Preprint, Department of Mathematics, Univ. of Louisiana at Lafayette, U.L. Box 41010, Lafayette, La 70504.
 12.
 R. B. Kearfott and J. Dian., Verifying topological indices for higherorder rank deficiencies, 2000, Preprint, Department of Mathematics, Univ. of Louisiana at Lafayette, U.L. Box 41010, Lafayette, La 70504.
 13.
 R. B. Kearfott, J. Dian, and A. Neumaier, Existence verification for singular zeros of complex nonlinear systems, SIAM J. Numer. Anal. 38 (2000), no. 2, 360379. MR 2001e:65078
 14.
 A. Neumaier, Interval methods for systems of equations, Cambridge University Press, Cambridge, England, 1990. MR 92b:65004
 15.
 H. Ratschek and J. Rokne, New computer methods for global optimization, Wiley, New York, 1988. MR 90b:90123
 16.
 W. C. Rheinboldt and J. M. Ortega, Iterative solution of nonlinear equations in several variables, Academic Press, New York, 1970. MR 42:8686
 17.
 F. Stenger, Computing the topological degree of a mapping in , Numer. Math. 25 (1976), 2338. MR 52:15440
Similar Articles
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:
HewlettPackard 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 41010, Lafayette, Louisiana 705041010
Email:
rbk@louisiana.edu
DOI:
http://dx.doi.org/10.1090/S0025571802014278
PII:
S 00255718(02)014278
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 DMS9701540
Article copyright:
© Copyright 2002
American Mathematical Society
