Abstract
Interval Newton methods in conjunction with generalized bisection are important elemetns of algorithms which find theglobal optimum within a specified box X ⊂ ℝn of an objective function ϕ whose critical points are solutions to the system of nonlinear equationsF(X)=0with mathematical certainty, even in finite presision arithmetic. The overall efficiency of such a scheme depends on the power of the interval Newton method to reduce the widths of the coordinate intervals of the box. Thus, though the generalized bisection method will still converge in a box which contains a critical point at which the Jacobian matrix is singular, the process is much more costly in that case. Here, we propose modifications which make the generalized bisection method isolate singular solutions more efficiently. These modifications are based on an observation about the verification property of interval Newton methods and on techniques for detecting the singularity and removing the region containing it. The modifications assume no special structure forF. Additionally, one of the observations should also make the algorithm more efficient when finding nonsingular solutions. We present results of computational experiments.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
G. Alefeld and J. Herzberger,Introduction to Interval Computations (Academic Press, New York, 1983).
E.R. Hansen, On solving systems of equations using interval arithmetic, Math. Comp. 22 (1968) 374–84.
E. Hansen, Global optimization using interval analysis — the multidimensional case, Numer. Math. 34(3) (1980) 247–70.
E. Hansen, and S. Sengupta, Bounding solutions of systems of equations using interval analysis. BIT 21 (1981) 203–11.
R.B. Kearfott, Abstract generalized bisection and a cost bound, Math. Comp. 49 (179) (1987) 187–202.
R.B. Kearfott, Some tests of generalized bisection, ACM Trans. Math. Software 13 (3) (1987) 197–220.
R.B. Kearfott, On handling singular systems with interval Newton methods, IMACS Ann. Comp. Appl. Math. 1.2 (1989) 653–655.
R.B. Kearfott, Preconditioners for the interval Gauss-Seidel method, accepted for publication, SIAM J. Numer. Anal. 27 (3) (1990) 804–822.
R.B. Kearfott, Interval arithmetic techniques in the computational solution of nonlinear systems of equations: introduction, examples, and comparisons, in:Proc. 1988 AMS/SIAM Seminar on Applied Mathematics, American Mathematical Society (1990) pp. 337–357.
R.B. Kearfott, An interval step control for continuation methods, submitted, Math. Comp. (1989).
R.E. Moore,Methods and Applications of Interval Analysis (SIAM, Philadelphia, 1979).
R.E. Moore and S.T. Jones, Safe starting regions for iterative methods, SIAM J. Numer. Anal. 14 (6) (1977) 1051–065.
A. Neumaier, Interval iteration for zeros of systems of equations, BIT 25 (1) (1985) 256–73.
A. Neumaier,Interval Methods for Systems of Equations (Cambridge University Press, 1989; in press).
K. Nickel, On the Newton method in interval analysis, Technical Summary Report no. 1136, Mathematics Research Center, the University of Wisconsin at Madison, Madison, WI.
H. Ratschek and J. Rokne,Computer Methods for the Range of Functions (Ellis Horwood and John Wiley, Chichester, New York, 1984).
H. Ratschek and J. Rokne,New Computer Methods for Global Optimization, (Ellis Horwood and John Wiley, Chichester, New York, 1988).
J.M. Shearer and M.A. Wolfe, Some computable existence, uniquencess, and convergence tests for nonlinear systems, SIAM J. Numer. Anal. 22 (6) (1985) 1200–207.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Kearfott, R.B. Interval Newton/generalized bisection when there are singularities near roots. Ann Oper Res 25, 181–196 (1990). https://doi.org/10.1007/BF02283694
Issue Date:
DOI: https://doi.org/10.1007/BF02283694