Lambda the Ultimate

a = new interval[-2,3]
[-2, 3]

a^2
[0,9]

a*a
[-6,9]

Aziz,,,

doesn't that mean that as soon as you have the same variable occuring twice in your plot example, things go wrong? for example sin(x)/x.

sorry, i should be less cryptic - it seems to me that many (all?) non-trivial cases where intervals are interesting, they are interesting because there are dependencies. if everyone assumes that they are independent, is it really that useful?

also, can these be related in any useful way to error intervals? typically with errors you assume gaussian distributions and the "interval" represents the spread but is not a formal upper/lower bound. it's also common to assume that linear approximations are sufficient for calculations, so if you want to know the error in f(x) and have a known error in x then you can estimate the error in f(x) as df/dx * error(x). is a similar approximation used in interval handling? (this handles repeated variables "correctly")

hmmm. slowly the gears in my head grind on. so is there some kind of unifying concept that makes intervals, error estimates, etc, all different instances of the same kind of phenomenon?
[edit (instead of another reply) - i guess if i read the leader article that might answer this.... sorry, was just replying to comments; edit 2 - and it's an interesting paper!]

Interval analysis is similar to error analysis, but they're different in significant ways. Interval analysis will always give you the absolute most pessimistic error boundaries, (which is what an engineer might like to see,) and treats all variables as being possibly correlated, while traditional error analysis more often than not (but not necessarily) treats errors as uncorrelated and adds errors as, say, the shorter Pythagorean distance sqrt[error(x)^2 + error(y)^2].

If your error analysis treats all errors as being correlated, interval analysis will give identical results, assuming a proper formulation. Well, at least to the point that interval analysis always gives a "hard" containing bound, while most traditional error analysis gives a confidence interval.

There are lots of really nice properties to interval arithmetic that make it readily implementable in a programming language, though, as opposed to standard error analysis.

A better way to do this is with automatic differentiation which is like interval arithmetic but in the limit as the intervals become small. This discussion seems to have fissioned now but I talk about this here. It's similar to interval arithmetic in many ways but simpler to implement and it executes faster. Suitable modification allows you to compute multiple sensitivities simultaneously. It's much more efficient than doing symbolic differentiation. For example CFD people are able to use this approach to compute sensitivities of entire fluid simulations this way without having to repeatedly run the sim to compute finite differences. There's a web site here.

There are many ways to implement automatic differentiation. Some involve literally transforming your source code by differentiating it line by line. But my favourite approach is the one that looks a lot like interval arithmetic (which could also, in principle, be carried out by a source to source transformation).

One of the largest issues in the use of interval arithmetic is the common problem of "overestimation." This means that, as I noted above, with one formulation, some of your bounds may be larger than they would be if you formulated the problem another way.

There's a large body of work in this area of the field; in fact it's probably where most of the work goes--to make bounds as tight as possible but no tighter!

For example, your example of sin[x]/x, which is common in communication theory, is often redefined as a special function sinc[x] which has the special property that its value at 0 is exactly 1, (by a limit argument,) not undefined. It might be that in evaluating this, you'd be better to take the Taylor series for sin[x], which is:

sin[x] = x - x^3/3! + x^5/5! - x^7/7! + ...

And recast that as:

sinc[x] = 1 - x^2/3! + x^4/5! - x^6/7! + ...

Which symbolic reformulation might give significantly tighter bounds than if you wrote it the first way and then divided by x. Smarter, tighter estimates can also be made by analyzing the behavior of the derivatives of a function, and assuming that all instances of x in the equation are identical, for instance. The bounds for transcendental functions like sin[x] are even tighter than a naive Taylor series formulation due to clever analysis of this sort.

Minimizing error bounds in interval arithmetic is a bit of an art, and explains why mathematicians make the big bucks.

First off, that frink page doesn't actually define the operations, it just gives examples so it's a bit hard to make comments. This paper gives some definitions.

One should symbolically reduce equations as much as possible so the fewest number of intervals are used in any calculation in order to get the tightest bounds. Thus, a^2 is preferred to a*a.

Symbolic reduction is subject to certain rules and with interval arithmetic the rules are very different to numerical arithmetic. This quote suggests that we should reduce an expression using the rules of numerical arithmetic before evaluating it using a completely different (incompatible) set of rules. This sounds like a recipe for bugs and confusion, especially if you have a very smart optimising compiler that might perform some further "harmless" reductions.

Also, what is the point of the power operator? Why would you want [-2, 3]^2 = [0, 9]. You say it depends on whether you think of the intervals as being independent or not. So for the square operator we imagine starting at the left and moving to the right, squaring everything. That's fine and having dependent intervals could be a good thing however you propose no way of declaring intervals to be dependent, so there's no way for me to say A*B and by the way A and B are dependent. So you should either throw away A^2 != A*A or you should make it possible to express (in)dependence. For example if we allow intervals to have identity and we assume dependence for identical objects and independence for non-identical (although possibly equal) objects and allow scalar operations to preserve dependence

A=[-2, 3]
A^2 = [0,9]
A*A=[0,9]
A+A = [-4, 6]
A-A = [0,0]

B=[-2,3]
A*B=[-6, 9] # as they are independent
C = 2 * A # [-4, 6] linked to A
A*C = [0, 18] # == 2 * A*A == 2 * A^2
D = copy(A) # D has the same bounds as A but is no longer dependent
A*D = [-6, 9]

I think then the value of an expression would be independent of whether algebraic reductions had been performed or not (although I haven't worked through the details).

Basically there's not much point in allowing dependence for just a single operation, either disallow it completely or expand it to *, +, - and /.

Alas I have a feeling that successfully expanding it to all operations requires that the language has a symbolic maths engine inside.

Finally, it might be useful to expand the set of intervals. I presume [1,2]/[-1, 1] currently dies with the equivalent of divide by 0. If you allowed interval complements, so for example ]1, 2[ is all numbers except those between 1 and 2 then

[1,2]/[-1, 2] == ]-1, .5[

This has the interesting result that it becomes very easy to arrive at the whole line because ]-1, .5[ + [x + 0, x + 1.5] == everything for any value of x.

While interval arithmetic might be useful, I think that trying to wedge it into a language via overloading of arthmetic operators does not seem like a great idea, existing code using these operators contains many unstated assumptions about distrubivity, cancellation, comparability etc so simply pumping intervals into it and expecting it to work seems hopeful to say the least.

You've addressed a lot of the common issues and frequently asked questions with interval analysis. I might again point to an Interval FAQ to address some of these issues.

First off, that frink page doesn't actually define the operations, it just gives examples so it's a bit hard to make comments.

True, I don't define the operations as well as I'd like (but then I don't define addition over real numbers nor define things like sin[x] either.) I do follow the normal conventions of the field, though, so a standard text on interval analysis should discuss these. Some conventions are interesting, and subject to various implementations, such as for arctan[x] over intervals, which I should document more.

Symbolic reduction is subject to certain rules and with interval arithmetic the rules are very different to numerical arithmetic. This quote suggests that we should reduce an expression using the rules of numerical arithmetic before evaluating it using a completely different (incompatible) set of rules.

I think the difference in the rules is somewhat overstated here. I wouldn't characterize the rules as necessarily being completely different or incompatible, but I also see and agree with your point. If the mathematical analyst reduces the expression x/x to 1, they do so knowing that the variable is dependent and identical, so this is often entirely valid under the rules of real analysis or interval analysis. (In practice, the mathematician should almost always make these and similar cancellations when performing symbolic manipulation, even when working with intervals.) However, to be as safe as possible, Frink treats them as independent and thus gives wider bounds. It does require some human-level intelligence to make this decision, though, just like writing any numerical code. A smarter programmer can tighen the bounds, just as they can improve accuracy in a numerical calculation by reformulating an expression.

This sounds like a recipe for bugs and confusion, especially if you have a very smart optimising compiler that might perform some further "harmless" reductions.

Very true. Which is why Frink doesn't perform possibly-incorrect optimizations of this sort. (I, say, removed the early optimization that x/x=1 when introducing interval arithmetic.) In contrast, Mathematica has some potential issues in their interval analysis, as they perform their tree-rewriting rules to simplify expressions early on. I've seen cases where this could be considered to cause theoretical problems, especially in older versions of Mathematica, which had some absolutely disastrous bugs in their interval implementations early on.

Also, what is the point of the power operator? Why would you want [-2, 3]^2 = [0, 9].

This is simply the convention in the field, and gives the tightest possible bound, assuming a dependence that you maybe shouldn't assume in x*x. You should also note that the power operator can take intervals and/or floating-point numbers as either the base or exponent, which makes defining it essential for completeness.

I think that your points about symbolic reduction and the concept of identity of x/x and x-x are good, common questions, and possibly best addressed in the FAQ entries cited before. In short, I think most (all?) designers of interval libraries leave the decision to symbolically reduce an expression up to the programmer or numerical analyst, otherwise they assume independence, which is the safest possible tactic. It would be nice to express dependence/equivalence in code, though, and let the computer do some of the harder algebraic work when possible. I just don't know a language that does this reliably, though.

Finally, it might be useful to expand the set of intervals. I presume [1,2]/[-1, 1] currently dies with the equivalent of divide by 0.

Yes. It does currently die with a divide by zero error. This is one of the largest sources of diversity in interval arithmetic implementations. There are lots of different tactics to take when dividing by an interval containing zero, such as returning the union of two disjoint intervals, throwing an exception, having half-infinite intervals, using some sort of "containment set" behavior, having intervals with exclusions as you suggested, having undefined behavior, and so on. There's no good agreement to the best tactic to take, as you'll see if you survey various implementations. Right now Frink just flags an error and terminates. This behavior may change.

While interval arithmetic might be useful, I think that trying to wedge it into a language via overloading of arthmetic operators does not seem like a great idea, existing code using these operators contains many unstated assumptions about distrubivity, cancellation, comparability etc so simply pumping intervals into it and expecting it to work seems hopeful to say the least.

Heh. You do see the difficulties easily. :) These are well-known objections, but the rules that Frink and most other interval implementations have chosen are intentionally chosen to avoid cancellation and distributivity errors by giving the widest possible bounds. Still, though, converting real-valued code to interval-valued requires thought and has potential pitfalls.

Whenever possible, I try to help the programmer avoid potential pitfalls. For example, see the section of my documentation about Interval Comparison Operators, which transparently works with intervals if your calculations are unambiguous, but explicitly stops you if your calculations contain ambiguity.

You might be interested in some of the good FAQ entries about converting real-valued code to interval code. Here's a short one and an excellent longer one. They say it better than I can, especially the latter, and point out lots of dangers and good advice.

Overall, you have the same questions and objections that I had when first encountering interval analysis. Your questions are right on target, and very commonly encountered in the field.

I almost wrote this in my original post, but ran out of time. Monte Carlo analysis is one area where interval arithmetic becomes quantumagically cool.

A typical example is electrical circuit simulation. In a real circuit, all of your parts may have varying tolerances, say, your resistors will be 100 ohms plus or minus 10%. Your circuit may or may not behave well if certain components are at the limits of their tolerances, or too hot or cold.

The usual way to analyze this is to perform a monte carlo analysis; the values of each component are varied randomly, and you run the circuit over and over again to see if any combination of values causes unwanted behavior.

The number of cases that you need to analyze grows exponentially. Say, you have a circuit with 20 components, each with 2 varying parameters (e.g. for a transistor, it might be operating temperature and gain.) In order to analyze this circuit solely at the limit points for each component, you actually have to make 4^20 runs, or over a trillion runs! If the components' response is not monotonic, you have to run even more!

With interval analysis, it's possible to perform the same analysis in one run, giving you the worst possible behavior case, including all bounds and nonlinearities! Now that's as close as you'll get to a magical quantum computer in this decade!

The general problem is that error bounds may be overestimated, and it may be a bit difficult to formulate the problem. But, if your error bounds come out tight enough, you know that your circuit will behave properly in all regimes. If the bounds come out large, you can then decide how much more work you want to do.

I'm not an expert but aren't you a bit overstating the benefits of IA?
If the function is non-monotonous, then things becomes a little more complicated for interval analysis no?
Or is-this included in the 'may be difficult to formulate the problem' provision?