Computation of topological degree using interval arithmetic, and applications
HTML articles powered by AMS MathViewer
 by Oliver Aberth PDF
 Math. Comp. 62 (1994), 171178 Request permission
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

O. Aberth, Precise numerical analysis, Wm. C. Brown, Dubuque, Iowa, 1988.
O. Aberth and M. J. Schaefer, Precise scientific computation with range arithmetic, via $C + +$, ACM Trans. Math. Software 18 (1992), 481491.
 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 P. Alexandroff and H. Hopf, Topologie, Chelsea, New York, 1935. R. C. Buck, Advanced calculus, 2nd ed., McGrawHill, New York, 1965.
 Jane Cronin, Fixed points and topological degree in nonlinear analysis, Mathematical Surveys, No. 11, American Mathematical Society, Providence, R.I., 1964. MR 0164101
 Charles Harvey and Frank Stenger, A twodimensional analogue to the method of bisections for solving nonlinear equations, Quart. Appl. Math. 33 (1975/76), no. 4, 351–368. MR 455361, DOI 10.1090/S0033569X197604553617
 Baker Kearfott, An efficient degreecomputation method for a generalized method of bisection, Numer. Math. 32 (1979), no. 2, 109–127. MR 529902, DOI 10.1007/BF01404868
 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 YorkLondon, 1979, pp. 627–633. MR 537571
 R. Baker Kearfott, Abstract generalized bisection and a cost bound, Math. Comp. 49 (1987), no. 179, 187–202. MR 890261, DOI 10.1090/S00255718198708902619
 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
 Ramon E. Moore, Interval analysis, PrenticeHall, Inc., Englewood Cliffs, N.J., 1966. MR 0231516
 Arnold Neumaier, Interval methods for systems of equations, Encyclopedia of Mathematics and its Applications, vol. 37, Cambridge University Press, Cambridge, 1990. MR 1100928
 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 411134, DOI 10.1137/0712050
 Krzysztof Sikorski, A threedimensional analogue to the method of bisections for solving nonlinear equations, Math. Comp. 33 (1979), no. 146, 722–738. MR 521286, DOI 10.1090/S00255718197905212866
 Frank Stenger, Computing the topological degree of a mapping in $\textbf {R}^{n}$, Numer. Math. 25 (1975/76), no. 1, 23–38. MR 394639, DOI 10.1007/BF01419526
Additional Information
 © Copyright 1994 American Mathematical Society
 Journal: Math. Comp. 62 (1994), 171178
 MSC: Primary 65G10; Secondary 55M25
 DOI: https://doi.org/10.1090/S00255718199412037314
 MathSciNet review: 1203731