Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2005-07-05
2005-07-05
Ngo, Chuong Dinh (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06915320
ABSTRACT:
One embodiment of the present invention provides a system for finding zeros of a function, ƒ, within an interval, X, using the interval version of Newton's method. The system operates by receiving a representation of the interval X. This representation including 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. Next, the system performs an interval Newton step on X, wherein the point of expansion is the midpoint, x, of the interval X. Note that performing the interval Newton step involves evaluating ƒ(x) to produce an interval result ƒI(x). If ƒI(x) contains zero, the system evaluates ƒ(a) to produce an interval result ƒI(a). It also evaluates ƒ(b) to produce an interval result ƒI(b). The system then evaluates a termination condition for the processing of the current interval X, wherein the termination condition is TRUE if a number of sub-conditions are satisfied, including if ƒI(a) contains zero and if ƒI(b) contains zero. If the termination condition is TRUE, the system terminates the processing of the current interval X, and records X as a final bound.
REFERENCES:
patent: 5220524 (1993-06-01), Hesson
patent: 5631858 (1997-05-01), Narita et al.
patent: 2004/0015830 (2004-01-01), Reps
Publication: “Design, implementation and evaluation of the constraint language cc (FD)” by Pascal Van Hentenryck et al., The Journal of Logic Programming 37, 1998, pp. 139-164.
E.R. Hansen, “Global Optimization Using Interval Analysis,” Marcel Dekker, Inc., New York, NY, 1992.
R.B. Kearfott, “A Fortran 90 Environment for Research and Prototyping of Enclosure Algorithms fo Nonlinear Equations and Global Optimization,” ACM Transactioins on Mathematical Software, vol. 21, No. 1, Mar. 1995, pp. 63-78 http://interval.louisiana.edu/preprints.html.
R. B. Kearfott, Algorithm 763: Interval Arithmetic: A Fortran 90 Module for an Interval Data Type, ACM Trans. Math. Software, 22, vol. 4, 1996, pp. 385-392. http://interval.louisiana.edu/preprints.html.
R. B. Kearfott and M. Novoa III, “Algorithm 681: INTBIS, A portable interval Newton/bisection package”, ACM Trans. Math. Software, vol. 16, no. 2, pp. 152-147. http://www.netlib.org/toms/681.
R. B. Kearfott, M. Dawande, K.S. Du, and C. Hu, “Algorithm 737: INTLIB: A Portable Fortran 737 Interval Standard Function Library,” ACM Trans. Math. Software, 20, vol. 4, Dec. 1994, pp. 447-458.
R. B. Kearfott and G.W. Walster, “On Stopping Criteria in Verified Nonlinear Systems or Optimization Algorithms,” ACM Trans. Math. Software, 26, vol. 3, Sep. 2000, pp. 323-351. The publication itself says Received: Jul. 1999; revised: Mar. 2000; accepted: Mar. 2000. http:/interval.louisiana.edu/preprints.html.
R.E. Moore and S.T. Jones “Safe Starting Regions for Iterative Methods”, SIAM Journal on Numerical Analysis, vol. 14, No. 6 (Dec. 1977), pp. 1051-1065.
A. Neumaier, “The Enclosure of Solutions of Parameter-Dependent Systems of Equations,” Cambridge University Press, Cambridge, 1990, ISBN: 0-12-505630-3, Reliability in Computing pp. 269-286.
S.M. Rump, “Verification Methods for Dense and Sparse Systems of Equations,” in Topics in Validated Computations: Proceedings of the IMACS-GAMM International Workshop on Validated Computations, University of Oldenburg, J. Herzberger, ed., Elsevier Studies in Computational Mathematics, Elsevier, 1994, pp. 63-136.
Hansen Eldon R.
Walster G. William
Ngo Chuong Dinh
Park Vaughan & Fleming LLP
Sun Microsystems Inc.
LandOfFree
Termination criteria for the one-dimensional interval... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Termination criteria for the one-dimensional interval..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Termination criteria for the one-dimensional interval... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3372296