I have a question regarding the dependency problem in interval arithmetics.
One common example that is often used to illustrate to problem is a function like
$f: [-1, 1] \rightarrow Y, \, f(x) = x \cdot x,$
with the task to compute $Y$ as accurate as possible. When applying interval arithmetic one gets $[-1, 1] \times[-1, 1] = [-1, 1]$ while the correct range is $[0, 1]$.
My question is now, can't this problem be solved by "recognizing" that the ranges depend on each other (just like a human would do it)? I mean from an implementation point of view, I could just asign each interval an extra flag which indicates on which variable it depends like:
$[-1, 1]_x \times [-1, 1]_y = \begin{cases} [-1, 1], &x \neq y\\ [0, 1], & x = y \end{cases} \,,$
where the $x$ and $y$ subscripts denote on which variables the interval depends on.
I guess not all combinations could be resolved like this (especially if after some computation intervals depend on multiple variables), but the situation should get at least better, right? Is there some theoretical analysis on this available, especially when it would fail? I.e., what are the roots of the dependency problem?
And are there more sofisticated techniques available apart from dividing intervals in smaller subintervals or rewriting $f$ such that each variable appears exactly once (which is not always possible)?
The root of the dependency problem in interval arithmetic is the multiple occurrence of one or more variables in an expression. When there are no multiple occurrences, the interval expression gives the exact result.
It is neither easy nor always possible to rewrite expressions by hand or even automatically to eliminate or reduce multiple occurrences. The dependency problem needs automatic solutions [1] such as centered forms, affine arithmetic, and Taylor models.
[1] Nedialkov et al, Interval Arithmetic, Affine Arithmetic, Taylor Series Methods: Why, What Next?, Numerical Algorithms (2004)