Melden Sie sich hier an, um auf Kommentare und die Whitepaper-Datenbank zugreifen zu können.

Kein Log-In? Dann jetzt kostenlos registrieren.

Falls Sie Ihr Passwort vergessen haben, können Sie es hier per E-Mail anfordern.

Der Zugang zur Reseller Only!-Community ist registrierten Fachhändlern, Systemhäusern und Dienstleistern vorbehalten.

Registrieren Sie sich hier, um Zugang zu diesem Bereich zu beantragen. Die Freigabe Ihres Zugangs erfolgt nach Prüfung Ihrer Anmeldung durch die Redaktion.

14.07.1989 - 

Chaos im Computer kann doch auch reale Situationen spiegeln:

Wege durch das numerische Dickicht

In der Meteorologie, in der Strömungsmechanik etwa beim Flugzeug- und Triebwerksbau oder auch bei der Festigkeitsanalyse stählerner Strukturen treten Gleichungssysteme auf, die oft erst nach vielen Tausend Iterationen brauchbare Lösungswerte liefern. Doch wenn man diese Iterationen, die auf das immer wiederkehrende Berechnen einer Gleichung mit immer wieder ein wenig sich ändernden Zahlen hinauslaufen, per Computer auch ausgesprochen schnell und bequem erledigen kann - wer garantiert eigentlich, daß die Resultate später auch wirklich korrekt und sinnvoll sind?

Diese Frage stellte sich unlängst der Mathematiker James A. Yorke vom Physik- und Technologie-Institut der University of Maryland, USA. Denn bei iterativen Berechnungen, bei denen er das Resultat von Versuch n gleich wieder als Ausgangswert von Versuch (n+ 1) benutzte, stellte er immer wieder fest: Selbst so ein einfaches iteratives Vorgehen führt häufig zu überraschend komplexen, unvorhersagbaren Ereignissen. Und da diese Ereignisketten sich mit wachsendem n oft ganz drastisch voneinander unterscheiden, weichen die Ausgangswerte für die Iteration 1 auch nur minimal voneinander ab, ist natürlich erst recht die Frage angebracht: Was geschieht da eigentlich in Rechnern, die Iterationen tausendfach durchlaufen und die man anfangs nur mit ziemlich unscharfen physikalischen Meßwerten hat füttern können, also beispielsweise mit einem Meßwert für die Temperatur, der überhaupt bloß auf drei signifikante (Dezimal-)Stellen genau bekannt ist - wie etwa 293 Kelvin?

Wie irrlichternd Zahlenwerte im Zuge einer vielstufigen Iteration hin- und herspringen können, macht Yorke gern am Beispiel eines einfachen Ausdrucks deutlich

4x-xe2

Denn setzt man hier für x die Zahl 0,2 ein, so ergibt sich 0,76. Und setzt man nun 0,76 ein und so weiter, so ergeben sich der Reihe nach die Werte

2,4624; 3,78619; 0,809539; 2,5828; 3,66034; 1,24327; 3,42736; 1,96266; 3,99861; 0,00557; 0,02227 etc.

Bei Verwendung von 0,21 als Startwert entsteht dagegen eine völlig neue Reihe, nämlich

0,7959; 2,55014; 3,69734; 1,11903; 3,22389; 2,50209; 3,7479; 0,9444834; 2,88662; 3,2139; 2,52645; 3,72285 etc.

Betrachtet man nun eine Vielzahl von Gleichungen dieser und ähnlicher Gestalt, so sieht man die einzelnen Zahlenwerte für jede neue Iteration fast immer wirr umherspringen, kann aber auch notieren: Die Bahn, die diese Punkte bei zweidimensionaler Darstellung beschreiben, tendiert immerhin dazu, innerhalb gewisser Grenzen zu bleiben und manche Zahlenbereiche - wie beispielsweise den zwischen 0,3 und 0,4 - häufiger aufzusuchen als andere. Und ändert man den Ausgangswert so einer vielstufigen Iteration wiederum um

auch bloß ein Geringes, so ergeben sich, wie demonstriert, zwar völlig andere Folge-Zahlenwerte - doch das beschriebene Allgemeinmuster der Kurve, die sich jeweils zeichnen läßt, bleibt mehr oder weniger gleich.

Da Computer von Haus aus mit begrenzter Mantisse, also mit begrenzter Stellenzahl rechnen, müssen sie immer wieder runden und mithin die jeweils "wahren" Zahlenwerte verfälschen. Und diese Vorstellung, so findet nicht nur Yorke, ist im Lichte der skizzierten, wilden Oszillationen und starken Abweichungen bei nur minimaler Verfälschung des jeweiligen Ausgangswerts eigentlich ziemlich beunruhigend.

So weiß man von Gleichungen, bei denen zwar mit 14 Dezimalstellen Genauigkeit gerechnet wird und bei denen man die Startwerte sogar nur an der allerletzten Stelle voneinander abweichen ließ, daß schon nach wenigen -zig Iterationen grundlegend andere Zahlenwerte erreicht werden.

Und nicht selten verdoppelt die Distanz zwischen je zwei korrespondierenden Punkten der beiden Reihen sich glatt schon mit jedem einzelnen weiteren Iterations-Schritt.

Trägt man für eine vielstufige Iteration der oben an Hand einer Gleichung skizzierten Art die Nummer des jeweiligen Iterations-Schritts auf der Abszisse eines Koordinatensystems an, während der zugehörige Wert in Ordinatenrichtung aufgetragen wird, so kann man bildlich davon sprechen, die Folge der Werte beschreibe eine Art Bahnkurve oder auch, wie Yorke sagt, "Orbit". Und in diesem Zusammenhang ist nun interessant, daß Yorke und zwei Kollegen - Celso Grebogi und Stephen M. Hammel - einen numerisch korrekten Weg gefunden haben, auf dem sie wenigstens eines sicherstellen können, daß nämlich die einzelnen Werte aller Punkte so einer Bahnkurve, ausgehend vom Startwert, allesamt absolut korrekt berechnet wurden - also ohne jeglichen verfälschenden Rundungsfehler, wie er normalerweise ja an fast jeder einzelnen Iterations-Stufe in Kauf genommen werden muß.

Die drei US-Mathematiker und -Informatiker haben bei der Arbeit an ihren Algorithmen aufwendige numerische Prozeduren entwickelt, die sicherstellen, daß eine bestimmte Bahnkurve absolut korrekt berechnet wird. Doch gleichzeitig haben diese neuen Prozeduren zur Überraschung aller Kundigen auch noch gezeigt: zu herkömmlich-verfälschten, weil durch Rundungsfehler wieder und wieder verzerrten und schließlich ins Unvorhersagbare laufenden Iterations-Bahnkurven, die der Computer auf die übliche Weise errechnet hat, gibt es über viele Iterationen hinweg weitgehend deckungsgleiche Bahnen, die nun aber Punkt für Punkt mit absoluter Exaktheit errechnet worden sind, bei denen es also keine Verfälschung gibt.

Vergleicht man für einen gegebenen Ausdruck und für einen gegebenen Anfangswert nun die gewöhnliche, mit herkömmlicher Computer-Numerik errechnete Bahnkurve einerseits mit jener, die aus der absolut exakten Rechnung folgt, so zeigt sich zwar erwartungsgemäß, daß beide sehr bald schon denkbar stark voneinander abweichen. Doch läßt man die exakt berechnete Bahnkurve für den gleichen Ausdruck nun probehalber an einem Startwert beginnen, der minimal neben dem "eigentlichem" Startwert liegt - so findet man etwas Überraschendes: Diese neue, exakte Bahnkurve folgt nun über Millionen von Iterationen hinweg Punkt für Punkt fast deckungsleich jener Bahnkurve, die mit gewöhnlicher, unscharfer Computer-Arithmetik für den "eigentlichen" Startwert ermittelt worden ist.

Versuche haben gezeigt, daß die normal berechnete und sozusagen "verrauschte" Bahnkurve mit dem echten Startwert über 10 Millionen Iterationen hinweg weitgehend deckungsgleich zur korrekt errechneten Kurve mit dem verschobenen Startwert bleiben kann. Wobei dies, wie erwähnt, für Rechner gilt, die beim Ermitteln der verrauschten Kurve mit 14 Dezimalstellen arbeiten.

Bedenkt man, daß die normal-unscharf errechneten Bahnkurven zweier Startwerte, die auch nur an der 14. Dezimalstelle voneinander abweichen, schon nach vielleicht 30 Iterationen zu völlig verschiedenen Werten kommen, so ist es fast schon sensationell, hier nun Kurven vorliegen zu haben, die einander über Millionen von Iterationen hinweg fast deckungsgleich folgen. Und nicht minder verblüffend ist die Beobachtung der drei Wissenschaftler, daß diese Deckungsgleichheit dennoch irgendwann ganz unversehens aufhört und fortan nie wieder erwartet werden kann; es sei denn durch Zufall - und dann auch nur für eine kurze Strecke.

An Yorkes und seiner Kollegen Experimenten ist nun interessant, daß sie vor allem eines beweisen: die irregulären und wilden Sprünge, mit denen die einzelnen Punkte bei sukzessive erfolgenden Iterationen sich quasi bewegen, sind nicht etwa nur ein Artefakt, also nicht etwa bloß das Ergebnis der unzulänglichen Technik gewöhnlicher numerischer Rechenanlagen beziehungsweise Algorithmen. Denn auch exakt berechnete Bahnkurven folgen exakt dieser exotischen Art von wildgezackten Linien.

So kennt man aus der Physik beispielsweise eine Gleichung, die das elektromagnetische Feld im Innern einer ringförmigen Laser-Struktur beschreibt und von der man auf herkömmliche, also "verrauschte" Weise schon Millionen einzelner Iterationen errechnet hat. Doch war dabei eines bislang nicht völlig klar: Ist die Tatsache, daß die Werte, die da pro Iteration errechnet werden, bevorzugt meist in der Nähe ganz bestimmter Zahlen auftreten, nun eine Folge des Rauschens infolge unscharfer Arithmetik - und mithin ein Artefakt, geboren aus den Eigenheiten der elektronischen Rechenanlage? Oder aber repräsentiert die selektive Verteilung der Punkte eben doch wahre, aus der reinen Physik der realen Welt resultierende Zusammenhänge?

Minimale Abweichungen schaukeln sich hoch

Hier nun ist natürlich Yorkes Erkenntnis interessant, es gebe eben doch auch eine völlig exakte, "wahre" Bahnkurve, die durch all' die Millionen Punkte der erwähnten Gleichung führt. Denn dies zeigt ja, daß auch bei exakter Rechnung bestimmte lokale Häufungen von Werten vorkommen, sowie, im Gegenzug, auch Stellen mit ausgesprochen wenig Punkten. Und es demonstriert auch, daß es eben doch eine völlig normale Erscheinung ist, wenn die Bahnkurvenpunkte erst über Tausende von Iterationen stets in einer gewissen numerischen Region bleiben, dann für bloß ein paar Dutzend Iterationen in eine völlig andere wandern, um anschließend wieder für Tausende von Iterationen ein weiteres "bevorzugtes" Gebiet aufzusuchen.

Zahlenfolgen, die schon bei minimal anderem Startwert eine völlig andere Gestalt annehmen, repräsentieren im Grunde nichts anderes als das typische Geschehen in der natürlichen Umwelt auch. Denn auch dort können beispielsweise minimale lokale Änderungen der Temperatur, des Luftdrucks oder auch der Windgeschwindigkeit weiträumig und langfristig zu völlig anderer Witterung führen, als zu erwarten gewesen wäre. Wie nicht nur Meteorologen wissen, sondern auch hoffungsvolle Sonntagsausflügler, die sich allzu fest auf die Fernseh-Wetterkarte verlassen haben.

Wie rasch minimale Abweichungen sich aufschaukeln können, zeigt auch der folgende Iterations-Algorithmus: Man nehme eine beliebige Zahl kleiner 1 und verdopple sie. Ist das Resultat wieder kleiner 1, so wird erneut verdoppelt; doch ist das Resultat größer 1, so wird einfach der 1 übersteigende Teil der Zahl als Ausgangswert des nächsten Iteration, also der erneuten - und fortan immer weiter fortzuführenden - Verdopplung genommen.

Dieser Algorithmus führt mit der Startzahl 1/3 zu den Folgewerten 2/3, 4/3 - beziehungsweise, nach Streichen der Ganzzahl, wieder 1/3 - und so weiter, und damit zu einer gleichbleibenden Kette aus den beiden Werten 1/3 und 2/3.

Doch setzt man bei dieser Berechnung einen Computer ein, der nur mit Dezimalbrüchen, nicht aber mit echten Brüchen arbeiten kann, so sieht die Sache völlig anders aus.

Arbeitet dieser Rechner beispielsweise nur mit zwei signifikanten Stellen, so kommt er auf die Zahlenfolge 0,33, 0,66, 1,32 (=) 0,32, 0,64, 0,28, 0,56, 0,12 und so weiter, während ein dreistelliger Rechner die Folge 0,333, 0,666, 0,332, 0,664, 0,328, 0,656, 0,312 etc. zustande bringt. Und egal, wie viel gültige Stellen man in diese Rechnung auch mit einbezieht - jedesmal erhält man eine völlig andere Bahnkurve.

Woran man sehen kann: Kleine Abweichungen in den Ausgangswerten, wie sie für die Praxis naturwissenschaftlichen Experimentierens mit ihren grundsätzlich nur begrenzt exakten Meßwerten ja geradezu normal sind, können bei iterativen Algorithmen ins Dickicht führen - und deshalb sind Arbeiten wie jene Yorkes so wichtig.