Computation of Topological Degree Using Interval Arithmetic, and Applications
Oliver Aberth · Mathematics of Computation · 1994
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.