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, \varepsilon, 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.
Categories: cs.DS cs.CC