Affine Arithmetic

by Cassio • 2011/10/03 • Research

In my previous post, I talked about interval arithmetic, a simple and popular formalism for handling interval data. We saw how interval arithmetic’s simplicity has a downside, namely the error explosion that happens as a consequence of ignoring dependencies between variables.

Affine arithmetic was proposed as an alternative, and it explicitly accounts for dependencies between variables, because it represents intervals as affine forms. Here’s the generic form for an interval $\hat{x}$ , corresponding to some quantity x:

$\hat{x} = x_0 + x_1 \epsilon_1 + \ldots + x_n\epsilon_n$

As we see, the affine form is a linear combination. The first term, $x_0$ , is the central coefficient. The remaining terms are of the form $x_i \epsilon_i$ . Each such term represents one source of noise, or uncertainty, that we know about x. In those terms, the $x_i$ are real coefficients, and the $\epsilon_i$ are called noise symbols, and can be either 1 or -1. This means the range of an affine form is $\sum_{i=0}^{n} x_i$ .

In the simplest case, then, one could represent a interval $\bar{x} = [1, 2]$ as an affine form with a single noise symbol: $\hat{x} = 1.5 + 0.5 \epsilon_1$ . In fact, this is how one converts between affine forms and intervals.

Things become more interesting, however, when we note that all the noise symbols can be shared by multiple affine forms. In other words, a symbol such as, say, $\epsilon_4$ is the same $\mathit{\epsilon_4}$ in all affine forms that contain it, and has the same value when they are evaluated. All those forms have some source of uncertainty in common, and the shared noise symbol is the way affine arithmetic represents that relation. Those forms are no longer independent, and their dependencies are explicitly handled through the sharing of noise symbols.

For an example of how this is useful, consider two affine forms, $\hat{x} = 10 + 3\epsilon_1 - 4\epsilon_3$ and $\hat{y} = 8 + \epsilon_2 + 2\epsilon_3$ . Using the formula for ranges above, we know that the value of x is in the interval [13, 27], and the range of y is the interval [2, 14]. So if we were to plot the point (x, y) on a plane, it could be anywhere in the rectangle delimited by the above values (light gray in the picture below). But we know that x and y have two sources of uncertainty each, and that some of their uncertainty is explained by the same source (corresponding to $\epsilon_3$ ). The shared noise symbol allows us to estimate their joint range, or the area in which the point (x, y) can lie, more precisely, as the darker polygon in the figure below.

Affine arithmetic provides operations on affine forms as well. These can be of two kinds: affine operations, which are linear combinations of its inputs, and non-affine operations. The first kind includes addition, subtraction, negation, multiplication by scalars and combinations of those. The generic formula for linear combinations of two affine forms is:

$z = \alpha x + \beta y + \gamma$

$\hat{z} = (\alpha x_0 + \beta y_0 + \gamma) + \sum_{i=1} (\alpha x_i + \beta y_i)$

where $\alpha, \beta, \gamma$ are real numbers. Obviously, setting appropriate values for one or more of those gives us the elementary operations of addition ( $\alpha=1, \beta=1, \gamma = 0$ ), subtraction ( $\alpha = 1, \beta = -1, \gamma = 0$ ) and so forth.

All affine operations are computed by specializations of the above formula, so they introduce no error during their computation. Also, elementary arithmetic axioms are respected, so the results look natural. For instance, it’s easy to see how x-x will be zero. Affine operations are also commutative, transitive, etc.

Unfortunately, not all useful operations are affine ones. Non-affine operations such as multiplication, division, logarithms and others are less straightforward, and will be presented in the next article in this series.