Algorithm 681: INTBIS, a portable interval Newton/bisection package

ABSTRACT

We present a portable software package for finding all real roots of a system of nonlinear equations within a region defined by bounds on the variables. Where practical, the package should find all roots with mathematical certainty. Though based on interval Newton methods, it is self-contained. It allows various control and output options and does not require programming if the equations are polynomials; it is structured for further algorithmic research. Its practicality does not depend in a simple way on the dimension of the system or on the degree of nonlinearity.

REFERENCES

• 1: ALEFELD, G., AND HERZBERGER, J. Introduction to Interval Computations. Academic Press, New York, 1983.
• 2: DONGARRA, J. J., MOLER, C. B., BUNCH, J. R., AND STEWART, G.W. LINPACK Users' Guide. SIAM, Philadelphia, 1979.
• 3: Jack J. Dongarra , Eric Grosse, Distribution of mathematical software via electronic mail, ACM SIGNUM Newsletter, v.20 n.3, p.45-47, July 1985 [doi>10.1145/1057947.1057951]
• 4: HANSEN, E. R., AND GREENBERG, R.i. An Interval Newton method. Appl. Math. Comput. 12 (1983), 89-98.
• 5: HANSEN, E. a., AND SENGUPTA, S. Bounding solutions of systems of equations using interval analysis. BIT 21 {1981), 203-211.
• 6: KEARFOTT, R.S. Abstract generalized bisection and a cost bound. Math. Comput. 49, 179 (July 1987), 187-202.
• 7: 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]
• 8: KEARFOTT, R.B. On handling singular systems with interval Newton methods. In Proceedings of the Twelfth IMACS World Congress on Scientific Computation, 1988.
• 9: R. Baker Kearfott, Preconditioners for the interval Gauss-Seidel method, SIAM Journal on Numerical Analysis, v.27 n.3, p.804-822, June 1990 [doi>10.1137/0727047]
• 10: KEARFOTT, R.S. Interval arithmetic methods for nonlinear systems and nonlinear optimization: An introductory review. In Impacts of Recent Computer Advances on Operations Research. Elsevier, New York, 1989.
• 11: MOORE, R. E., AND JONES, S.T. Safe starting regions for iterative methods. SIAM J. Numer. Anal. 14, 6 (Dec. 1977), 1051-1065.
• 12: Ramon E. Moore , Fritz Bierbaum, Methods and Applications of Interval Analysis (SIAM Studies in Applied and Numerical Mathematics) (Siam Studies in Applied Mathematics, 2.), Soc for Industrial & Applied Math, 1979
• 13: MOORE, R. E., ED. Reliability in Computing. Academic Press, New York, 1988.
• 14: MORGAN, A.P. Solving Polynomial Systems using Continuation for Engineering and Scientific Problems. Prentice-Hall, Englewood Cliffs, N.J., 1987.
• 15: RATSCHEK, H., AND ROKNE, J.G. Computer Methods for the Range of Functions. Horwood, Chichester, England, 1984.

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

General Terms:
Algorithms, Theory