5.3.1.4 Konvexität und Diskontinuität

Die bisher betrachteten Intervalle sind ununterbrochen und werden auch konvexe Intervalle genannt. Neben konvexen Intervallen können allerdings auch unterbrochene Intervalle auftreten. Diese weisen ähnlich einer unstetigen Funktion Lücken in ihrem Wertebereich auf:

Definition 5.3.7   (konvexes Intervall)
Ein konvexes Intervall ist ein ununterbrochener Wertebereich, definiert durch eine untere und eine obere Schranke. Entsprechend ist ein diskontinuierliches Intervall ein unterbrochener Wertebereich, der aus einzelnen, disjunkten Subintervallen besteht.

Wenn ein Problem ausschließlich Variablen mit konvexen Wertebereichen involviert, kann sich dies positiv auf das Intervall-Lösungsverfahren bzgl. des erreichten Konsistenzgrades und der Vollständigkeit des Ergebnisses auswirken. Analog zu konvexen Intervallen spricht man von konvexen Constraints:

Definition 5.3.8   (konvexes Constraint)
Ein konvexes Constraint besitzt ausschließlich konvexe Intervalle als Ergebnismengen.

Ein konvexes Constraint führt demnach, bedingt durch die Art der Relation, zu konvexen Ergebnisintervallen. Konvexe Constraints werden auch engl. non-disjunctive Constraints genannt, da sie die Wertebereiche der Ergebnisintervalle nicht unterbrechen.

Eine wichtige Frage betrifft die Behandlung von diskontinuierlichen Intervallen. Sie treten auf, wenn die Menge der mit einem Constraint konsistenten Werte unterbrochen ist, weil dem Constraint für die Berechnung eines Wertes (1) eine unstetige oder (2) eine mehrwertige Funktion der anderen Werte zugrunde liegt (vgl. Davis, 1987, S. 297):

Beispiel 5.3.3   Für das Constraint $v_1 \times v_2 = v_3$ mit den Wertebereichen $v_2: [-1,1]$ und $v_3:[4,5]$ ist die Ergebnismenge für $v_1$ das unterbrochene Intervall $[-\infty,-4] \cup [4,+\infty]$. Dies liegt darin begründet, dass $v_1=\frac{v_3}{v_2}$ eine unstetige Funktion für $v_2=0$ ist.

Eine mehrwertige Funktion mit einem unterbrochenen Intervall als Ergebnis liegt für das Constraint im folgenden Fall vor:

Beispiel 5.3.4   Für das Constraint $v_1^2=v_2$ mit dem Wertebereich $v_2:[4,9]$ ergibt sich für $v_1:[-3,-2] \cup [2,3]$, weil $v_1=\sqrt{v_2}$ eine mehrwertige Funktion ist.

Zur Verarbeitung dieser Ergebnismengen existieren zwei Ansätze: Zum einen kann die Intervallrepräsentation um diskontinuierliche Intervalle, bestehend aus Vereinigungsmengen von Teilintervallen, erweitert werden.^5.89 Zum anderen ist es möglich, lediglich die konvexe Hülle der Ergebnisintervalle zu betrachten, d.h. das Minimum und das Maximum aller Teilintervalle. Das Ergebnis jeder Operation ist hier ein ununterbrochenes bzw. konvexes Intervall. Dies ist jeweils das kleinste Intervall, welches sämtliche Lösungen umschließt. Der entstehende Informationsverlust wird i.d.R. aufgewogen durch die einfache Verarbeitung konvexer Intervalle (vgl. Davis, 1987, S. 297). Viele verfügbare Systeme bzw. Algorithmen implementieren daher das letztere Vorgehen.

Fußnoten

...^5.89

Die in diesem Fall bei Rechenoperationen auf diskontinuierlichen Intervallen entstehenden überlappenden Teilintervalle werden jeweils zu ununterbrochenen (Teil-)Intervallen zusammengefasst.