Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Abstract generalized bisection and a cost bound
HTML articles powered by AMS MathViewer

by R. Baker Kearfott PDF
Math. Comp. 49 (1987), 187-202 Request permission

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
Similar Articles
  • Retrieve articles in Mathematics of Computation with MSC: 65H10, 68Q25
  • Retrieve articles in all journals with MSC: 65H10, 68Q25
Additional Information
  • © Copyright 1987 American Mathematical Society
  • Journal: Math. Comp. 49 (1987), 187-202
  • MSC: Primary 65H10; Secondary 68Q25
  • DOI: https://doi.org/10.1090/S0025-5718-1987-0890261-9
  • MathSciNet review: 890261