Das Unglück ereignete sich aus heiterem Himmel. Seit Wochen hatten Techniker die neue Gasturbine des Leipziger Kraftwerks Nord einjustiert. Alle Maschinen liefen problemlos, als am 1. November 1994 mittags mit einem lauten Knall das Getriebe zerbarst. "Ein Teil wurde aus der Halle geschleudert, riss ein fahrzeuggroßes Loch in die Hallendecke und landete 250 Meter entfernt auf dem Gelände der Wasserwerke", so der Zeitungsbericht vom Tag danach. Auslaufendes Öl ergoss sich in den Maschinenraum und fing Feuer; dabei kamen vier Menschen ums Leben, sechs wurden schwer verletzt.

Was immer die unmittelbaren Ursachen der Katastrophe gewesen sein mögen – ein ausführlicher Untersuchungsbericht benannte einen Materialfehler –, es muss ein Resonanzeffekt eine entscheidende Rolle gespielt haben. Selbst die beträchtliche Bewegungsenergie, die in einer rotierenden Welle steckt, reicht nicht aus, sie ohne weiteres mit dieser Wucht in die Luft zu schleudern. Wenn aber die Drehzahl der Welle sich nahe einer Eigenfrequenz des mechanisches Systems befindet, also der Frequenz, bei der dieses bevorzugt schwingt, können sich Schwingungen mit der Zeit zu zerstörerischen Amplituden aufschaukeln.

Man muss also beim Anfahren einer Turbine einerseits die Drehzahl langsam erhöhen, damit sie sich langsam und gleichmäßig erwärmt, denn große Temperatursprünge schädigen das Material; andererseits muss man über gewisse gefährliche Drehzahlen – die nämlich, die den Resonanzfrequenzen entsprechen – möglichst rasch hinwegfahren.

Wie ermittelt man nun diese Eigenfrequenzen? Besser nicht durch Probieren; man würde einen Unfall wie den von Leipzig riskieren. Auch die experimentelle Bestimmung am verkleinerten Modell stößt bald an prinzipielle Grenzen. Vor allem möchte man die Anlage von vornherein so konstruieren, dass sie in gewissen Drehzahlbereichen gar keine Eigenfrequenzen hat. Nachbessern an der fertigen Anlage wäre sehr kostspielig. Man wird also die Bauteile samt ihren Schwingungseigenschaften mit dem Computer berechnen. Damit liegt auf denen, die diese Berechnungen durchführen, und den Hard- und Software-Fachleuten, die dafür die Werkzeuge bereitstellen, eine erhebliche Verantwortung.

Wie kann man sicher sein, dass die Berechnungen innerhalb der geforderten Genauigkeit korrekt sind? Die beunruhigende Antwort ist: mit den herkömmlichen Methoden gar nicht. Hier gibt es in aller Regel keinen mathematischen Beweis für die Korrektheit des Ergebnisses.

Wie die physikalischen Verhältnisse in mathematische (Differenzial-)Gleichungen umzusetzen sind, ist bekannt. Es gibt Verfahren – vornehmlich die Methode der finiten Elemente, vergleiche Spektrum der Wissenschaft 3/1997, S. 90 –, diese Gleichungen durch computerlösbare (algebraische) Gleichungen zu ersetzen, und zwar so, dass sich der durch diese Näherung begangene Fehler in beherrschbaren Grenzen hält. Dem Computer bleibt nur noch, die Lösungen eines sehr großen Gleichungssystems zu finden – eine vielleicht äußerst Zeit raubende, aber unspektakuläre Arbeit.

Aber genau in diesem Schritt können sich krasse Fehler einschleichen. Es gibt computerberechnete Ergebnisse, an denen nicht einmal die erste Ziffer richtig ist – trotz korrekter Programmierung. Die Software hätte die hoch gelobten automatischen Verifikationstests ohne weiteres bestanden.

Woran liegt es dann? An einer Konvention, die so allgegenwärtig und – zumindest auf den ersten Blick – so einleuchtend ist, dass man sich kaum vorstellen kann, wie es anders gehen soll: an dem so genannten Gleitkommaformat. Aber es gibt Alternativen. Ihr Grundgedanke ist bestechend einfach; ihre volle Wirkung entfalten sie allerdings erst im Verein mit geeigneter Hardware und völlig neu konzipierter Software. In diesem Artikel wird daher nicht nur von hochgenauen Rechenverfahren die Rede sein, sondern auch von einem Chip zur Realisierung dieser Verfahren und von Intervallarithmetik. Mit all diesen Zutaten zusammen kann es gelingen, eine lange, komplizierte Berechnung korrekt durchzuführen – mit derselben Sicherheit wie ein klassischer mathematischer Beweis.

Dieser Artikel beschreibt Arbeiten des Mathematikers Ulrich Kulisch und seiner Schule. Seit Kulisch 1966 Professor an der Technischen Hochschule, der heutigen Universität Karlsruhe, wurde, hat er beide Grundideen aus vagen Anfängen bis zur Perfektion fortentwickelt – und er tut dies noch heute. Aus der Fülle der Ergebnisse kann hier nur ein sehr kleiner Teil wiedergegeben werden.

Stand der Technik: das Gleitkommaformat

Eine Zahl wird innerhalb des Computers zum Beispiel in der Form 1,726793381539881*10E–1 dargestellt, das heißt, als eine Zahl zwischen 1 und 10 – die so genannte Mantisse – mit einer festgelegten Zahl von Stellen hinter dem Komma, multipliziert mit einer Zehnerpotenz, um das Komma an die richtige Stelle zu rücken. Üblich sind 16 Dezimalstellen. (Dass die Zahlen im Inneren des Computers zur Basis 2 statt 10 dargestellt werden, ist für unsere Diskussion unerheblich.) Wenn das Ergebnis einer Rechnung aus dem Bereich von 1 bis 10 hinausgerät – nach oben oder unten –, wird das Komma so verschoben, dass die Mantisse wieder zwischen 1 und 10 liegt, und der Exponent wird entsprechend korrigiert ("Normalisierung"); daher auch der Name Gleitkomma (floa-ting point).

Die reellen Zahlen, mit denen die Theorie arbeitet, haben unendlich viele Stellen hinter dem Komma. Eine Computerzahl ist also stets nur die gerundete Näherung an die reelle Zahl, die man eigentlich im Sinn hat. Das Gleitkommaformat hat den Vorteil, dass es die (üblicherweise) 16 gültigen Ziffern stets unterbringen kann, einerlei, welche Größenordnung die Zahl hat. Wenn man stattdessen beispielsweise für alle Zahlen stets sechs Stellen vor dem Komma und zehn dahinter vorsehen würde, könnte man Zahlen oberhalb einer Million gar nicht mehr darstellen, und für Zahlen der Größenordnung 10–5 gäbe es nur noch Platz für sechs gültige Stellen, weil zunächst vier Nullen hinter dem Komma stehen müssten. In komplizierten numerischen Rechnungen kommen jedoch regelmäßig und unvermeidlich sehr große und sehr kleine Zahlen vor.

Bei jedem Rechenschritt wird gerundet: Das Produkt zweier Zahlen mit 16 Stellen hinter dem Komma hat 32 Stellen hinter dem Komma. Von ihnen werden die letzten 16 Stellen weggeworfen oder gar nicht erst berechnet, damit das Ergebnis wieder in das festgelegte Zahlenformat passt; sie sind ohnehin bedeutungslos, wenn die beiden Faktoren, wie üblich, bereits gerundete Zahlen sind. Wenn zwei Zahlen, die zwischen 1 und 10 liegen, addiert werden, und das Ergebnis ist größer als 10, dann rückt bei der Normalisierung das Komma um eine Stelle nach links, und von den jetzt 17 Stellen hinter dem Komma wird die letzte weggerundet.

Jeder Rechenschritt geht also im Allgemeinen mit einem Rundungsfehler einher. Solche Fehler pflanzen sich über viele Rechenschritte hinweg fort und häufen sich mit der Zeit an. Aber das allein kann so schlimm nicht sein. Nehmen wir an, es gebe eine Million Gleitkommazahlen zu addieren, die sämtlich zwischen 1 und 10 liegen, und es werde nie auf-, sondern immer nur abgerundet, sodass alle Rundungsfehler sich aufaddieren. In diesem ungünstigen Falle wäre ein Fehler von einer Million mal der Einheit der letzten Dezimalstelle zu befürchten. Das Endergebnis wäre also nicht mehr auf 16, sondern nur noch auf 10 Stellen genau. Damit kann ein Anwender immer noch gut zufrieden sein, vor allem, wenn seine Daten ohnehin nur auf fünf Stellen genau sind. Problematisch wird es erst, wenn Zahlen sehr unterschiedlicher Größenordnung zu addieren sind (Kasten oben).

Allein dadurch, dass beide Zahlen auf den gleichen Exponenten zu bringen sind, sodass "Komma unter Komma" zu stehen kommt, muss die Ziffernfolge des kleineren Summanden um eine gewisse Anzahl von Stellen nach rechts rücken. Links wird mit Nullen aufgefüllt, und die rechts überhängenden Stellen werden weggerundet. Wenn vom Ergebnis a+b im weiteren Verlauf der Rechnung wieder a subtrahiert wird, müsste eigentlich b herauskommen. Aber die weggerundeten Stellen von b sind unwiederbringlich verloren: Im Beispiel des Kastens bleiben von den ursprünglich 16 Stellen von b nur noch vier richtige übrig, und wenn a und b um mehr als 16 Zehnerpotenzen auseinander liegen, keine einzige. Die Rechenoperation a+b–a liefert also auf dem Computer ein wesentlich anderes Ergebnis als a–a+b! Damit ist ein wesentliches Gesetz der Addition verletzt: das Kommutativgesetz.

Das Problem: Auslöschung gültiger Ziffern

Anders ausgedrückt: Wenn zwei nahezu gleiche Zahlen (im Beispiel: a+b und a) voneinander subtrahiert werden, verliert das Ergebnis so viele Stellen an Genauigkeit, wie sich durch die Subtraktion führende Nullen ergeben. Das ist die gefürchtete Auslöschung gültiger Stellen durch Subtraktion. Indem der so verunreinigte Zahlenwert im Verlauf der Rechnung weiterverwendet, zum Beispiel mit einer größeren Zahl multipliziert wird, kann der Auslöschungsfehler beliebig große Folgefehler verursachen und die gesamte Rechnung wertlos machen.

In der klassischen Numerik gilt Auslöschung als prinzipielles Problem, das man nicht lösen, sondern nur vermeiden kann, und zwar in der Regel nicht während der Rechnung, sondern weit im Vorfeld. Viel Mühe und Schweiß wird dafür investiert, den Rechengang so zu gestalten, dass Auslöschung gar nicht erst auftreten kann. Es ist ja ziemlich albern, wie in unserem Beispiel erst a und b zu addieren und dann a wieder abzuziehen. Wenn man beide Operationen gar nicht ausführen, sondern an die Stelle des Ergebnisses einfach b setzen würde, hätte man nicht nur Genauigkeit gerettet, sondern auch noch Rechenzeit gespart.

Allgemein sind also Algorithmen zu suchen, die ohne die Subtraktion nahezu gleicher Größen auskommen. Es muss sie geben, wenn das zu Grunde liegende Problem "vernünftig gestellt" ist.

Die Praxis bleibt hinter diesen hehren Zielen in der Regel weit zurück.

- Häufig verfügt man nicht über ausreichend Einblick in die Problemstruktur, um den richtigen Algorithmus zu finden.

- Addieren und Subtrahieren der gleichen Größe folgen im Allgemeinen nicht, wie in dem obigen Beispiel, unmittelbar aufeinander, sondern sind durch zahlreiche andere Operationen voneinander getrennt, sodass das Paar einander entgegengesetzter Operationen praktisch nicht zu identifizieren ist.

- Ob Auslöschung stattfindet oder nicht, hängt mitunter von den Eingangsdaten ab, die der Programmierer noch nicht kennt, wenn er seine Software schreibt.

- Im Prinzip ist es möglich, den Fehler jeder einzelnen arithmetischen Operation abzuschätzen und seine Fortpflanzung im weiteren Gang der Rechnung zu verfolgen. Bei Milliarden von Operationen – die auf modernen Rechnern in Sekunden erledigt sind – ist eine solche Fehleranalyse jedoch meistens praktisch nicht durchführbar.

- In gewissen Situationen, vor allem beim iterativen Lösen von Gleichungen, tritt die Subtraktion nahezu gleicher Größen sogar regelmäßig auf, und zwar gerade dann, wenn das Verfahren der Lösung schon sehr nahe gekommen ist (Kasten unten).

Eine gebräuchliche Abhilfe ist die so genannte vierfachlange Arithmetik. Man sieht zur Speicherung einer Zahl nicht einen, sondern zwei Gleitkommazahl-Speicherplätze vor. (Eine 16-stellige Dezimalzahl heißt traditionell "doppeltgenau" oder "doppeltlang", weil es auch einfachgenaue Zahlenformate mit dem halben Speicherplatzbedarf gibt.) Von den 32 so darstellbaren Dezimalziffern kommen die linken 16 Stellen in den ersten Speicherplatz, die rechten in den zweiten. Die stellenrichtige Addition zweier vierfachlanger Zahlen wird durch eine entsprechend programmierte Folge von Einzelbefehlen realisiert. Wenn durch Auslöschung 16 gültige Stellen verloren gehen, bleiben bei vierfachgenauem Rechnen immerhin noch 16 brauchbare Stellen übrig (statt gar keiner beim üblichen Verfahren).

Aber warum soll man bei der Verdopplung der Stellenzahl stehen bleiben? Warum nicht achtfach-, sechzehnfach-, hundertfachgenau rechnen oder, realistischer, stets mit der maximalen noch sinnvollen Stellenzahl? Die konsequente Weiterentwicklung dieser Idee besteht in einer Abkehr vom Gleitkommaformat. Es gibt schließlich auch noch die Festkomma-(fixed point)-Darstellung, die normalerweise für ganze Zahlen benutzt wird. In der Festkomma-Arithmetik gibt es keine Verluste gültiger Ziffern durch Normalisierung, weil es keine Normalisierung gibt: Die Festkomma-Addition ist stets fehlerfrei. Nur ist der Rechenbereich sehr eng begrenzt: Zahlen, die betragsmäßig größer sind als 232, das ist etwas mehr als zwei Milliarden, können nicht mehr dargestellt werden.

Diese Grenze ist aber nicht prinzipieller Natur, sondern beruht abermals auf einer Konvention: Seit Jahrzehnten pflegt man einer Festkommazahl nicht mehr als vier Bytes (32 Bits) Speicherplatz einzuräumen. Der Grund dafür, nämlich sparsamer Umgang mit dem knappen Speicherplatz, ist durch den Fortschritt in der Hardwaretechnik längst überholt. Auf einem modernen Chip ist mühelos ein Register – ein chip-interner Speicherplatz – für eine Festkommazahl mit etwa 2000 Binärstellen, entsprechend ungefähr 600 Dezimalstellen, unterzubringen.

Und das ist im Prinzip auch schon das neue Konzept: Man rechne mit extrem langen Festkommazahlen, so lang, dass sie jede Gleitkommazahl exakt darstellen können. Eine 600-stellige Dezimalzahl mit jeweils 300 Stellen links und rechts vom Komma reicht bereits aus; denn im heute üblichen Gleitkommaformat ist die Größe des Exponenten nach oben und unten beschränkt, und diese großzügigen Schranken einzuhalten ist nicht schwer. Zahlen, die betragsmäßig größer sind als 21024~10300 oder kleiner als 2–1024~10–300, sind in Gleitkommaform ohnehin nicht darstellbar; also muss das lange Festkommaregister für sie auch keinen Platz bereithalten.

Wenn zu einer solchen langen Festkommazahl eine gewöhnliche Gleitkommazahl addiert werden soll, findet die ansonsten erforderliche Normalisierung nicht statt. Der Exponent bestimmt nur, unter welche Ziffern der langen Festkommazahl die Gleitkommazahl gesetzt wird, und schon kann die Addition beginnen (Schema unten).

Interessanterweise greift dieses Verfahren eine Technik wieder auf, die in den alten mecha-nischen Tischrechnern gang und gäbe war (Foto rechts). Das Ergebnisregister war sehr lang und hatte im Gegensatz zu den Eingaberegistern ein festes Komma. In dieses Register konnte man beliebig viele Summanden der verschiedensten Größenordnungen hineinaddieren (eine Summe "auflaufen lassen"), ohne dass es zu Rundungs- oder Auslöschungsfehlern kam. Mit den ersten elektronischen Rechnern wurde dieses Prinzip aus Kostengründen zu Gunsten des Gleitkommaformats aufgegeben. Heute spielen diese Gründe keine Rolle mehr; es ist nur noch das Beharrungsvermögen der etablierten Technik – samt der zugehörigen Trägheit der einseitig trainierten Gedanken –, das der Wiederaufnahme des Prinzips im Wege steht.

Das Skalarprodukt: die fünfte Grundrechenart

Besteht also die Lösung des Auslöschungsproblems darin, alle Rechnungen nur noch mit 600-stelligen Festkommazahlen auszuführen? Keineswegs; man würde mit Kanonen auf Spatzen schießen. Die Ergebnisse von Multiplikation und Division allein werden durch ein Langzahlregister nicht besser; nur Addition und Subtraktion sind die kritischen Operationen. Bei näherer Analyse kristallisiert sich jedoch eine einzige – zusammengesetzte – Rechenoperation he-raus, bei der die Kanone nicht nur das angemessene Mittel ist, sondern einen Großteil der gängigen Probleme erledigt: das Skalarprodukt zweier Vektoren.

Diese Operation ist von zentraler Bedeutung für die gesamte Numerik. Das Lösen großer Gleichungssysteme läuft im Endeffekt praktisch immer auf vielfache Anwendung des Skalarprodukts hinaus. Die Operation besteht darin, zahlreiche Produkte – 1000 Stück sind nicht ungewöhnlich – von jeweils zwei Gleitkommazahlen zu addieren. Die Größenordnung dieser Produkte ist im Allgemeinen kaum abschätzbar. Deswegen ist es sehr hilfreich, dass im Langzahlregister das Aufaddieren (die "Akkumulation") ohne jegliche Rundung verläuft (Schema unten). Erst die Gesamtsumme wird wieder gerundet, damit die weitere Rechnung im Gleitkommaformat stattfinden kann.

Im Prinzip ist das lange Festkommaregister mit der üblichen Hardware realisierbar. Man zerlege die Folge der 600 Ziffern, aus denen die lange Festkommazahl besteht, in Teilfolgen geeigneter Länge und schreibe jede von ihnen in ein Register für eine konventionelle Festkommazahl. Jedem dieser Speicherplätze ist seine Position innerhalb der langen Zahl fest zugeordnet; man muss nur noch durch geeignete Programmierung dafür Sorge tragen, dass eine Gleitkommazahl an der richtigen Stelle zu dieser langen Zahl addiert wird.

Ein so zusammengebasteltes ("emuliertes") Langregister arbeitet zwar so fehlerfrei, wie die Theorie es behauptet, ist für die Praxis jedoch ungeeignet. Die Rechenarbeit beansprucht ein Vielfaches der sonst benötigten Zeit, sodass ein Nutzer sich lieber mit den konventionell, aber viel schneller errechneten Ergebnissen zufrieden geben wird.

In einem modernen Prozessor ist die Gleitkomma-Addition so optimiert, dass sie viel schneller abläuft als jede logisch äquivalente, aber explizit programmierte (das heißt aus mehreren Einzelbefehlen zusammengesetzte) Aktion. Deswegen kostet bereits die in Software realisierte Vierfacharithmetik ungefähr viermal so viel Zeit wie die konventionelle. Wenn man jedoch die Akkumulation im langen Festkommaregister als "fest verdrahteten" Befehl bereits in den Mikrochip einbaut, ist die erhöhte Genauigkeit ohne Zeitverlust zu haben.

Eine Arbeitsgemeinschaft aus Kulischs Institut an der Universität Karlsruhe, dem Institut für Informatik der Technischen Universität Hamburg-Harburg und dem Institut für Mikroelektronik an der Universität Stuttgart hat 1995 einen solchen Mikrochip entwickelt: den Vektorarithmetik-Koprozessor XPA3233. Zugleich wurden Erweiterungen gebräuchlicher Programmiersprachen geschrieben, mit denen man die neuen Fähigkeiten des Prozessors in komfortabler Weise nutzen kann: Pascal-XSC, C-XSC und Fortran-XSC. Gegenüber der oben angesprochenen Software-Implementierung erzielte der Chip die hundertfache Rechengeschwindigkeit und übertraf damit auch die Vierfacharithmetik, sowohl an Qualität wie auch an Arbeitsgeschwindigkeit.

Die Ergebnisse der hochgenauen Arithmetik sind stellenweise spektakulär. Alfons Ams und Wolfram Klein haben an dem Karlsruher Institut das Schwingungsverhalten einer rotierenden Turbine berechnet. Während die konventionelle Rechnung eine Häufung von Eigenfrequenzen in höheren Drehzahlbereichen findet, ergibt die hochgenaue Arithmetik, dass die vorgeblichen Eigenfrequenzen bis auf eine sämtlich auf Rechenungenauigkeiten zurückzuführen sind, dass also die Turbine auch bei diesen Drehzahlen sicher betrieben werden kann.

Intervallarithmetik

Es ist sogar möglich, dieses Ergebnis mit einer Garantie zu versehen, die so gut ist wie ein mathematischer Beweis.

In modernen Prozessoren sind die klassischen vier Grundrechenarten so sauber implementiert, dass der Rundefehler so klein ist wie überhaupt möglich, das heißt höchstens einen halben Stellenwert der letzten Ziffer. Nachdem mit der Akkumulation und dem Skalarprodukt ein großer Genauigkeitsvernichter unschädlich gemacht ist, kann ein gutes altes Prinzip die Geltung erlangen, die ihm gebührt: die Intervallrechnung.

Wenn die Eingangswerte einer langen Rechnung gemessene Daten sind, haben sie "von Natur aus" eine gewisse Ungenauigkeit. Vielleicht wurde eine Länge mit 1,075±0,002 Millimeter gemessen; dann ist es üblich, mit dem Wert 1,075 zu rechnen, als ob er exakt wäre, und zu ignorieren, dass der Messfehler sich durch die gesamte Rechnung fortpflanzt. Dabei ist es zumindest im Prinzip sehr einfach, das Schicksal des Fehlers durch die ganze Rechnung hindurch zu verfolgen: Man rechnet nicht mit einzelnen Zahlen, sondern mit ganzen Intervallen. Ein Intervall ist definiert durch eine obere und eine untere Grenze; dem im obigen Beispiel genannten Messwert entspricht das Intervall [1,073; 1,077]. Diese Angabe ist zwar schwammiger als der – scheinbar – präzise Wert 1,075; aber dafür haben wir uns die Gewissheit eingehandelt, dass der Messwert im Inneren des Intervalls liegt.

Dieses Prinzip überträgt man nun auf den gesamten Verlauf der Rechnung. Man gibt nicht mehr eine Zahl an, die – hoffentlich – ungefähr gleich dem richtigen Ergebnis der Rechnung ist, sondern ein Intervall, in dem das richtige Ergebnis mit Sicherheit enthalten ist. Hat man zwei Zahlen a und b dargestellt durch die Intervalle [a1, a2] und [b1, b2], dann liegt deren Summe mit Sicherheit in dem Intervall [a1b1, a2b2]. Dabei bedeutet "Addieren mit Aufrunden" und "Addieren mit Abrunden". Auf analoge Weise wird definiert, wie Intervalle zu subtrahieren, multiplizieren und dividieren sind.

In einer Weiterentwicklung der Theorie werden Intervalle zu mathematischen Subjekten eigenen Rechts: Man findet mathematische Gesetze für das Rechnen mit Intervallen, erweitert den Intervallbegriff auf mehrere Dimensionen – ein zweidimensionales Intervall ist ein Rechteck, ein dreidimensionales ein Quader, Entsprechendes gibt es für höhere Dimensionen – und vor allem: Man schreibt Programmiersprachen, in denen ein Intervall mit einem einzigen Namen bezeichnet wird, so wie sonst eine Zahl. Die oben genannten Erweiterungen der klassischen Programmiersprachen Fortran, Pascal und C haben diese Eigenschaft. Der Programmierer kann also Anweisungen zum Rechnen mit Intervallen mit exakt denselben formelmäßigen Ausdrücken erteilen wie sonst zum Rechnen mit Zahlen.

Das Konzept der Intervallrechnung bietet also handfeste Vorteile – und es ist in den Grundzügen seit Jahrzehnten bekannt: Erste Vorläufer der Ideen veröffentlichte 1958 der japanische Mathematiker Teruo Sunaga; in Karlsruhe lief bereits 1967 eine entsprechende Erweiterung der Programmiersprache Algol-60 auf einer Anlage Z23 von Zuse. Gleichwohl hat sich die Intervallarithmetik bislang nicht allgemein durchgesetzt.

Sie sei viel zu langsam, wenden die Kritiker ein, und häufig viel zu pessimistisch in dem Sinne, dass sie zu große Intervalle liefere und damit dem Ergebnis eine weit größere Unsicherheit zuschreibe, als den Tatsachen entspreche. Nur allzu oft stehe am Ende einer langen und mühsamen Rechnung das Ergebnis, dass die Lösung zwischen – und + liegt; aber das wusste man vorher schon.

Der erste Einwand trifft zu – allerdings nur für die gegenwärtige Situation, nicht für das Prinzip. Intervallrechnung ist langsam, weil sie bislang – notgedrungen – auf Maschinen praktiziert wird, die genau dafür nicht gebaut sind. So kostet allein das Umschalten zwischen Auf- und Abrunden sehr viel Zeit, weil es in dem heute fast allgemein befolgten IEEE-Standard von der eigentlichen Rechenoperation getrennt ist; es wird ja auch in der üblichen Arithmetik kaum gebraucht. Auf einem geeignet entworfenen Prozessor, der auch noch beide Intervallgrenzen parallel berechnet, ist eine elementare Operation mit Intervallen so schnell wie eine mit gewöhnlichen Zahlen.

Der zweite Einwand trifft allenfalls auf naive Anwendungen der Intervallarithmetik zu. Eine Funktion f, ausgewertet auf einem Intervall X=[a,b], soll ein Intervall ergeben, das dann f(X) genannt wird und alle f(x) für x zwischen a und b enthält – aber möglichst nicht mehr. Wenn das Intervall groß ist und man die Funktion f ungeschickt berechnet, kann man in der Tat eine erhebliche Überschätzung des Intervalls erhalten. Zwei Rechenverfahren, die für Zahlen gleichwertig sind, können nämlich auf Intervalle angewandt völlig verschiedene Ergebnisse liefern. Aber die Theorie gibt ein Verfahren an (die "zentrierte Berechnung"), das die Überschätzung minimal macht.

Darüber hinaus hat man stets die Freiheit, ein Intervall in Teilintervalle zu zerlegen – in der numerischen Mathematik ohnehin gängige Praxis. Mit der genannten optimalen Berechnungsweise nimmt die Überschätzung sogar schneller ab als die Größe der Teilintervalle.

Allgemein geht es darum, unter mehreren Wegen zur Lösung eines Problems einen zu finden, bei dem die Intervallrechnung ihre Stärken entfaltet. Dieser Lösungsweg ist häufig nicht der sonst übliche. So gibt es für manche Gleichungssysteme explizite Lösungsalgorithmen: Rechenanweisungen, die nach einer vorab begrenzten Anzahl von Schritten die exakte Lösung liefern würden – wenn man exakt rechnen könnte. Einen solchen Algorithmus zur Verfügung zu haben ist ein relativ seltenes Vergnügen; meistens gibt es nur iterative Verfahren, also solche, die aus einer Näherung an die Lösung eine – hoffentlich – bessere machen.



Besser gut iteriert als falsch exakt

Es sieht so aus, als wäre ein iteratives Verfahren eine Notlösung, zu der man greift, wenn kein explizites zur Verfügung steht. Aber explizite Verfahren leiden unter der üblichen Fehlerfortpflanzung, die eben auch Fehlerverstärkung bedeuten kann. Unter ungünstigen Umständen liefert die Intervallarithmetik ein unbrauchbar großes Intervall als Lösung (und die konventionelle Rechnung ein krass falsches Ergebnis, ohne dass man es merkt). Dagegen sind iterative Verfahren so gebaut, dass sie ein Intervall, in dem die Lösung liegt, in der Tendenz verkleinern; wenn sie das nicht täten, würden sie überhaupt nicht funktionieren. Es gibt also einen ins Verfahren eingebauten Mechanismus, der dem Trend zur Vergrößerung der Intervalle entgegenwirkt. Dadurch kann die Intervallrechnung eine große Ungenauigkeit (entsprechend einem großen, nichts sagenden Intervall), die sich während einer längeren Rechnung angehäuft hat, auch wieder abbauen.

Leider wirken Iterationsverfahren nicht unter allen Umständen Intervall verkleinernd ("kontrahierend"). Vielmehr kann es vorkommen, dass ein Iterationsschritt nicht nur vorübergehend in die Irre führt, sondern auch ein Intervall erheblich vergrößert. Die konventionelle Arithmetik verliert dann Genauigkeit, ohne dass man es merkt; die Intervallarithmetik dagegen muss bisher Erreichtes nicht aufgeben. Das bisher erreichte Intervall enthält mit Sicherheit die Lösung, das neu berechnete, größere auch; also muss die Lösung im Durchschnitt beider Intervalle enthalten sein. So gewinnt das Intervallverfahren noch Information aus einer Situation, die ansonsten einem Scheitern des Verfahrens gleichkäme. Die Intervallarithmetik ist einleuchtenderweise besonders geeignet, wenn eigentlich keine Zahl, sondern ein Intervall gesucht ist. Man hat beispielsweise eine Funktion f(x), die zu kompliziert ist, um mit theoretischen Mitteln erfassbar zu sein, und möchte wissen, ob sie für alle x-Werte in einem gewissen Bereich größer als null ist. (Vielleicht entspricht f(x)=0 einem gefährlichen Zustand oder dem Zusammenbruch des Systems.)

Üblicherweise würde man f(x) an sehr vielen Stellen x ausrechnen, obgleich einen die Funktionswerte nicht sonderlich interessieren. Wenn die Stützstellen hinreichend dicht beieinander liegen, die Funktionswerte an all diesen Stellen positiv sind und zwischen benachbarten Stellen keine allzu großen Sprünge machen, verbindet man nur zu bereitwillig die Punkte durch eine glatte, interpolierende Kurve – was falsch sein kann. Die echte Kurve kann sehr wohl einen Durchhänger haben. Dagegen liefert die Intervallrechnung möglicherweise bereits mit einer einzigen Auswertung die Gewissheit, dass f in dem betrachteten Intervall keine Nullstelle hat.

Ein zentrales Verfahren der klassischen Analysis wirkt, genau besehen, wie gemacht für die Anwendung der Intervallarithmetik: die Approximation von Funktionen durch Taylor-Polynome. Man kann die Werte fast aller für die Anwendungen bedeutender Funktionen mit großer Genauigkeit näherungsweise berechnen, und zwar mit Hilfe einer Anweisung, die nur Additionen und Multiplikationen enthält. Vor allem aber ist der Approximationsfehler, also der Unterschied zwischen dem richtigen und dem genäherten Funktionswert, angebbar. Er ist eine kleine Zahl mal einer gewissen Ableitung der zu berechnenden Funktion an einer Stelle x, die wiederum in einem explizit angebbaren Intervall liegt.

Die Theorie gibt also bereits ein Intervall für den Fehler an, die Intervallarithmetik muss es nur noch ausrechnen. Allerdings ist dafür eine hohe Ableitung der zu berechnenden Funktion auszuwerten. Das ist von Hand sehr mühsam zu programmieren; aber es gibt bereits eine Technik, das "automatische Differenzieren", mit welcher der Programmierer diese Arbeit bequem an den Computer delegieren kann.

Damit ergibt sich für die Intervallarithmetik ein ähnliches Bild wie für das hochgenaue Rechnen: Beide können allein nicht gedeihen in einer Welt, in der alles auf andere Arten des Rechnens eingestellt ist. Sie stützen sich zwar gegenseitig; aber zu ihrer vollen Entfaltung benötigen sie sowohl die passende Hardware als auch eine passende Theorie mitsamt daraus entwickelter Software.

Der Chip XPA 3233 ist immerhin ein Demonstrationsmodell für die Realisierbarkeit dieser Konzepte. Als Rechengerät für den praktischen Einsatz ist er von der rasanten Entwicklung der Technologie längst wieder überholt worden. Mittel für seine Weiterentwicklung bis zur Vermarktungsreife konnten seinerzeit nicht aufgebracht werden.

Immerhin hat John Gustafson, ein bedeutender Computerexperte der USA, in jüngerer Zeit öffentlich dazu aufgerufen, dem Rechnen mit garantierten Ergebnissen und der Intervallarithmetik große Aufmerksamkeit zu widmen. Für die Zukunft beider Konzepte gibt es Anlass zu verhaltenem Optimismus.

Literaturhinweise


Computer, Arithmetik und Numerik – ein Memorandum. Von Ulrich Kulisch in: Überblicke Mathematik 1998. Vieweg, Wiesbaden 1998.

Advanced Arithmetic for the Digital Computer – Design of Arithmetic Units. Von Ulrich Kulisch in: Electronic Notes of Theoretical Computer Science, 1999.

Computational Verifiability and Feasibility of the ASCI Program. Von John Gustafson in: IEEE Computational Science & Engineering Bd. 5, Nr. 1, S. 36–45 (1998).

Aus: Spektrum der Wissenschaft 9 / 2000, Seite 54
© Spektrum der Wissenschaft Verlagsgesellschaft mbH