Termination criteria for the one-dimensional interval version of newton's method

Abstract

One embodiment of the present invention provides a system for finding zeros of a function, ƒ, within an interval, X, using the interval version of Newton's method. The system operates by receiving a representation of the interval X. This representation including a first floating-point number, a, representing the left endpoint of X, and a second floating-point number, b, representing the right endpoint of X. Next, the system performs an interval Newton step on X, wherein the point of expansion is the midpoint, x, of the interval X. Note that performing the interval Newton step involves evaluating ƒ(x) to produce an interval result ƒ(x). If ƒ(x) contains zero, the system evaluates ƒ(a) to produce an interval result ƒ(a). It also evaluates ƒ(b) to produce an interval result ƒ(b). The system then evaluates a termination condition for the processing of the current interval X, wherein the termination condition is TRUE if a number of sub-conditions are satisfied, including if ƒ(a) contains zero and if ƒ(b) contains zero. If the termination condition is TRUE, the system terminates the processing of the current interval X, and records X as a final bound.