Time Complexity and Convergence Analysis of Domain Theoretic Picard Method

Amin Farjudian and Michal Konečný, in Proceedings of Wollic'08, Edinburgh, pp149-163, Lecture Notes in Artificial Intelligence 5110, Springer-Verlag, 2008

Abstract

We present an implementation of the domain-theoretic Picard method for solving initial value problems (IVPs) introduced by Edalat and Pattinson in 2004. Compared to Edalat and Pattinson's implementation, our algorithm uses a more efficient arithmetic based on an arbitrary precision floating-point library. Despite the additional overestimations due to floating-point rounding, we obtain a similar bound on the convergence rate of the produced approximations. Moreover, our convergence analysis is detailed enough to allow a static optimisation in the growth of the precision used in successive Picard iterations. Such optimisation greatly improves the efficiency of the solving process. Although a similar optimisation could be performed dynamically without our analysis, a static one gives us a significant advantage: we are able to predict the time it will take the solver to obtain an approximation of a certain (arbitrarily high) quality.

BibTeX, pdf(a4)
Michal Konečný
Last modified: 7 August 2008