Method and apparatus for solving systems of nonlinear equations using interval arithmetic

Abstract

One embodiment of the present invention provides a computer-based system for solving a system of nonlinear equations specified by a vector function, f, wherein f(x)=0 represents ƒ(x)=0, ƒ(x)=0, ƒ(x)=0 . . . , ƒ(x)=0, wherein x is a vector (x, X, X, . . . x). The system operates by receiving a representation of a subbox X=(X, X, . . . , X), wherein for each dimension, i, the representation of X, includes 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. The system stores the representation in a computer memory. Next, the system applies term consistency to the set of nonlinear equations, ƒ(x)=0, ƒ(x)=0, ƒ(x)=0, . . . , ƒ,(x)=0, over X, and excludes portions of X that violate the set of nonlinear equations. The system also applies box consistency to the set of nonlinear equations over X, and excludes portions of X that violate the set of nonlinear equations. Finally, the system performs an interval Newton step on X to produce a resulting subbox Y, wherein the point of expansion of the interval Newton step is a point x within X, and wherein performing the interval Newton step involves evaluating f(x) using interval arithmetic to produce an interval result f(x). The system integrates the sub-parts of the process with branch tests designed to increase the overall speed of the process.