End Cover for Initial Value Problem: Complete Validated Algorithms with Complexity Analysis

Abstract

We consider the first-order autonomous ordinary differential equation \[ \mathbf{x}' = \mathbf{f}(\mathbf{x}), \] where $\mathbf{f}:{\mathbb{R}}^n\to {\mathbb{R}}^n$ is locally Lipschitz. For a box $B_0\subseteq {\mathbb{R}}^n$ and $h>0$, we denote by ${\mathrm{IVP}}_{\mathbf{f}}(B_0,h)$ the set of solutions $\mathbf{x}:[0,h]\to {\mathbb{R}}^n$ satisfying \[ \mathbf{x}'(t) = \mathbf{f}(\mathbf{x}(t)), \qquad \mathbf{x}(0) \in B_0 . \] We present a complete validated algorithm for the following \emph{End Cover Problem}: given $(\mathbf{f},B_0,\epsilon ,h)$, compute a finite set $\mathcal{C}$ of boxes such that \[ \mathrm{End}_{\mathbf{f}}(B_0,h) \;\subseteq\; \bigcup_{B \in \mathcal{C}} B \;\subseteq\; \mathrm{End}_{\mathbf{f}}(B_0,h) \oplus [-\varepsilon,\varepsilon]^n , \] where \[ \mathrm{End}_{\mathbf{f}}(B_0,h) = \left\{ \mathbf{x}(h) : \mathbf{x} \in \mathrm{IVP}_{\mathbf{f}}(B_0,h) \right\}. \] Moreover, we provide a complexity analysis of our algorithm and introduce a novel technique for computing the end cover $\mathcal{C}$ based on covering the boundary of ${\mathrm{End}}_{\mathbf{f}}(B_0,h)$. Finally, we present experimental results demonstrating the practicality of our approach.