Covers for Initial Value Problem: Complete Validated Algorithms with Complexity Analysis

Abstract

We consider the first order autonomous differential equation (ODE) ${\mathbf{x}}^{\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$, the set of solutions $\mathbf{x}:[0,h]\to {\mathbb{R}}^n$ that satisfies ${\mathbf{x}}^{\prime }(t)=\mathbf{f}(\mathbf{x}(t))$ and $\mathbf{x}(0)\in B_0$ is denoted ${\mathrm{IVP}}_{\mathbf{f}}(B_0,h)$. We provide a complete validated algorithm for the following \emph{End Cover Problem}: given $(\mathbf{f},B_0,\epsilon ,h)$, to 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 [-\epsilon ,\epsilon {]}^n)$$ where ${\mathrm{End}}_{\mathbf{f}}(B_0,h)=\{\mathbf{x}(h):\mathbf{x}\in \mathrm{IVP}(B_0,h)\}$. We will also give a complexity analysis of our algorithm, and introduce an alternative technique to compute End Cover $\mathcal{C}$ based on covering the boundary of ${\mathrm{End}}_{\mathbf{f}}(B_0,h)$. We also introduce the \emph{Boundary Cover Problem} to compute a $\epsilon$-cover for the boundary of ${\mathrm{End}}_{\mathbf{f}}(B_0,h)$, leading to a faster algorithm the above End Cover Problem. Finally, we give experimental results indicating the practicality of our techniques.