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

摘要

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_n), wherein the system of non-linear equations is specified by a vector function f=(f₁, . . . , f_n). 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 X_i includes a first floating-point number, a_i, representing the left endpoint of X_i, and a second floating-point number, b_i, representing the right endpoint of X_i. 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 f(x) to produce an interval result f¹(x). The system then evaluates a first termination condition, wherein the first termination condition is TRUE if: zero is contained within f¹(x), J(x, X) is regular (wherein J(x, X) is the Jacobian of the function f 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.