Computation of topological degree using interval arithmetic, and applications

Author:
Oliver Aberth

Journal:
Math. Comp. **62** (1994), 171-178

MSC:
Primary 65G10; Secondary 55M25

DOI:
https://doi.org/10.1090/S0025-5718-1994-1203731-4

MathSciNet review:
1203731

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A method is described for computing the topological degree of a mapping from into defined by *n* functions of *n* variables on a region specified as a product of *n* intervals, a generalized box *B*. The method is an adaptation of Kearfott's method to boxes, and begins by checking the signs of the *n* functions on the boundary of *B* with interval arithmetic. On the basis of this check, a portion, , of the boundary of *B* is designated for further investigation, and one of the *n* functions defining the mapping is dropped. The signs of the remaining functions are checked on the boundary of . Again a portion, , of the boundary of is designated for further investigation, and another of the functions is dropped. On the *n*th cycle of the process, the topological degree finally is evaluated by determining the signs of a single function on a collection of isolated points, comprising the boundary of a region .

When the topological degree is nonzero, there is at least one point inside *B* where the *n* functions are simultaneously zero. To locate such a point, the familiar bisection method for functions defined over an interval [*a, b*], using sign changes of , is easily generalized to apply to *n* functions defined over boxes, using the topological degree. For this application we actually use the topological degree , the *crossing parity*, because its computation is easier. If the *n* functions have all partial derivatives in the box *B*, with a nonzero Jacobian at any point where the functions are simultaneously zero, then all such points inside *B* can be located by another method, which also uses the crossing parity.

**[1]**O. Aberth,*Precise numerical analysis*, Wm. C. Brown, Dubuque, Iowa, 1988.**[2]**O. Aberth and M. J. Schaefer,*Precise scientific computation with range arithmetic, via*, ACM Trans. Math. Software**18**(1992), 481-491.**[3]**G. Alefeld and J. Herzberger,*Introduction to interval computation*, Translated by Jon Rokne, Academic Press, New York, 1983. MR**733988 (85d:65001)****[4]**P. Alexandroff and H. Hopf,*Topologie*, Chelsea, New York, 1935.**[5]**R. C. Buck,*Advanced calculus*, 2nd ed., McGraw-Hill, New York, 1965.**[6]**J. Cronin,*Fixed points and topolgical degree in nonlinear analysis*, Math Surveys, no. 11, Amer. Math. Soc., Providence, RI, 1964. MR**0164101 (29:1400)****[7]**C. Harvey and F. Stenger,*A two-dimensional analogue to the method of bisections for solving nonlinear equations*, Quart. Appl. Math.**33**(1975), 351-368. MR**0455361 (56:13600)****[8]**R. B. Kearfott,*An efficient degree-computation method for a generalized method of bisection*, Numer. Math.**32**(1979), 109-127. MR**529902 (80g:65062)****[9]**-,*A summary of recent experiments to compute the topological degree*, Applied Nonlinear Analysis, Proceedings of an International Conference on Applied Nonlinear Analysis, University of Texas at Arlington, April 20-22, 1978 (V. Laskshmikantham, ed.), Academic Press, New York, 1979, pp. 627-633. MR**537571 (80h:55003)****[10]**-,*Abstract generalized bisection and a cost bound*, Math. Comp.**49**(1987), 187-202. MR**890261 (88h:65109)****[11]**R. E. Moore,*Methods and applications of interval analysis*, SIAM Stud. Appl. Math., SIAM, Philadelphia, PA, 1979. MR**551212 (81b:65040)****[12]**-,*Interval analysis*, Prentice-Hall, Englewood Cliffs, NJ, 1966. MR**0231516 (37:7069)****[13]**A. Neumaier,*Interval methods for systems of equations*, Cambridge Univ. Press, Cambridge, 1990. MR**1100928 (92b:65004)****[14]**T. O'Neal and J. Thomas,*The calculation of the topological degree by quadrature*, SIAM J. Numer. Anal.**12**(1975), 673-680. MR**0411134 (53:14873)****[15]**K. Sikorski,*A three-dimensional analogue to the method of bisections for solving nonlinear equations*, Math. Comp.**33**(1979), 722-738. MR**521286 (80i:65058)****[16]**F. Stenger,*Computing the topological degree of a mapping in*, Numer. Math.**25**(1975), 23-38. MR**0394639 (52:15440)**

Retrieve articles in *Mathematics of Computation*
with MSC:
65G10,
55M25

Retrieve articles in all journals with MSC: 65G10, 55M25

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1994-1203731-4

Article copyright:
© Copyright 1994
American Mathematical Society