Box-bisection for solving second-degree systems and the problem of clustering

ABSTRACT

Box-bisection is a method for solving nonlinear systems. Space is subdivided into boxes of smaller and smaller diameter, and each subbox is tested for the existence of solutions by a test that either eliminates it from further consideration or marks it for subdivision. Simple bisection uses a test for the exclusion of subboxes, but no test that guarantees the existence of a unique solution in a subbox. Using this simple bisection, we show that the passed boxes tend to cluster in geometrical configura- tions whose number is stable under subdivision. This implies for many problems that the work required to do simple bisection may be prohibitive. However, improvements may be possible by grouping clusters and dynamically redefining the box proportions. The restriction to second-degree systems is sufficient to display this behavior.

REFERENCES

• 1: CHOW, S. N., MALLET-PARET, J., AND YORKE, J.A. A homotopy method for locating all zeros of a systems of polynomials. In Functional Differential Equations and Approximation of Fixed Points, H. O. Peitgen and H. O. Walther (Eds.), Lecture Notes in Mathematics vol. 730. Springer- Verlag, New York, 1979, 228-237.
• 2: A. Eiger , K. Sikorski , F. Stenger, A bisection method for systems of nonlinear equations, ACM Transactions on Mathematical Software (TOMS), v.10 n.4, p.367-377, Dec. 1984 [doi>10.1145/2701.2705]
• 3: FIELD, D., AND MORGAN, A. A quick method for determining whether a second-degree polynomial has solutions in a given box. IEEE Comput. Graph. Appl., 2 (1982), 65-68.
• 4: GARCIA, C. B., AND ZANGWILL, W. I. Pathways to Solutions, Fixed Points, and Equilibria. Prentice-Hall, Englewood Cliffs, N.J., 1981.
• 5: HANSEN, E. R., AND SENGUPTA, S. Bounding solutions of systems of equations using interval arithmetic. BIT 21 (1981), 203-211.
• 6: KEARFOTT, R.B. A proof of convergence and an error bound for the method of bisection in R" Math. Comput. 32 (1978), 1147-1153.
• 7: KEARFOTT, R.B. An efficient degree-computation method for a generalized method of bisection. Numer. Math. 39 (1979), 109-127.
• 8: KEARFOTr, R. B. Cube bisection and always finding all solutions reliably. Submitted for publication.
• 9: KEARFOI'r, R.B. Abstract generalized bisection and a cost bound. Math. Comput. To appear July 1987.
• 10: R. Baker Kearfott, Some tests of generalized bisection, ACM Transactions on Mathematical Software (TOMS), v.13 n.3, p.197-220, Sept. 1987 [doi>10.1145/29380.29862]
• 11: Keith Meintjes , Alexander P Morgan, A methodology for solving chemical equilibrium systems, Applied Mathematics and Computation, v.22 n.4, p.333-361, June 1987 [doi>10.1016/0096-3003(87)90076-2]
• 12: MOORE, R. E., AND JONES, S.T. Safe starting regions for iterative methods. SIAM J. Numer. Anal. 14 (1977), 1051-1065.
• 13: MOORE, R. E., AND QI, L. A successive interval test for nonlinear systems. SIAM J. Numer. Anal. 19 (1982), 845-850.
• 14: MORGAN, A.P. A homotopy for solving polynomial systems. Appl. Math. Comput. 18 (1986), 87-92.
• 15: MORGAN, A.P. A transformation to avoid solutions an infinity for polynomial systems. Appl. Math. Comput. 18 (1986), 77-86.
• 16: MORGAN, A.P. Solving Polynomial Systems Using Continuation for Engineering and Scientific Problems. Prentice-Hall, Englewood Cliffs, N.J., 1987.
• 17: NIJENHUIS, A., AND WILF, H.S. Combinatorial Algorithms. Academic Press, New York, 1975.
• 18: SIKORSKL K. A three-dimensional analogue to the method of bisections for solving nonlinear equations. Math. Comput. 33 (1979), 722-738.
• 19: STENGER, F. Computing the topological degree of a mapping in Rn. Numer. Math. 25 (1975), 23-38.
• 20: TSAI, L.-W., AND MORGAN, A.P. Solving the kinematics of the most general six- and fivedegree-of-freedom manipulators by continuation methods. ASME J. Mech. Transm. Automa. Des. 107 (1985), 189-200.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Systems of equations

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Iterative methods; Polynomials, methods for

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.9 Robotics
          Subjects: Manipulators

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Chemistry

General Terms:
Algorithms, Theory

Keywords:
bisection, chemical equilibrium problems, inverse kinematics of manipulators, root finding, systems of polynomials