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
- 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, DOI 10.1137/1022003 J. E. Dennis & R. B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Least Squares, Prentice-Hall, Englewood Cliffs, N. J., 1983.
- 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, DOI 10.1145/2701.2705
- C. B. García and Tien-Yian Li, On the number of solutions to polynomial systems of equations, SIAM J. Numer. Anal. 17 (1980), no. 4, 540–546. MR 584729, DOI 10.1137/0717046 C. B. Garcia & W. I. Zangwill, Pathways to Solutions, Fixed Points, and Equilibria, Prentice-Hall, Englewood Cliffs, N. J., 1981.
- Eldon Hansen, A globally convergent interval method for computing and bounding real roots, BIT 18 (1978), no. 4, 415–424. MR 520752, DOI 10.1007/BF01932020
- Eldon Hansen, Global optimization using interval analysis—the multidimensional case, Numer. Math. 34 (1980), no. 3, 247–270. MR 571289, DOI 10.1007/BF01396702
- Eldon Hansen and Saumyendra Sengupta, Bounding solutions of systems of equations using interval analysis, BIT 21 (1981), no. 2, 203–211. MR 627881, DOI 10.1007/BF01933165 E. Hansen, private communication, 1984.
- 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 455361, DOI 10.1090/S0033-569X-1976-0455361-7
- F. B. Hildebrand, Introduction to numerical analysis, 2nd ed., International Series in Pure and Applied Mathematics, McGraw-Hill Book Co., New York-Düsseldorf-Johannesburg, 1974. MR 0347033 R. B. Kearfott, Computing the Degree of Maps and a Generalized Method of Bisection, Ph.D. dissertation, University of Utah, 1977.
- Baker Kearfott, An efficient degree-computation method for a generalized method of bisection, Numer. Math. 32 (1979), no. 2, 109–127. MR 529902, DOI 10.1007/BF01404868
- 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
- R. E. Moore and S. T. Jones, Safe starting regions for iterative methods, SIAM J. Numer. Anal. 14 (1977), no. 6, 1051–1065. MR 468147, DOI 10.1137/0714072
- 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, DOI 10.1145/356022.356023
- Werner C. Rheinboldt and John V. Burkardt, A locally parameterized continuation process, ACM Trans. Math. Software 9 (1983), no. 2, 215–235. MR 715303, DOI 10.1145/357456.357460
- 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, DOI 10.1090/S0025-5718-1979-0521286-6 F. Stenger, "An algorithm for the topological degree of a mapping in ${{\mathbf {R}}^n}$," Numer. Math., v. 25, 1976, pp. 23-28.
- Michael J. Todd, The computation of fixed points and applications, Lecture Notes in Economics and Mathematical Systems, Vol. 124, Springer-Verlag, Berlin-New York, 1976. MR 0410732
- Alan Tucker, Applied combinatorics, John Wiley & Sons, Inc., New York, 1980. MR 591461
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