Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Abstract generalized bisection and a cost bound

Author: R. Baker Kearfott
Journal: Math. Comp. 49 (1987), 187-202
MSC: Primary 65H10; Secondary 68Q25
MathSciNet review: 890261
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The purpose of this paper is to study desirable properties of binary search algorithms for isolating all solutions to nonlinear systems of equations $ F(X) = 0$ within a given compact domain $ {\mathbf{D}} \in {{\mathbf{R}}^n}$. We devise a general framework such that any algorithm fitting into the general framework will always isolate all solutions $ Z \in {\mathbf{D}}$ such that $ F(Z) = 0$; this framework contains a new idea for handling the occurrence of roots on boundaries. We then present and prove a bound on the total amount of computation which is valid for any algorithm in the class.

Finally, we define a specific prototypical algorithm valid for F satisfying certain natural smoothness properties; we show that it satisfies the hypotheses for the general framework. This algorithm is based on "bisection" of generalized rectangles, the Kantorovich theorem, and second-order Taylor type models for F. It is meant to provide further guidelines for the development of effective heuristics, etc., for actual implementations.

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

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65H10, 68Q25

Retrieve articles in all journals with MSC: 65H10, 68Q25

Additional Information

Keywords: Nonlinear algebraic systems, global optimization, analysis of algorithms, generalized bisection, Kantorovich theorem
Article copyright: © Copyright 1987 American Mathematical Society

American Mathematical Society