Empirical Evaluation of Innovations in Interval Branch and Bound Algorithms for Nonlinear Systems
Ralph Baker Kearfott · SIAM Journal on Scientific Computing · 1997
Interval branch and bound algorithms for finding all roots use a combination of a computational existence/uniqueness procedure and a tessellation process (generalized bisection). Such algorithms identify, with mathematical rigor, a set of boxes that contains unique roots and a second set within which all remaining roots must lie. Though each root is contained in a box in oneof the sets, the second set may have several boxes in clusters near a single root. Thus, the output is of higher quality if there are relatively more boxes in the first set. In contrast to previously implemented similar techniques, a box expansion technique in this paper, based on using an approximate root finder, $\epsilon$-inflation, and exact set complementation, decreases the size of the second set, increases the size of the first set, and never loses roots. In addition to the expansion technique, use of second-order extensions to eliminate small boxes that do not contain roots, and interval slopes versus interval derivative matrices are studied. These items are evaluated empirically on a significant test problem set, within a Fortran-90 environment designed for such purposes. The results are compared with previous results and show that careful incorporation of the techniques yields both quantitatively and qualitatively superior computer codes.