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 Free Access

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 within a given compact domain . We devise a general framework such that any algorithm fitting into the general framework will always isolate all solutions such that ; 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.

**[1]**Eugene Allgower and Kurt Georg,*Simplicial and continuation methods for approximating fixed points and solutions to systems of equations*, SIAM Rev.**22**(1980), no. 1, 28–85. MR**554709**, 10.1137/1022003**[2]**J. E. Dennis & R. B. Schnabel,*Numerical Methods for Unconstrained Optimization and Nonlinear Least Squares*, Prentice-Hall, Englewood Cliffs, N. J., 1983.**[3]**A. Eiger, K. Sikorski, and F. Stenger,*A bisection method for systems of nonlinear equations*, ACM Trans. Math. Software**10**(1984), no. 4, 367–377. MR**792001**, 10.1145/2701.2705**[4]**C. B. García and T. Y. Li,*On the number of solutions to polynomial systems of equations*, SIAM J. Numer. Anal.**17**(1980), no. 4, 540–546. MR**584729**, 10.1137/0717046**[5]**C. B. Garcia & W. I. Zangwill,*Pathways to Solutions, Fixed Points, and Equilibria*, Prentice-Hall, Englewood Cliffs, N. J., 1981.**[6]**Eldon Hansen,*A globally convergent interval method for computing and bounding real roots*, BIT**18**(1978), no. 4, 415–424. MR**520752**, 10.1007/BF01932020**[7]**Eldon Hansen,*Global optimization using interval analysis—the multidimensional case*, Numer. Math.**34**(1980), no. 3, 247–270. MR**571289**, 10.1007/BF01396702**[8]**Eldon Hansen and Saumyendra Sengupta,*Bounding solutions of systems of equations using interval analysis*, BIT**21**(1981), no. 2, 203–211. MR**627881**, 10.1007/BF01933165**[9]**E. Hansen, private communication, 1984.**[10]**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**0455361****[11]**F. B. Hildebrand,*Introduction to numerical analysis*, 2nd ed., McGraw-Hill Book Co., New York-Düsseldorf-Johannesburg, 1974. International Series in Pure and Applied Mathematics. MR**0347033****[12]**R. B. Kearfott,*Computing the Degree of Maps and a Generalized Method of Bisection*, Ph.D. dissertation, University of Utah, 1977.**[13]**Baker Kearfott,*An efficient degree-computation method for a generalized method of bisection*, Numer. Math.**32**(1979), no. 2, 109–127. MR**529902**, 10.1007/BF01404868**[14]**Ralph Baker Kearfott,*On a general technique for finding directions proceeding from bifurcation points*, Numerical methods for bifurcation problems (Dortmund, 1983) Internat. Schriftenreihe Numer. Math., vol. 70, Birkhäuser, Basel, 1984, pp. 210–218. MR**821031****[15]**R. E. Moore and S. T. Jones,*Safe starting regions for iterative methods*, SIAM J. Numer. Anal.**14**(1977), no. 6, 1051–1065. MR**0468147****[16]**Alexander P. Morgan,*A method for computing all solutions to systems of polynomial equations*, ACM Trans. Math. Software**9**(1983), no. 1, 1–17. MR**715803**, 10.1145/356022.356023**[17]**Werner C. Rheinboldt and John V. Burkardt,*A locally parameterized continuation process*, ACM Trans. Math. Software**9**(1983), no. 2, 215–235. MR**715303**, 10.1145/357456.357460**[18]**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**, 10.1090/S0025-5718-1979-0521286-6**[19]**F. Stenger, "An algorithm for the topological degree of a mapping in ,"*Numer. Math.*, v. 25, 1976, pp. 23-28.**[20]**Michael J. Todd,*The computation of fixed points and applications*, Springer-Verlag, Berlin-New York, 1976. Lecture Notes in Economics and Mathematical Systems, Vol. 124. MR**0410732****[21]**Alan Tucker,*Applied combinatorics*, John Wiley & Sons, Inc., New York, 1980. MR**591461**

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

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

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1987-0890261-9

Keywords:
Nonlinear algebraic systems,
global optimization,
analysis of algorithms,
generalized bisection,
Kantorovich theorem

Article copyright:
© Copyright 1987
American Mathematical Society