= Interval subdivision
{title2=$f(X)\subseteq\bigcup_j F(X_j)$}
<Interval subdivision> covers $X$ by smaller <closed intervals> $X_j$, computes a valid <interval enclosure> $F(X_j)$ on each, and takes their <union>. Every allowed input belongs to a piece, so its output belongs to that <union>. If one <closed interval> is wanted, take the smallest one containing the <union>; gaps between separate output pieces can then be lost. Splitting narrows the freedom given to repeated inputs, while increasing the number of evaluations.
For $f(x)=x(1-x)$, split $[0,1]$ at $1/2$. The <natural interval extensions> are
$$
\begin{aligned}
F([0,1/2])&=[0,1/2][1/2,1]=[0,1/2],\\
F([1/2,1])&=[1/2,1][0,1/2]=[0,1/2].
\end{aligned}
$$
Their <union> is $[0,1/2]$. Four equal pieces sharpen the upper bound again:
$$
\begin{array}{c|c|c}
X_j&[1,1]-X_j&F(X_j)\\\hline
[0,1/4]&[3/4,1]&[0,1/4]\\
[1/4,1/2]&[1/2,3/4]&[1/8,3/8]\\
[1/2,3/4]&[1/4,1/2]&[1/8,3/8]\\
[3/4,1]&[0,1/4]&[0,1/4]
\end{array}
$$
The <union> is now $[0,3/8]=[0,0.375]$, still wider than the actual <image of a function> $[0,1/4]$. These are exact <rational number> bounds: the excess width comes from the <interval dependency problem>, rather than <roundoff error>.
Back to article page
