in der Intervallrechnung der Nachweis der Existenz einer Lösung x* = (x_i) eines linearen Gleichungssystems \begin{eqnarray}\begin{array}{cc}Ax=b,\,\,\,\,\,\,\,A\in {{\mathbb{R}}}^{n\times n},\,\,\,\,b\in {{\mathbb{R}}}^{n}\end{array}\end{eqnarray} sowie Einschließung von x* in einen Intervallvektor x*. Im Falle der Existenz von x* = (x*) ist die Verifikation meist verbunden mit einer Eindeutigkeitsuntersuchung und einer Schrankenverbesserung bis hin zu einer Einschließung von \({x}_{i}^{* }\) in enge Intervalle, bei denen möglichst viele führende Ziffern der Intervalluntergrenze mit den entsprechenden der Intervallobergrenze übereinstimmen (Zifferngarantie für x*!).

Hat man mehrere lineare Gleichungssysteme der Gestalt (1) zu betrachten mit der Einschränkung A ∈ A, b ∈ b, wobei A eine gegebene Intervallmatrix und b ein gegebener Intervallvektor sind, so führt dies auf ein Intervall-Gleichungssystem \begin{eqnarray}\begin{array}{cc}{\bf{\text{A}}}x={\bf{\text{b}}},\end{array}\end{eqnarray} für dessen Lösungsmenge \begin{eqnarray}S=\{x|\exists A\in {\bf{\text{A}}},\,\,b\in {\bf{\text{b}}}:Ax=b\}\end{eqnarray} eine Einschließung durch einen Intervallvektor x^* gesucht ist. Eine solche Einschließung – wenn auch nicht immer eine enge – liefert der Intervall-Gauß-Algorithmus, sofern er durchführbar ist. Eine andere erhält man mit Hilfe des Krawczyk-Operators (Krawczyk-Verfahren) \begin{eqnarray}{\bf{\text{K}}}(\tilde{x},{\bf{\text{x}}})=\tilde{x}-C({\bf{\text{b}}}-{\bf{\text{A}}}\tilde{x})+(I-C{\bf{\text{A}}})({\bf{\text{x}}}-\tilde{x})\end{eqnarray} bei dem C eine präkonditionierende Matrix bedeutet und \(\tilde{x}\) eine Näherung für die Lösung eines linearen Gleichungssystems \(\tilde{A}x=\tilde{b}\) mit einer regulären Matrix \(\tilde{A}\in \bf \text{A}\) und einer rechten Seite \(\tilde{b}\in \bf \text{b}\) ist. Meist wählt man für \(\tilde{A}\), \(\tilde{b}\) den Mittelpunkt von A bzw. b und für C eine Näherung der Inversen \({\tilde{A}}^{-1}\). Dabei werden die Näherungen \(\tilde{x}\) und C mit herkömmlichen Verfahren berechnet.

Lineare Gleichungssysteme mit komplexen Eingangsdaten können auf analoge Weise behandelt werden. Ist man an einer Einschließung der symmetrischen Lösungsmenge \begin{eqnarray}{S}_{\text{sym}}=\{x|\exists A\in {\bf{\text{A}}},b\in {\bf{\text{b}}}:A={A}^{T}\,\,\text{und}\,\,Ax=b\}\end{eqnarray} interessiert, so kann man das Intervall-Cholesky-Verfahren oder eine Modifikation des Krawczyk-Operators verwenden.

Für die Problemstellung (2) gilt der folgende Satz:

1. Gilt\begin{eqnarray}\begin{array}{cc}{({\bf{\text{K}}}(\tilde{x},{\bf{\text{x}}}))}_{i}\subset {{\bf{\text{x}}}}_{i},\,\,i=1,\ldots,n, & (3)\end{array}\end{eqnarray}für einen Intervallvektorx = (x_i), so sindAund C regulär und (1) ist für jede Wahl von A ∈ Aund b ∈ beindeutig lösbar mit S ⊆ x. Startet man das Iterationsverfahren\begin{eqnarray}\begin{array}{cc}{{\bf{\text{x}}}}^{(k+1)}={\bf{\text{K}}}(\tilde{x},{{\bf{\text{x}}}}^{(k)}),\,\,\,\,\,\,k=0,1,\ldots, & (4)\end{array}\end{eqnarray}mitx⁰ = x. so konvergieren die Iterierten gegen einen Intervallvektorx^* mit \begin{eqnarray}S\subseteq {{\bf{\text{x}}}}^{* }\subseteq {{\bf{\text{x}}}}^{(k+1)}\subseteq {{\bf{\text{x}}}}^{(k)}\subseteq \ldots \subseteq {{\bf{\text{x}}}}^{(0)},\,\,\,k=0,1,\ldots.\end{eqnarray}SindAundbPunktgrößen, d.h.A = [A, A] ≡ A, b = [b, b] ≡ b, so gilt x* = [x*, x*] ≡ x* mit Ax* = b.
2. Mit der Maximumsnorm ║ · ║_∞und dem Betrag | · | einer Intervallgröße gelte\begin{eqnarray}\begin{array}{cc}{\Vert |I-C{\bf{\text{A}}}|\Vert }_{\infty }\lt 1. & (5)\end{array}\end{eqnarray}Dann folgt \(K(\tilde{x},\,x)\subseteq x\)für jeden Intervallvektor\begin{eqnarray}{\bf{\text{x}}}=({\tilde{x}}_{i}+[-\alpha,\alpha ])\end{eqnarray} mit \(\alpha \ge ||\,|C(b-A\tilde{x})|\,|{|}_{\infty }/(1-||\,|I-CA|\,|{|}_{\infty })\), und alle Aussagen in a) bleiben für diesen Vektor gültig.

Wendet man den Satz auf ein einzelnes lineares Gleichungssystem (1) – als Spezialfall von (2) – an, so kann man durch (3) bzw. (5) die Regularität von A und damit die Existenz und Eindeutigkeit der Lösung x* von (1) nachweisen. Außerdem liefert dann (4) im Verbund mit (3) oder (5) Einschließungen von x^* mit Zifferngarantie und läßt sich (unter Verwendung einer Maschinenintervallarithmetik) problemlos auf einem Computer implementieren. Die Bedingung (5) des Satzes gilt bei einem einzelnen linearen Gleichungssystem (1) sicher, wenn C die Inverse A⁻¹ hinreichend gut approximiert. Unabhängig davon kann man die Voraussetzung (3) – auch bei Intervall-Gleichungssystemen – mit Hilfe einer ϵ-Inflation zu erfüllen suchen.

[1] Alefeld, G.; Herzberger, J.: Introduction to Interval Computations. Academic Press New York, 1983.
[2] Neumaier, A.: Interval Methods for Systems of Equations. Cambridge University Press Cambridge, 1990.