Reducing the truncation error in Taylor model multiplication

Abstract

We present two new methods, a simple fast and a slower more precise one, to reduce the truncation error occurring during multiplication in verified Taylor model arithmetic. These methods were implemented in MATLAB in INTLAB’s Taylor model toolbox which targets solving ordinary differential equations rigorously, i.e., numerical solutions are computed along with rigorous error bounds that include all numerical as well as all rounding errors so that the exact solution must lie within these error bounds. The methods are applied to several test cases to show their effect.

Appendix

1.1 Proof of Lemma 1

i) For $c\in [0,1]$ and $q \in [0,1)$ we have $c^{\frac{1}{1-q}}, q^{\frac{1}{1-q}} \in [0,1]$ so that

$$ \lim _{q\uparrow 1} \nu (c,q) = \lim _{q\uparrow 1} c^{\frac{1}{1-q}}(1-q)q^{\frac{q}{1-q}} = 0 = \nu (c,1). $$

Here, $\lim \limits _{q\uparrow 1}$ denotes the one-sided limit as q increases in value approaching 1 from below.

ii) By definition of $\mu$ it suffices to show that $\nu (c,\cdot )$ is monotonically decreasing. Clearly, the factor $c^{\frac{1}{1-q}}$ in (6) is monotonically decreasing w.r.t. $q\in [0,1)$. Thus, it suffices to show that $(1-q)q^{\frac{q}{1-q}}$ is decreasing w.r.t. $q\in [0,1)$. A computation gives

$$ \left( (1-q)q^{\frac{q}{1-q}}\right) ' = \frac{\ln (q)}{1-q} q^{\frac{q}{1-q}} < 0 \quad \text {for all} q\in (0,1). $$

By continuity, this proves the assertion.

iii) Abbreviate $f(c):=\nu (c,q)$ and $g(c):=1-c$. The functions f and g are continuous, f is monotonically increasing, g is strictly monotonically decreasing, $f(0) = 0 < 1 = g(0)$, and $f(1)\geqslant 0=g(1)$. Therefore, $\mu (c,q) = \max (f(c),g(c))$ becomes minimal if $f(c) = g(c)$, i.e., if $\kappa (c) = f(c) - g(c) = 0$. Since g is strictly decreasing, such a $c = c_q$ is unique. The remaining statements are evident.

iv) If $q=0$, then $|cx^q-x| = |c-x| \leqslant \max (c,1-c) = \mu (c,0)$ and this upper bound is attained for an $x\in \{0,1\}$. If $q=1$, then $|cx^q-x| = |(c-1)x|\leqslant 1-c =\mu (c,1)$ and this bound is attained for $x = 1$. If $c = 0$, then $|cx^q-x| = |x|\leqslant 1 = \mu (0,q)$ and this bound is attained for $x=1$. Thus, we can assume that $q\in (0,1)$ and $c\ne 0$. The absolute values of the local and global extrema of $f(x):=cx^q-x$, $x\in [0,1]$, build a superset of the local and global maxima of |f|. The derivative $f'(x) = cqx^{q-1}-1$ has the unique root $z:=(cq)^{\frac{1}{1-q}} \in [0,1]$. Since $f(z) = c^{\frac{1}{1-q}}(1-q)q^{\frac{q}{1-q}} = \nu (c,q)$, $f(0) = 0$, and $|f(1)|=1-c$, this proves

$$ |f(x)| \leqslant \max (|f(z)|,|f(1)|) = \max (\nu (c,q),1-c) = \mu (c,q) \quad \text {for all} x\in [0,1] $$

and this bound is attained for an $x\in \{z,1\}$. $\square$

1.2 Proof of Corollary 3

i) For $\gamma \in \{\alpha ,\beta \}$ set $Z_\gamma := \{ i\in \{1,\dots ,n\} ~|~ \gamma _i = 0 \}$. Then $\alpha \leqslant \beta$ implies $Z_\beta \subseteq Z_\alpha$. Thus, if $i \in Z_\beta$, then $x_i^{\alpha _i} = 1 = x_i^{\beta _i}$ for all $x\in [0,1]^n$ and these factors have trivial impact on $x^\alpha$ and $x^\beta$. Omitting them leads to the same problem in lower dimension. We may therefore assume that $Z_\beta = \emptyset$, i.e., $\beta \in \mathbb {N}^n$. If $Z_\alpha$ is nonempty and $i\in Z_\alpha$, then $\alpha _i = 0 <\beta _i$ gives $\alpha _i/\beta _i = 0 = q$. For $x\in [0,1]^n$ we have $x^\alpha ,x^{\beta -\alpha }\in [0,1]$ so that

$$ |cx^\alpha -x^\beta | = |c-x^{\beta -\alpha }|x^\alpha \leqslant |c - x^{\beta -\alpha }| \leqslant \max (c,1-c) = \mu (c,0). $$

Taking $y:=\textbf{1}$ and $z:=\textbf{1}-e_i$ we get $|cy^\alpha -y^\beta | = 1-c$ and $|cz^\alpha -z^\beta |=c$ which shows that the bound $\mu (c,0)$ is attained for an $x\in \{y,z\}$. This proves the assertion and we may therefore assume that $Z_\alpha = \emptyset$, i.e., $\alpha \in \mathbb {N}^n$. The absolute values of the local and global extrema of

$$ f:[0,1]^n\rightarrow \mathbb {R}, \quad x \mapsto cx^\alpha -x^\beta $$

build a superset of the local and global maxima of |f|. Since f has partial derivatives

$$ \frac{\partial f}{\partial x_i} (x) = (c\alpha _i-\beta _i x^{\beta -\alpha })x^{\alpha -e_i}, \quad i = 1.\dots ,n, $$

a critical point $z\in (0,1)^n$ of f must fulfill

$$ z^{\beta -\alpha } = \frac{\alpha _i}{\beta _i}c \quad \text {for all}\,\, i \in \{1,\dots ,n\}. $$

In particular, this requires $c\ne 0$ and means that f has no local extrema in $(0,1)^n$ if there are $i,j\in \{1,\dots , n\}$ with $\frac{\alpha _i}{\beta _i} \ne \frac{\alpha _j}{\beta _j}$. Hence, in this case, |f| assumes its local and global maxima on the boundary of $[0,1]^n$. Since $f(x)=0$ if $x_i = 0$ for some i, those maxima are attained at boundary points x having nonzero components and at least one component equal to one. Omitting these one-components reduces the problem to a lower dimension. Therefore, the general case reduces to the special one in which

$$\begin{aligned} \frac{\alpha _i}{\beta _i} \in (0,1) \quad \text {is independent of}\,\, i\in \{1,\dots ,n\} \end{aligned}$$

(16)

so that $\alpha = q \beta$. The mapping $[0,1]^n\rightarrow [0,1], \ x \mapsto x^\beta =:\tilde{x}$ is surjective. By Corollary 2 i) we have $|cx^\alpha -x^\beta | = |c\tilde{x}^q-\tilde{x}|\leqslant \mu (c,q)$ for all $x\in [0,1]^n$ and by surjectivity this upper bound is sharp. The special case (16) reveals the general one in which $q_i:=\alpha _i/\beta _i$ is not necessarily independent of i by building

$$ \max _{1 \leqslant i \leqslant n} \mu (c,q_i) = \mu (c,\underset{1 \leqslant i \leqslant n}{\min }q_i) = \mu (c,q) $$

since $\mu (c,\cdot )$ is monotonically decreasing by Lemma 1 ii). This proves i) and ii) follows by taking $c:=1$. $\square$