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

摘要

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 . . . , ƒ_n(x)=0, wherein x is a vector (x₁, X₂, X₃, . . . x_n). The system operates by receiving a representation of a subbox X=(X₁, X₂, . . . , X_n), 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. 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, . . . , ƒ_n,(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^I(x). The system integrates the sub-parts of the process with branch tests designed to increase the overall speed of the process.