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

We consider the first-order autonomous ordinary differential equation $${\mathbf{x}}^{\mathrm{\prime }}=\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{I}\mathrm{V}\mathrm{P}}_{\mathbf{f}}(B_0,h)$ the set of solutions $\mathbf{x}:[0,h]\to {\mathbb{R}}^n$ satisfying $${\mathbf{x}}^{\mathrm{\prime }}(t)=\mathbf{f}(\mathbf{x}(t)),\mathbf{x}(0)\in B_0\mathrm{.}$$ 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{E}\mathrm{n}\mathrm{d}}_{\mathbf{f}}(B_0,h)\subseteq \bigcup _{B\in \mathcal{C}}B\subseteq {\mathrm{E}\mathrm{n}\mathrm{d}}_{\mathbf{f}}(B_0,h)\oplus [-\epsilon ,\epsilon {]}^n,$$ where $${\mathrm{E}\mathrm{n}\mathrm{d}}_{\mathbf{f}}(B_0,h)=\{\mathbf{x}(h):\mathbf{x}\in {\mathrm{I}\mathrm{V}\mathrm{P}}_{\mathbf{f}}(B_0,h)\}\mathrm{.}$$ 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{E}\mathrm{n}\mathrm{d}}_{\mathbf{f}}(B_0,h)$. Finally, we present experimental results demonstrating the practicality of our approach.