Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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 $ {R^n}$ into $ {R^n}$ 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, $ {B^{(1)}}$, 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 $ {B^{(1)}}$. Again a portion, $ {B^{(2)}}$, of the boundary of $ {B^{(1)}}$ is designated for further investigation, and another of the functions is dropped. On the nth 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 $ {B^{(n - 1)}}$.

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 $ f(x)$ defined over an interval [a, b], using sign changes of $ f(x)$, is easily generalized to apply to n functions defined over boxes, using the topological degree. For this application we actually use the topological degree $ \bmod\;2$, 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.


References [Enhancements On Off] (What's this?)

  • [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 $ C + + $, 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 $ {R^n}$, Numer. Math. 25 (1975), 23-38. MR 0394639 (52:15440)

Similar Articles

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

American Mathematical Society