Termination criteria for the interval version of newton's method for solving systems of non-linear equations

Abstract

One embodiment of the present invention provides a system for finding the roots of a system of nonlinear equations within an interval vector X=(X, . . . , X), wherein the system of non-linear equations is specified by a vector function ƒ=(ƒ, . . . , ƒ). The system operates by receiving a representation of the interval vector X (which is also called a box), wherein for each dimension, i, the representation of Xincludes a first floating-point number, α, 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 to produce a resulting interval vector, X', wherein the point of expansion of the interval Newton step is a point, x, within the interval X, and wherein performing the interval Newton step involves evaluating ƒ(x) to produce an interval result ƒ(x). The system then evaluates a first termination condition, wherein the first termination condition is TRUE if: zero is contained within ƒ(x), J(x,X) is regular (wherein J(x,X) is the Jacobian of the function ƒevaluated with respect to x over the box X); and X is contained within X′. If the first termination condition is TRUE, the system terminates the interval Newton method and records X′ as a final bound.