Taylor Tube Method for Validated IVP

Bingwei Zhang, Chee Yap · 2026

Read Taylor Tube Method for Validated IVP by Bingwei Zhang, Chee Yap (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-19068.txt.

Introduction

Zhang and Yap generalize the Euler Tube technique for validated initial value problems to Taylor Tubes of any degree at least one. Higher degree tubes improve accuracy and, surprisingly, can also speed up the solver overall when combined with bisection. The Euler Tube refines end and full enclosures and underpins the complexity bound of their complete validated solver.

Catalog record

CREATORBingwei Zhang, Chee Yap
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE32866
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.19068

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Taylor Tube Method for Validated IVP Thanks: This document contains the results of the research funded by NSF Grant #CCF-2212462. A paper by the same title will appear in the Proceeding of the International Congress on Mathematical Software (ICMS) 2026. This arxiv version has all the proofs in an appendix. Bingwei Zhang, Chee Yap Abstract We recently introduced a novel architecture for the design of validated IVP algorithms. This architecture forms the basis of our complete validated algorithm for IVP. A key subroutine in our algorithm is the Euler Tube : it gave a technique for refining end- and full-enclosures and is also key to deriving a complexity bound of our IVP solver. In this paper, we generalize it to Taylor Tube of degree p ≥ 1 p\geq 1 . As expected, higher-degree Taylor Tubes improve accuracy. But surprisingly, our experiments show that it can also lead to an overall speedup when combined with bisection. 1 Introduction Consider the initial value problem (IVP) for an autonomous ODE of the form {\bm{x}}^{\prime}={\bm{f}}({\bm{x}}). (1) where {\bm{f}}:{\mathbb{R}}^{n}\to{\mathbb{R}}^{n} is C^{k} -continuous (for some global constant k\geq 1 ). For B_{0}\subseteq{\mathbb{R}}^{n} ( n\geq 1 ) and h>0 , let \mbox{{{{IVP}}}}_{\bm{f}}(B_{0},h) denote the set of solutions {\bm{x}}:[0,h]\to{\mathbb{R}}^{n} that satisfies ( 1 ) and {\bm{x}}(0)\in B_{0} . We say (B_{0},h) is valid (or {\bm{f}} -valid) if for each {\bm{p}}_{0}\in B_{0} , some {\bm{x}}\in\mbox{{{{IVP}}}}_{\bm{f}}(B_{0},h) with {\bm{x}}(0)={\bm{p}}_{0} has unique-existence. 1 1 1 i.e., it exists, and it is unique. For a valid (B_{0},h) , let \begin{array}[]{rcl}\mbox{End}_{\bm{f}}(B_{0},h)&{\color[rgb]{1,0,0}\mathrel{\,:=\,}}&\left\{{\bm{x}}(h):{\bm{x}}\in\mbox{{{{IVP}}}}_{\bm{f}}(B_{0},h)\right\},\\ \mbox{Image}_{\bm{f}}(B_{0},h)&{\color[rgb]{1,0,0}\mathrel{\,:=\,}}&\left\{{\bm{x}}(t):{\bm{x}}\in\mbox{{{{IVP}}}}_{\bm{f}}(B_{0},h),t\in[0,h]\right\}.\end{array} (2) We fix {\bm{f}} in this paper; so the subscript {\bm{f}} may be omitted above. By an end-closure and a full-enclosure for (B_{0},h) we mean any sets E and F that contain \mbox{End}(B_{0},h) and \mbox{Image}(B_{0},h) , respectively. Two central problems in the applications of IVP are to compute such end- and full-enclosures. These are often called reachability problems in control theory. The literature on validated algorithms for IVP has a history of over 50 years going back to Moore, and are of course based on interval methods. See the surveys of Corliss [ 2 ] and Nedialkov et al. [ 5 ] ). We formulate the following reachability problem, called the End Cover Problem : Given ({\bm{f}},B_{0},h,\varepsilon) ( \varepsilon>0 ) where B_{0} is a box, to compute a finite set of boxes {\mathcal{C}}=\left\{B_{1},\ldots,B_{m}\right\} such that \mbox{End}_{\bm{f}}(B_{0},h)~\subseteq~\bigcup{\mathcal{C}}~\subseteq~\mbox{End}_{\bm{f}}(B_{0},h)\oplus[-\varepsilon,\varepsilon]^{n} (3) where \bigcup{\mathcal{C}}=\cup_{i=1}^{m}B_{i} and A\oplus B denotes the Minkowski sum of Euclidean sets A,B\subseteq{\mathbb{R}}^{n} . Any {\mathcal{C}} that satisfies ( 3 ) is called an \varepsilon -cover of \mbox{End}_{\bm{f}}(B_{0},h) . Recently, we introduced an algorithm [ 9 , 10 ] for this End Cover Problem. It represented the first complete validated IVP algorithm. By “complete” we mean that our algorithm is a halting algorithm. Most validated algorithms are only partially correct 2 2 2 This is a standard terminology in theoretical computer science. in the sense that, the output is correct if it halts . Halting is especially challenging in IVP problems, partly because the error typically grows exponentially with time. We note some features in our solution: (1) We guarantee that the “over-approximation” of {\mathcal{C}} is within any user-specified \varepsilon bound. To our knowledge, no current solver promises such bounds. (2) Our algorithm is fully automatic; it does not require hyper-parameters , such as a minimum step size or tolerance bounds, which are commonly used in such algorithms. (3) In preliminary implementations, our algorithm has proved to be practical. It is reasonable to expect that the algorithm takes a performance hit in order to ensure completeness. But surprisingly, it often performs better than the incomplete algorithms. Our previous papers [ 9 , 10 ] introduced a novel architecture for IVP algorithms based on the scaffold framework. Within this framework, many of our original subroutines could be swapped. One of these subroutines is called Euler tube . In this paper, we generalize it into Taylor tube , based on using the first p\geq 1 terms of a Taylor expansion. The case p=1 corresponds to Euler tube. Our experiments show that a higher degree for p leads to tighter enclosures (not a surprise) but surprisingly, they can also lead to overall speedup. We remark that such tube techniques were critical for our ability to prove complexity bounds for our halting algorithm. 2 Taylor Tube Most of the following notations are taken from [ 9 , 10 ] . For a square matrix A\in{\mathbb{R}}^{n\times n} and the induced matrix p -norm, the logarithmic p -norm is \mu_{p}(A){\color[rgb]{1,0,0}\mathrel{\,:=\,}}\lim_{h\to 0+}\frac{\|I+hA\|_{p}-1}{h}. We focus on p=2 and write \mu(A) as the logNorm. For any B\subseteq{\mathbb{R}}^{n} , define \mu(J_{\bm{f}}(B)){\color[rgb]{1,0,0}\mathrel{\,:=\,}}\sup\left\{\mu(J_{\bm{f}}({\bm{p}})):{\bm{p}}\in B\right\}. Call {\overline{\mu}} a logNorm-bound on B if {\overline{\mu}}\geq\mu(J_{\bm{f}}(B)) . Unlike classical norms, logarithmic norms can be negative. We have this basic result: Lemma 1 Let {\bm{x}}_{1},{\bm{x}}_{2}\in\mbox{{{{IVP}}}}(Ball_{{\bm{p}}_{0}}(r),h,F) and assume {\overline{\mu}}\geq\mu_{2}(J_{\bm{f}}(F)) . For all t\in[0,h] , \|{\bm{x}}_{1}(t)-{\bm{x}}_{2}(t)\|_{2}\leq\|{\bm{x}}_{1}(0)-{\bm{x}}_{2}(0)\|e^{{\overline{\mu}}t}. (4) This lemma is just a special case of logNorm version of the Fundamental IVP Inequality ( [ 7 , 3 ] ). Tubular region of a trajectory. Fix a trajectory {\bm{x}}=\mbox{{{{IVP}}}}({\bm{q}}_{0},h) . For any \delta>0 , the \delta -tube of {\bm{x}} is the set \mbox{Tube}_{\delta}({\bm{x}}){\color[rgb]{1,0,0}\mathrel{\,:=\,}}\left\{(t,{\bm{p}}):0\leq t\leq h,\ \|{\bm{p}}-{\bm{x}}(t)\|_{2}\leq\delta\right\}\quad(\subseteq[0,h]\times{\mathbb{R}}^{n}). An arbitrary curve C:[0,\infty)\to{\mathbb{R}}^{n} lies in the \delta -tube of {\bm{x}} if (t,C(t))\in\mbox{Tube}_{\delta}({\bm{x}}) for all t\in[0,h] . For p\geq 1 , the Taylor polynomial of {\bm{f}} of degree p at any {\bm{q}}\in{\mathbb{R}}^{n} is defined to be T^{p}_{{\bm{q}}}(t){\color[rgb]{1,0,0}\mathrel{\,:=\,}}\sum_{i=0}^{p}t^{i}{\bm{f}}^{[i]}({\bm{q}})) (5) where 3 3 3 We may call this the normalized i -th Taylor differential coefficient of {\bm{f}} , where “differential” here emphasizes that it is not the usual coefficient of polynomial. {\bm{f}}^{[i]}({\bm{x}}){\color[rgb]{1,0,0}\mathrel{\,:=\,}}\left\{\begin{array}[]{lllllllllllllllllllllllll}{\bm{x}}&\mbox{{\ if}}\ i=0,\\ \tfrac{1}{i}\left(J_{{\bm{f}}_{[i-1]}}\bullet{\bm{f}}\right)({\bm{x}})&\mbox{\rm\ else}\end{array}\right. where J_{\bm{g}} denotes the Jacobian of {\bm{g}} and \bullet is matrix-vector product. The Taylor sequence of {\bm{q}}_{0} with step size {\overline{h}}>0 is the infinite sequence of points {\bm{q}}_{0},{\bm{q}}_{1},{\bm{q}}_{2}\ldots where {\bm{q}}_{i+1}{\color[rgb]{1,0,0}\mathrel{\,:=\,}}T^{p}_{{\bm{q}}_{i}}({\overline{h}}) for all i\geq 0 . This sequence defines the piece-wise continuous Taylor curve where T^{p}_{{\bm{q}}_{0},{\overline{h}}}(t){\color[rgb]{1,0,0}\mathrel{\,:=\,}}T^{p}_{{\bm{q}}_{i}}(t-i{\overline{h}}),\qquad(t\geq 0,i=\left\lfloor{t/{\overline{h}}}\right\rfloor). (6) We could similarly define the \delta -tube of the Taylor curve T^{p}_{{\bm{q}}_{0},{\overline{h}}}(t) and ask: does it contain the trajectory {\bm{x}} ? Our next lemma gives an affirmative answer provided the step size {\overline{h}} is less than an explicit bound. Using Lemma 1 , we obtain: Lemma 2 (Taylor Tube Step Size Bound) Let {\bm{x}}=\mbox{{{{IVP}}}}({\bm{q}}_{0},h) and B_{1} be a full enclosure of ({\bm{q}}_{0},h) . Assume that {\overline{\mu}} is a logNorm-bound on B_{1} and {\overline{M}}\geq\|{\bm{f}}^{[p+1]}(B_{1})\| . For any \delta>0 , if {\overline{h}} satisfies {\overline{h}}\leq h^{\text{taylor}}_{p}(h,{\overline{M}},\overline{\mu},\delta){\color[rgb]{1,0,0}\mathrel{\,:=\,}}\begin{cases}\displaystyle\Big(\dfrac{{\overline{\mu}}\,\delta}{{\overline{M}}\,(e^{\overline{\mu}h}-1)}\Big)^{\!1/p}&\text{if }\overline{\mu}>0,\\[10.0pt] \displaystyle\Big(\dfrac{\delta}{{\overline{M}}h}\Big)^{\!1/p}&\text{if }\overline{\mu}=0,\\[10.0pt] \displaystyle\min\!\left\{\left(\frac{{\overline{\mu}}\delta}{2{\overline{M}}\,(e^{{\overline{\mu}}h}-1)}\right)^{1/p},\,-\frac{1}{{\overline{\mu}}}\right\},&\text{if }\overline{\mu}<0,\end{cases} (7) and if \mbox{Image}({\bm{q}}_{i},{\overline{h}})\subseteq B_{1} (for all i=0,\ldots,\left\lfloor{h/{\overline{h}}}\right\rfloor ) then the \delta -tube of {\bm{x}} contains the Taylor curve T^{p}_{{\bm{q}}_{0},{\overline{h}}}(t) of step size {\overline{h}} . 3 Overview of the End-Cover Algorithm Most validated IVP algorithms are based on two key subroutines which we call 4 4 4 The StepA in [ 9 ] , has two extra arguments h,\varepsilon\geq 0 , which is defaulted to h=\infty,\varepsilon=0 here. StepA and StepB . Given a box E_{0} , we may call StepA / StepB in sequence to transform E_{0} into the following triple and then quad: E_{0}\stackrel{{\scriptstyle{\mbox{\tt StepA}}}}{{\relbar\joinrel\relbar\joinrel\relbar\joinrel\relbar\joinrel\rightarrow}}(E_{0},h,F_{1})\stackrel{{\scriptstyle{\mbox{\tt StepB}}}}{{\relbar\joinrel\relbar\joinrel\relbar\joinrel\relbar\joinrel\rightarrow}}(E_{0},h,F_{1},E_{1}). (8) In general, for i\geq 1 , we transform E_{i-1}\stackrel{{\scriptstyle}}{{\longrightarrow}}(E_{i-1},h_{i},F_{i},E_{i}) . These triples and quads are said to be admissible and have the property that F_{i} and E_{i} are full- and end-enclosures for (E_{i-1},h_{i}) . Note that E_{m} ( m\geq 1 ) is an end-enclosure for (E_{0},t_{m}) where t_{m}=\sum_{i=1}^{m}h_{i} . Next, we introduce

Read the complete text