Module inari::_docs::intro [−][src]
Expand description
Introduction to Interval Arithmetic
This is an introduction to interval arithmetic (IA) provided by the crate. There are other variations on IA, which are not mentioned in this documentation. The variation here is called the set-based flavor in the IEEE 1788 standard.
Intervals
An interval is a set of the all real numbers within a range such as $-1 β€ x β€ 2, -1 β€ x$ and $x β€ 2$. The empty set ($β $) as well as the set of all real numbers ($\R$) are also treated as intervals. Here is a summary of the notations and definitions of intervals:
Interval Notation | Definition | Bounded | Notes |
---|---|---|---|
$β $ | $β $ (the empty set) | Yes | |
$[a, b]$ | $\{x β \R β£ a β€ x β€ b\}$ | Yes | $a, b β \R, a β€ b$ |
$[a, +β]$ | $\{x β \R β£ a β€ x\}$ | No | $a β \R$ |
$[-β, b]$ | $\{x β \R β£ x β€ b\}$ | No | $b β \R$ |
$\R$ or $[-β, +β]$ | $\R$ (the whole real line) | No |
To put the definitions of intervals into a simpler form, let us introduce the extended real numbers $\XR$:
$$ \XR = \R βͺ \{+β, -β\}, $$
which is a totally ordered set extending $\XR$ with the following ordering rules:
$$ βx β \R βͺ \{-β\} : x < +β,\qquad βx β \R βͺ \{+β\} : -β < x. $$
Now we can define any nonempty interval $[a, b]$ as $\{x β \R β£ a β€ x β€ b\}$, where $a, b β \XR β§ a β€ b β§ a < +β β§ b > -β$. $a$ is called the lower bound and $b$ is called the upper bound of the interval. Fundamentally, the lower and upper bounds of an interval $π$ are defined as $\inf π$ and $\sup π$ (the infimum and the supremum of $π$ in $\XR$), respectively. Therefore, the lower (resp. upper) bound of $β $ is $+β$ (resp. $-β$).
Note that while the bounds of an interval are members of $\XR$, the interval itself is a subset of $\R$. Therefore, neither $-β$ nor $+β$ can be a member of an interval.
We denote by $\IR$ the set of all intervals:
$$ \IR = \{β \} βͺ \{[a, b] β£ a, b β \XR β§ a β€ b β§ a < +β β§ b > -β\}. $$
An interval is denoted by a bold letter such as $π$ or $π$. Furthermore, an $n$-tuple of intervals $(π_1, β¦, π_n) β \IR^n$ is also denoted by $π$.
Every interval is a closed subset of $\R$.
Interval Extensions of Functions
Let $n β \N = \{0, 1, 2, β¦\}$ and $X β \R^n$. Let $f : X β \R$ be a real-valued function. A function $π : \IR^n β \IR$ is said to be an interval extension of $f$ if and only if:
$$ βπ β \IR^n : π(π) β f[π], $$
where $f[π] = \{f(x) β£ x β π β© X\}$ is the image of $π$ under $f$.
The natural interval extension of $f$ is the interval extension that maps an interval $π$ to the tightest interval that encloses $f[π]$:
$$ \begin{align} π(π) &= \operatorname{min}_β\{π β \IR β£ π β f[π]\} \\ &= \begin{cases} β & \if f[π] = β , \\ [\inf f[π], \sup f[π]] & \otherwise. \end{cases} \end{align} $$
Let $n > 0$. Let $π$ be the natural interval extension of $f$. The following holds:
$$ βπ β \IR^n : ((βi β \{1, β¦, n\} : π_i = β ) βΉ π(π) = β ). $$
Examples
Here are some examples of the natural interval extension. The cases where any of the arguments is $β $ are omitted. In the examples, we also define arithmetic operations on extended real numbers involving $Β±β$.
-
$\surd : [0, β] β β$ is extended as
$$ \sqrt{[a, b]} = \begin{cases} β & \if b < 0, \\ [0, \sqrt{b}] & \if a β€ 0 β€ b, \\ [\sqrt{a}, \sqrt{b}] & \otherwise, \end{cases} $$
where $\sqrt{+β} = +β$.
-
Addition and subtraction ($+, - : β Γ β β β$) are extended as
$$ \begin{align} [a, b] + [c, d] &= [a + c, b + d], \\ [a, b] - [c, d] &= [a - d, b - c], \end{align} $$
where
$$ \begin{gathered} βx β \R βͺ \{+β\} : x + (+β) = +β + x = +β, \\ βx β \R βͺ \{-β\} : x + (-β) = -β + x = -β, \\ -(Β±β) = ββ. \end{gathered} $$
-
Multiplication ($Γ : β Γ β β β$) is extended as
$[a, b] Γ [c, d] =$
$d β€ 0$ $c < 0 < d$ $0 β€ c$ $b β€ 0$ $[bd, ac]$ $[ad, ac]$ $[ad, bc]$ $a < 0 < b$ $[bc, ac]$ $[\min\{ad, bc\}, \max\{ac, bd\}]$ $[ad, bd]$ $0 β€ a$ $[bc, ad]$ $[bc, bd]$ $[ac, bd]$ where
$$ βx β \XR{β}\{0\} : x Γ (Β±β) = Β±β Γ x = \begin{cases} Β±β & \if x > 0, \\ ββ & \if x < 0. \end{cases} $$
-
Division ($/ : β Γ β{β}\{0\} β β$) is extended as
$[a, b]/[c, d] =$
$d < 0$ $c < 0 β§ d = 0$ $c = d = 0$ $c < 0 < d$ $c = 0 β§ 0 < d$ $0 < c$ $b β€ 0$ $[b/c, a/d]$ $[b/c, +β]$ $β $ $\R$ $[-β, b/d]$ $[a/c, b/d]$ $a = 0 = b$ $[0, 0]$ $[0, 0]$ $β $ $[0, 0]$ $[0, 0]$ $[0, 0]$ $a < 0 < b$ $[b/d, a/d]$ $\R$ $β $ $\R$ $\R$ $[a/c, b/c]$ $0 β€ a$ $[b/d, a/c]$ $[-β, a/c]$ $β $ $\R$ $[a/d, +β]$ $[a/d, b/c]$ where
$$ \begin{gathered} βx β \R : x/(Β±β) = 0, \\ βx β \R{β}\{0\} : Β±β/x = \begin{cases} Β±β & \if x > 0, \\ ββ & \if x < 0. \end{cases} \end{gathered} $$
-
Let $c β \R$. Let $f : \R^0 β \R$ be a function that maps $β $ to $c$ (note that $S^0 = \{β \}$ for any set $S$). The natural interval extension of $f$ is a function $π : \IR^0 β \IR$ that maps $β $ to $[c, c]$.
For this reason, we define the natural interval extension of an real constant $c$ as $[c, c]$.
$\IF$-Interval Extensions of Functions
Floating-point arithmetic (FA) is an approximation of the extended real numbers designed to be efficiently implemented at hardware level. The crate provides an efficient implementation of IA by using f64
numbers to represent and compute with intervals. See the IEEE 754 standards for the details of FA.
We denote by $\F β \XR$ the set of all normal and subnormal f64
numbers, zero, $+β$ and $-β$.
Let $\RD$ and $\RU : \XR β \F$ be the functions that maps an extended real number $x$ to the greatest $\F$ number $β€ x$ and the least $\F$ number $β₯ x$ respectively:
$$ \begin{align} \RD x &= \max\{y β \F β£ y β€ x\}, \\ \RU x &= \min\{y β \F β£ x β€ y\}, \end{align} $$
and $\RDU : \IR β \IF$ be the function that maps an interval $π$ to the tightest $\IF$ interval that encloses $π$:
$$ \begin{align} \RDU π &= \operatorname{min}_β\{π β \IF β£ π β π\} \\ &= \begin{cases} β & \if π = β , \\ [\RD a, \RU b] & \otherwise, π = [a, b]. \end{cases} \end{align} $$
Let $\nextDown$ and $\nextUp : \F β \F$ be the functions defined as follows:
$$ \begin{align} \nextDown(x) &= \begin{cases} -β & \if x = -β, \\ \max\{y β \F β£ y < x\} & \otherwise, \end{cases} \\ \nextUp(x) &= \begin{cases} +β & \if x = +β, \\ \min\{y β \F β£ x < y\} & \otherwise, \end{cases} \end{align} $$
and $\nextOut : \IF β \IF$ be the function defined as follows:
$$ \nextOut(π) = \begin{cases} β & \if π = β , \\ [\nextDown(a), \nextUp(b)] & \otherwise, π = [a, b]. \end{cases} $$
We denote by $\IF β \IR$ the set of intervals whose bounds are $\F$ numbers:
$$ \IF = \{β \} βͺ \{[a, b] β£ a, b β \F β§ a β€ b β§ a < +β β§ b > -β\}. $$
Let $n β \N$ and $X β \R^n$. Let $f : X β β$ be a real-valued function. A function $π_\IF : \IF^n β \IF$ is said to be an $\IF$-interval extension of $f$ if and only if:
$$ βπ β \IF^n : π_\IF(π) β f[π]. $$
Let $π_\IF$ be an $\IF$-interval extension of $f$. Then $π_\IF$ is also an interval extension of $f$. The tightness of $π_\IF$ is said to be tightest if and only if its values are the tightest $\IF$ intervals:
$$ π_\IF(π) = \RDU π(π), $$
where $π : \IR β \IR$ is the natural interval extension of $f$. The tightness of $π_\IF$ is said to be accurate if and only if its values are slightly wider than in the tightest case:
$$ π_\IF(π) β \nextOut(\RDU π(\nextOut(π))). $$
The tightness of $π_\IF$ is said to be valid if and only if:
$$ π_\IF(π) β π(π), $$
which is always true.
For example, the tightest $\IF$-interval extension of $Ο = 3.14159265358979323β¦$ is
$$ π_\IF β [3.14159265358979311, 3.14159265358979357]. $$
Note that $β$ is used instead of $=$ because $\F$ numbers are often too long to be written in decimal.
The Decoration System
The decoration system gives us some additional information on the underlying function of an interval extension being evaluated, such as whether it is defined or continuous on the input interval.
We denote by $\D$ the set of decorations:
$$ \D = \{\com, \dac, \def, \trv, \ill\}. $$
They are abbreviations of common, defined and continuous, defined, trivial and ill-formed, respectively. $\D$ is a totally ordered set with the following ordering rules:
$$ \com > \dac > \def > \trv > \ill. $$
Let $n β \N$ and $X β \R^n$. Let $f : X β \R$ be a real-valued function. Let $π β \XR^n, π β \XR$. We define the following predicates:
$$ \begin{align} p_\com(f, π, π) &:βΊ β β π β X β§ (f \text{ is continuous on } π) β§ (\text{$π$ and $π$ are bounded}), \\ p_\dac(f, π, π) &:βΊ β β π β X β§ (f{βΎ_π} \text{ is continuous}), \\ p_\def(f, π, π) &:βΊ β β π β X, \\ p_\trv(f, π, π) &:βΊ (\text{always true}), \\ p_\ill(f, π, π) &:βΊ X = β , \end{align} $$
where $f{βΎ_π}$ is the restriction of $f$ to $π$. The following implications hold:
$$ \begin{align} p_\com(f, π, π) βΉ p_\dac(f, π, π) &βΉ p_\def(f, π, π) βΉ p_\trv(f, π, π), \\ p_\ill(f, π, π) &βΉ p_\trv(f, π, π). \end{align} $$
Let $π β \IR, d β \D$. A decorated interval is a pair $(π, d)$ of the following combinations:
Interval $π$ | Decoration $d$ |
---|---|
Nonempty and bounded | $\com, \dac, \def$ or $\trv$ |
Unbounded | $\dac, \def$ or $\trv$ |
Empty | $\trv$ |
Any | $\ill$ |
We denote by $\DIR$ the set of all decorated intervals.
-
(Advanced) Fundamentally, a pair $(π, dy)$ is said to be a decorated interval (member of $\DIR$) if and only if:
$$ βn β \N, X β \R^n, f β \R^X, π β \IR^n : (π β f[π] β§ p_{dy}(f, π, π)). $$
Let $f : β β \R$ be the empty function. By substituting $n = 0, X = β , f$ and $π = β $ into the above statement, one can show that for any $π β \IR$, $(π, \ill)$ is a decorated interval.
A decorated interval $(π, d) β \DIR$ is also written as $π_d$, thus $[1, 2]_\com = ([1, 2], \com)$, for example. We also write an $n$-tuple of decorated intervals $({π_1}_{d_1}, β¦, {π_n}_{d_n}) β \DIR^n$ as $π_d$.
A function $π : \DIR^n β \DIR$ is said to be a decorated interval extension of $f$ if and only if:
$$ βπ_{dx} β \DIR^n : (π β f[π] β§ βd β \D : (p_d(f, π, π) β§ dy = \min\{d, dx_1, β¦, dx_n\})), $$
where $π = (π_1, β¦, π_n)$ and $π_{dy} = π(π_{dx})$.
Let $n > 0$. Let $π$ be a decorated interval extension of $f$. The following holds:
$$ βπ_{dx} β \DIR^n : ((βi β \{1, β¦, n\} : dx_i = \ill) βΉ dy = \ill), $$
where $π_{dy} = π(π_{dx})$.
Any interval decorated with $\ill$ is called NaI (Not an Interval). NaI is produced by an invalid construction of a (decorated) interval, and it is propagated through calculations.
In all functions in the crate, unless otherwise mentioned, $d$ in the above statement is chosen to be the strongest decoration for $(f, π, π)$:
$$ d = \begin{cases} \com & \if p_\com(f, π, π), \\ \dac & \if p_\dac(f, π, π) β§ Β¬p_\com(f, π, π), \\ \def & \if p_\def(f, π, π) β§ Β¬p_\dac(f, π, π), \\ \ill & \if p_\ill(f, π, π), \\ \trv & \otherwise. \end{cases} $$
Examples
-
Let $β{β }β : \DIR β \DIR$ be the decorated (natural) interval extension of the floor function $β{β }β : \R β \R$.
$$ β[-1/2, 1/2]_\comβ = [-1, 0]_\def. $$
In this case, the result is decorated with $\def$ because the floor function is discontinuous at $0$.
$$ β[0, 1/2]_\comβ = [0, 0]_\dac. $$
In this case, the result is decorated with $\dac$ bacause the restriction of the floor function to $[0, 1/2]$ is continuous, by the definition of the subspace topology.
Notation
Some of the symbols used in this document is different from the standard. Here are the differences between them:
This Document | IEEE 1788 Standard |
---|---|
$\IR$ | $\overline{πβ}$ |
$\DIR$ | $\overline{π»πβ}$ |
$\F$ | $\operatorname{Val}(π½)$ |
$\IF$ | $π$ |
$\DIF$ | $π»π$ |
$f[π]$ | $\operatorname{Rge}(f|π)$ |
$p_d(f,π,π)$ | $p_d(f|π)$ |
The strongest decoration for $(f, π, π)$ | $\operatorname{Dec}(f|π)$ |