Die effektive Bestimmung von Näherungslösungen ist natürlich schon seit dem Altertum – damals vor allem in China und Indien – ein Thema der Mathematik. Bis ins 19. Jahrhundert entstanden numerische Methoden aber stets im Kontext technischer oder naturwissenschaftlicher Anwendungen und stellten kein eigenständiges Gebiet der Mathematik dar. Neben dem Gaußschen Eliminationsverfahren und dem Gauß-Jordan-Algorithmus zur Lösung linearer Gleichungssysteme wurden etwa zur Lösung gewöhnlicher Differentialgleichungen das Runge-Kutta-Verfahren (Einschrittverfahren) und das Adams-Moulton-Verfahren (Mehrschrittverfahren), und zur Lösung partieller Differentialgleichungen beispielsweise die Rayleigh-Ritz-Methode, die man als Vorgänger der Finite-Elemente-Methode sehen kann, entwickelt. Auch diese Verfahren entstanden jeweils im Zusammenhang mit konkreten Anwendungsgebieten, das Runge-Kutta-Verfahren etwa in der Aerodynamik. Berechnungen wurden in dieser Zeit noch mit einfachen Geräten durchgeführt.
Ersetzt man bei den klassischen linearen Differentialgleichungsproblemen der mathematischen Physik die Differentialquotienten durch Differenzenquotienten in einem rechtwinkligen Gitter, so gelangt man zu algebraischen Problemen von sehr einfacher Struktur. Diese Endliche-Differenzen-Methoden hatten u.a. in einer Arbeit von Richardson 1910 und in einer Arbeit von Courant-Friedrichs-Lewy 1928 eine Rolle gespielt. In letzterer ging es aber nicht um die Lösung praktischer Probleme, sondern um Existenz- und Eindeutigkeitsbeweise für elliptische Rand- und Eigenwertprobleme. Die Autoren bewiesen an einigen typischen Beispielen, dass der Grenzübergang stets möglich ist, also dass die Lösungen der Differenzengleichungen gegen die Lösung der entsprechenden Differentialgleichung konvergieren. Durch den Grenzübergang erhält man also insbesondere einen einfachen Beweis für die Lösbarkeit der Differentialgleichungen.
Während bei elliptischen Gleichungen einfache und weitgehend von der Wahl des Gitters unabhängige Konvergenzverhältnisse herrschen, ist beim Anfangswertproblem hyperbolischer Gleichungen – z.B. der Wellengleichung – Konvergenz im Allgemeinen nur vorhanden, wenn die Verhältnisse der Gittermaschen in verschiedenen Richtungen gewissen Ungleichungen genügen, die von der Lage der Charakteristiken zum Gitter bestimmt werden. Insbesondere bewiesen Courant-Friedrichs-Lewy, dass das explizite Polygonzugverfahren nur dann stabil (unempfindlich gegenüber kleinen Störungen der Daten) ist, wenn die Ungleichung gilt. Dabei ist u die Geschwindigkeit der Welle und die beiden anderen Größen sind der diskrete Ortsschritt und der diskrete Zeitschritt. Ähnliche Bedingungen gelten auch für andere Diskretisierungsschemata. Dieses Resultat war später sehr wichtig für die Numerik partieller Differentialgleichungen.
Die 1947 im Bulletin of the American Mathematical Society veröffentlichte Arbeit „Numerical inverting of matrices of high order“ von Goldstine und von Neumann wurde später als Beginn der numerischen linearen Algebra und überhaupt der modernen numerischen Mathematik angesehen, weil sie als eine der ersten Rundungsfehler und ihre Fortpflanzung diskutierte. In der Sache war sie hauptsächlich eine detaillierte Analyse der Rundungsfehler für Methoden der Faktorisierung und Inversion von Matrizen. Für invertierbare Matrizen A führte sie die Konditionszahl ein und zeigte, dass die Algorithmen nur für gut konditionierte Probleme brauchbare Näherungslösungen liefern.
Die Konditionszahl mißt die Abhängigkeit der Lösung von Störungen der Eingangsdaten. Probleme mit κ>1 sind schlecht konditioniert, bei κ=10k verliert man ungefähr k Stellen an Genauigkeit. Probleme mit κ=∞ bezeichnet man als schlechtgestellt. (Bei linearen Gleichungssystemen ist das der Fall, wenn die zugehörige Matrix singulär ist, also det(A)=0. Der Begriff schlechtgestellter Probleme geht auf Hadamard zurück. Er bezeichnete so Probleme, bei denen mindestens eine von drei Bedingungen nicht erfüllt ist: die Lösung existiert, ist eindeutig und hängt stetig von den Eingangsdaten ab. Letzteres bezeichnet man als Stabilität.)
Im ersten Kapitel ihrer Arbeit diskutierten Goldstine und Neumann die möglichen Fehlerquellen bei numerischen Berechnungen. In heutiger Sprache spricht man von Kondition, Stabilität und Konsistenz. Kondition beschreibt die Abhängigkeit der exakten Lösung von den Eingangsdaten, Stabilität die Abhängigkeit des Verfahrens von den Eingangsdaten und Konsistenz mißt, wie gut für hinreichend kleine Schrittweiten die Näherungslösungen (bei exakten Eingangsdaten) die tatsächlichen Lösungen approximieren. Konsistenz wird oft mit Taylor-Reihen-Entwicklungen bewiesen und in der Regel folgt aus Konsistenz und Stabilität die Konvergenz des Verfahrens. (Hingegen zeigten einige Beispiele von Courant-Friedrichs-Lewy, dass aus Stabilität eines Problems nicht notwendig die Stabilität eines leicht gestörten Problems folgt. Insbesondere folgt aus guter Konditionierung nicht unbedingt die Stabilität eines Näherungsverfahrens.)
Die numerische Stabilitätsanalyse begann ebenfalls mit von Neumann und mit einer 1947 veröffentlichten Arbeit von Crank-Nicholson über die Stabilität von Endliche-Differenzen-Verfahren zur Lösung von Differentialgleichungen.
Kommentare (20)