Abstract
We present a domain-theoretic version of Picard’s theorem for solving classical initial value problems in ℝn. For the case of vector fields that satisfy a Lipschitz condition, we construct an iterative algorithm that gives two sequences of piecewise linear maps with rational coefficients, which converge, respectively from below and above, exponentially fast to the unique solution of the initial value problem. We provide a detailed analysis of the speed of convergence and the complexity of computing the iterates. The algorithm uses proper data types based on rational arithmetic, where no rounding of real numbers is required. Thus, we obtain an implementation framework to solve initial value problems, which is sound and, in contrast to techniques based on interval analysis, also complete: the unique solution can be actually computed within any degree of required accuracy.
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
AWA. A software package for validated solution of ordinary differential equations, http://www.cs.utep.edu/interval-comp/intsoft.html
The GNU multi precision library, http://www.swox.com/gmp/
Aberth, O.: Computable analysis and differential equations. In: Intuitionism and Proof Theory. Studies in Logic and the Foundations of Mathematics, pp. 47–52. North-Holland, Amsterdam (1970); Proc. of the Summer Conf. at Buffalo N.Y. (1968)
Abramsky, S., Jung, A.: In: Abramsky, S., Gabbay, D.M., Maibaum, T.S.E. (eds.) Handbook of Logic in Computer Science, vol. 3, Clarendon Press, Oxford (1994)
Aubin, J.P., Cellina, A.: Differential Inclusions. Springer, Heidelberg (1984)
Brattka, V.: Computability of Banach space principles. Informatik Berichte 286, FernUniversität Hagen, Fachbereich Informatik (June 2001)
Clarke, F.H., Ledyaev, Y.S., Stern, R.J., Wolenski, P.R.: Nonsmooth Analysis and Control Theory. Springer, Heidelberg (1998)
Cleave, J.P.: The primitive recursive analysis of ordinary differential equations and the complexity of their solutions. Journal of Computer and Systems Sciences 3, 447–455 (1969)
Coddington, E.A., Levinson, N.: Theory of Ordinary Differential Equations. McGraw-Hill, New York (1955)
Edalat, A., Krznarić, M., Lieutier, A.: Domain-theoretic solution of differential equations (scalar fields). In: Proceedings of MFPS XIX. of Elect. Notes in Theoret. Comput. Sci., vol. 83 (2004), Full Paper in www.doc.ic.ac.uk/~ae/papers/scalar.ps
Edalat, A., Lieutier, A.: Domain theory and differential calculus (Functions of one variable). In: Seventh Annual IEEE Symposium on Logic in Computer Science, IEEE Computer Society Press, Los Alamitos (2002), Full paper in www.doc.ic.ac.uk/~ae/papers/diffcal.ps
Grzegorczyk, A.: Computable functionals. Fund. Math. 42, 168–202 (1955)
Iserles, A.: Numerical Analysis of Differential Equations. Cambridge Texts in Applied Mathematics. CUP (1996)
Ko, K.-I.: On the computational complexity of ordinary differential equations. Inform. Contr. 58, 157–194 (1983)
Kolmogorov, A.N., Fomin, S.V.: Introductory Real Analysis. Dover, New York (1975)
Moore, R.E.: Interval Analysis. Prentice-Hall, Englewood Cliffs (1966)
Müller, N.T., Moiske, B.: Solving initial value problems in polynomial time. In: Proceedings of the 22th JAIIO - Panel 1993, Buenos Aires, pp. 283–293 (1993)
Nedialkov, N.S., Jackson, K.R., Corliss, G.F.: Validated solutions of initial value problems for ordinary differential equations. Applied Mathematics and Computation 105, 21–68 (1999)
Pour-El, M.B., Richards, J.I.: Computability in Analysis and Physics. Springer, Heidelberg (1988)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Edalat, A., Pattinson, D. (2004). A Domain Theoretic Account of Picard’s Theorem. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds) Automata, Languages and Programming. ICALP 2004. Lecture Notes in Computer Science, vol 3142. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-27836-8_43
Download citation
DOI: https://doi.org/10.1007/978-3-540-27836-8_43
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22849-3
Online ISBN: 978-3-540-27836-8
eBook Packages: Springer Book Archive