Computation of topological degree using interval arithmetic, and applications
HTML articles powered by AMS MathViewer
- by Oliver Aberth PDF
- Math. Comp. 62 (1994), 171-178 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), 481-491.
- 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., McGraw-Hill, 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 two-dimensional 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/S0033-569X-1976-0455361-7
- Baker Kearfott, An efficient degree-computation 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 York-London, 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/S0025-5718-1987-0890261-9
- 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, Prentice-Hall, 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 three-dimensional analogue to the method of bisections for solving nonlinear equations, Math. Comp. 33 (1979), no. 146, 722–738. MR 521286, DOI 10.1090/S0025-5718-1979-0521286-6
- 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), 171-178
- MSC: Primary 65G10; Secondary 55M25
- DOI: https://doi.org/10.1090/S0025-5718-1994-1203731-4
- MathSciNet review: 1203731