Solving a nonlinear equation through interval arithmetic and term consistency

Abstract

One embodiment of the present invention provides a system for solving a nonlinear equation through interval arithmetic. During operation, the system receives a representation of the nonlinear equation ƒ(x)=0, as well as a representation of an initial interval, X, wherein this representation of X includes a first floating-point number, X L , for the left endpoint of X, and a second floating-point number, X U , for the right endpoint of X. Next, the system symbolically manipulates the nonlinear equation ƒ(x)=0 to solve for a first term, g 1 (x), thereby producing a modified equation g 1 (x)=h 1 (x), wherein the first term g 1 (x) can be analytically inverted to produce an inverse function g 1 −1 (x). The system then plugs the initial interval X into the modified equation to produce the equation g 1 (X′)=h 1 (X), and solves for X′=g 1 −1 [h 1 (X)]. Next, the system intersects X′ with the initial interval X to produce a new interval X + , wherein the new interval X + contains all solutions of the equation ƒ(x)=0 within the initial interval X, and wherein the size of the new interval X + is less than or equal to the size of the initial interval X.

What is claimed is:  
     
       1. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for using a computer system to solve a nonlinear equation by using interval arithmetic, the method comprising: 
       receiving a representation of the nonlinear equation ƒ(x)=0 within the computer system;  
       receiving a representation of an initial interval, X, within the computer system, wherein the representation includes a first floating-point number, X L , for the left endpoint of X, and a second floating-point number, X U , for the right endpoint of X;  
       symbolically manipulating the nonlinear equation ƒ(x)=0 within the computer system to solve for a first term, g 1 (x), thereby producing a modified equation g 1 (x)=h 1 (x), wherein the first term g 1 (x) can be analytically inverted to produce an inverse function g 1   −1 (x);  
       plugging the initial interval X into the modified equation to produce the equation g 1 (X′)=h 1 (X);  
       solving for X′=g 1   −1 [h 1 (X)]; and  
       intersecting X′ with the initial interval X to produce a new interval X + ;  
       wherein the new interval X +  contains all solutions of the equation ƒ(x)=0 within the initial interval X, and wherein the size of the new interval X +  is less than or equal to the size of the initial interval X.  
     
     
       2. The computer-readable storage medium of  claim 1 , wherein the method further comprises: 
       setting X=X + ; and  
       repeating the process of symbolically manipulating, plugging, solving and intersecting to produce a new interval X +  for a second term g 2 (x)=h 2 (x), wherein the second term g 2 (x) can be analytically inverted to produce an inverse function g 2   −1 .  
     
     
       3. The computer-readable storage medium of  claim 1 , wherein for each term, g 1 (x), that can be analytically inverted within the equation ƒ(x)=0, the method further comprises: 
       setting X=X + ; and  
       repeating the process of symbolically manipulating, plugging, solving and intersecting to produce a new interval X + .  
     
     
       4. The computer-readable storage medium of  claim 1 , wherein the method further comprises performing an interval Newton step on the function ƒ(x)=0 and the initial interval X to narrow the set of interval solutions to the equation ƒ(x)=0. 
     
     
       5. The computer-readable storage medium of  claim 1 , wherein symbolically manipulating the nonlinear equation ƒ(x)=0 involves first selecting the invertible term, g 1 (x), as the term that dominates the function ƒ(x)=0 within the interval X. 
     
     
       6. The computer-readable storage medium of  claim 1 , wherein receiving the representation of the nonlinear equation ƒ(x)=0 involves symbolically manipulating an inequality to produce the nonlinear equation ƒ(x)=0. 
     
     
       7. The computer-readable storage medium of  claim 1 , wherein the method is performed as part of an optimization process.