Abstract
Interval methods for ordinary differential equations (ODEs) provide guaranteed enclosures of the solutions and numerical proofs of existence and unicity of the solution. Unfortunately, they may result in large over-approximations of the solution because of the loss of precision in interval computations and the wrapping effect. The main open issue in this area is to find tighter enclosures of the solution, while not sacrificing efficiency too much. This paper takes a constraint satisfaction approach to this problem, whose basic idea is to iterate a forward step to produce an initial enclosure with a pruning step that tightens it. The paper focuses on the pruning step and proposes novel multistep filtering operators for ODEs. These operators are based on interval extensions of a multistep solution that are obtained by using (Lagrange and Hermite) interpolation polynomials and their error terms. The paper also shows how traditional techniques (such as mean-value forms and coordinate transformations) can be adapted to this new context. Preliminary experimental results illustrate the potential of the approach, especially on stiff problems, well-known to be very difficult to solve.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aberth, O.: Precise Numerical Analysis. William Brown (1988)
Alefeld, G., Herzberger, J.: Introduction to Interval Computations. Academic Press, New York (1983)
Atkinson, K.E.: An Introduction to Numerical Analysis. Wiley, Chichester (1988)
Berz, M., Bischof, C., Corliss, G., Griewank, A. (eds.): Computational Differentiation: Techniques, Applications, and Tools. SIAM, Philadelphia (1996)
Corliss, G.F.: Applications of differentiation arithmetic. In: Moore, R.E. (ed.) Reliability in Computing, pp. 127–148. Academic Press, London (1988)
Deville, Y., Janssen, M., Van Hentenryck, P.: Consistency Techniques in Ordinary Differential Equations. In: Maher, M.J., Puget, J.-F. (eds.) CP 1998. LNCS, vol. 1520, pp. 162–176. Springer, Heidelberg (1998)
Kincaid, D., Cheney, W.: Numerical Analysis. Brooks/Cole (1996)
Lohner, R.J.: Enclosing the solutions of ordinary initial and boundary value problems. In: Kaucher, E.W., Kulisch, U.W., Ullrich, C. (eds.) Computer Arithmetic: Scientific Computation and Programming Languages, pp. 255–286. Wiley, Chichester (1987)
Moore, R.E.: Interval Analysis. Prentice-Hall, Englewood Cliffs (1966)
Moore, R.E.: Methods and Applications of Interval Analysis. SIAM, Philadelphia (1979)
Neumaier, A.: Interval Methods for Systems of Equations. PHI Series in Computer Science. Cambridge University Press, Cambridge (1990)
Rall, L.B.: Applications of software for automatic differentiation in numerical computation. In: Alefeld, G., Grigorieff, R.D. (eds.) Fundamentals of Numerical Computation (Computer Oriented Numerical Analysis). Computing Supplement No. 2, pp. 141–156. Springer-Verlag, Heidelberg (1980)
Rall, L.B.: Automatic Differentiation: Techniques and Applications. LNCS, vol. 120. Springer-Verlag, Heidelberg (1981)
Stauning, O.: Enclosing Solutions of Ordinary Differential Equations. Tech. Report IMM-REP-1996-18, Technical University Of Denmark (1996)
Van Hentenryck, P.: A Constraint Satisfaction Approach to a Circuit Design Problem. Journal of Global Optimization 13, 75–93 (1998)
Van Hentenryck, P.: A Gentle Introduction to Numerica. Artificial Intelligence 103(1-2), 209–235 (1998)
Van Hentenryck, P., Laurent, M., Deville, Y.: Numerica, A Modeling Language for Global Optimization. MIT Press, Cambridge (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Janssen, M., Deville, Y., Van Hentenryck, P. (1999). Multistep Filtering Operators for Ordinary Differential Equations. In: Jaffar, J. (eds) Principles and Practice of Constraint Programming – CP’99. CP 1999. Lecture Notes in Computer Science, vol 1713. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-48085-3_18
Download citation
DOI: https://doi.org/10.1007/978-3-540-48085-3_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66626-4
Online ISBN: 978-3-540-48085-3
eBook Packages: Springer Book Archive