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ö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****[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]**Jane Cronin,*Fixed points and topological degree in nonlinear analysis*, Mathematical Surveys, No. 11, American Mathematical Society, Providence, R.I., 1964. MR**0164101****[7]**Charles Harvey and Frank Stenger,*A two-dimensional analogue to the method of bisections for solving nonlinear equations*, Quart. Appl. Math.**33**(1975/76), no. 4, 351–368. MR**0455361**, https://doi.org/10.1090/S0033-569X-1976-0455361-7**[8]**Baker Kearfott,*An efficient degree-computation method for a generalized method of bisection*, Numer. Math.**32**(1979), no. 2, 109–127. MR**529902**, https://doi.org/10.1007/BF01404868**[9]**Baker Kearfott,*A summary of recent experiments to compute the topological degree*, Applied nonlinear analysis (Proc. Third Internat. Conf., Univ. Texas, Arlington, Tex., 1978) Academic Press, New York-London, 1979, pp. 627–633. MR**537571****[10]**R. Baker Kearfott,*Abstract generalized bisection and a cost bound*, Math. Comp.**49**(1987), no. 179, 187–202. MR**890261**, https://doi.org/10.1090/S0025-5718-1987-0890261-9**[11]**Ramon E. Moore,*Methods and applications of interval analysis*, SIAM Studies in Applied Mathematics, vol. 2, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, Pa., 1979. MR**551212****[12]**Ramon E. Moore,*Interval analysis*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1966. MR**0231516****[13]**Arnold Neumaier,*Interval methods for systems of equations*, Encyclopedia of Mathematics and its Applications, vol. 37, Cambridge University Press, Cambridge, 1990. MR**1100928****[14]**T. O’Neil and J. W. Thomas,*The calculation of the topological degree by quadrature*, SIAM J. Numer. Anal.**12**(1975), no. 5, 673–680. MR**0411134**, https://doi.org/10.1137/0712050**[15]**Krzysztof Sikorski,*A three-dimensional analogue to the method of bisections for solving nonlinear equations*, Math. Comp.**33**(1979), no. 146, 722–738. MR**521286**, https://doi.org/10.1090/S0025-5718-1979-0521286-6**[16]**Frank Stenger,*Computing the topological degree of a mapping in 𝑅ⁿ*, Numer. Math.**25**(1975/76), no. 1, 23–38. MR**0394639**, https://doi.org/10.1007/BF01419526

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