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 \frac{u\Delta t}{\Delta x} \lneq 1 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 \kappa(A)=\Vert A\Vert \Vert A^{-1}\Vert 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.

1 / 2 / 3

Kommentare (20)

  1. #1 echt?
    8. Oktober 2020

    Sehr interessant!

  2. #2 Rufus Quintex
    9. Oktober 2020

    John von Neumann, ein Experte in numerischen Berechnungen für partielle Differentialgleichungen, löste Einsteins partielles Differentialgleichungssystem numerisch nicht.

    Erst Anfang des 3ten Milleniums wurden nicht divergierende numerische Algorithmen gefunden.

    Kurz darauf wurden Gravitationswellen gefunden.

  3. #3 Fluffy
    20:22
    9. Oktober 2020

    Wer war Einst ein?
    Mal ne echte Frage, wie ist hier die Norm einer Matrix definiert?

  4. #4 Jan
    9. Oktober 2020

    @Fluffy:
    Wie für Vektoren gibt es auch für Matrizen jede Menge unterschiedliche Normen. Und wie Vektornormen sind auch Matrixnormen im endlichdimensionalen alle äquivalent, so dass es oft keine Rolle spielt, welche Matrixnorm man verwendet.

    Oft nimmt man die von einer Vektornorm induzierte Matrixnorm. Für eine Matrix A ist das das Maximum von |A x|, wobei x alle Vektoren mit |x| = 1 durchläuft.

    Wenn die Vektornorm die euklidische Norm ist und die Matrix A hermitesch ist, dann ist die induzierte Matrixnorm der Betrag des betragsmäßig größten Eigenwerts von A.

  5. #5 Fluffy
    21:48
    9. Oktober 2020

    Ich verweise mal auf die oben genannte Konditionzahl kappa = ||A|| ||A^-1||

  6. #6 Thilo
    9. Oktober 2020

    Da ist die Operatornorm gemeint, also die maximale Norm von Ax für Einheitsvektoren x. Es würde aber, wie von Jan gesagt, nur quantitativ und nicht qualitativ etwas ändern, wenn man eine andere Matrixnorm verwendet.

  7. #7 Karl-Heinz
    9. Oktober 2020

    @Fluffy

    Summennorm, euklidische Norm, Maximumsnorm, Spaltensummennorm, Zeilensummennorm, Spektralnorm, Gesamtnorm, Frobeniusnorm, Schatten-Normen, Ky-Fan-Normen

    Sag jetzt nicht, du kennst dich da aus.
    kappa = ||A|| ||A^-1||
    Oh … tust da Einheitskugel verzehren äh ich meinte verzerren. 😉

  8. #8 Karl Mistelberger
    mistelberger.net
    9. Oktober 2020

    Ein paar Ergänzungen

    Gauss schrieb an Gerling, das er ein iteratives Verfahren anwende und rühmt ausführlich die Vorteile der Methode.

    Über Stationsausgleichungen: GAUSS an GERLING 1823 Dec

    https://gdz.sub.uni-goettingen.de/id/PPN23601515X?tify=%7B%22pages%22:%5B284%5D%7D

    Richard Feynman war auch dafür bekannt, dass er ganze Bataillone von Rechnern koordinierte und motivierte. Die Männer waren im Krieg, sodass die Frauen den Job erledigten.

    John Argyris brachte sein Knowhow in die Bundesrepublik mit:

    https://www.uni-stuttgart.de/presse/archiv/uni-kurier/uk93/personalia/inmemoriam.html

    Mein PC aus 2016 hatte ca. 1000 € gekostet und leistet 250 GFLOPS, ungefähr das 100.000-fache der CDC 6700, für die Argyris in den Sechzigern US $2,370,000 (heute $19,540,000) bezahlen musste.

  9. #9 Karl-Heinz
    9. Oktober 2020

    @Rufus Quintex

    John von Neumann, ein Experte in numerischen Berechnungen für partielle Differentialgleichungen, löste Einsteins partielles Differentialgleichungssystem numerisch nicht.

    Hätte er mit den damaligen Röhren und Bipolartransistor eine Chance dazu gehabt?
    Was meinst du?

  10. #10 Thilo
    9. Oktober 2020

    Ich weiß sowieso nicht, was damit gemeint sein soll. Die Einstein-Gleichung im Vakuum? Oder zu einer völlig beliebigen Verteilung des Energie-Impuls-Tensors?

  11. #11 Karl Mistelberger
    mistelberger.net
    9. Oktober 2020

    > #9 Karl-Heinz, 9. Oktober 2020
    >> John von Neumann, ein Experte in numerischen Berechnungen für partielle Differentialgleichungen, löste Einsteins partielles Differentialgleichungssystem numerisch nicht.

    > Hätte er mit den damaligen Röhren und Bipolartransistor eine Chance dazu gehabt? Was meinst du?

    Neutronentransport ist in der Praxis ein vertracktes Problem, doch zur Not ist es auch ohne Röhren und Bipolartransistor zu lösen:

    http://static.sif.it/SIF/resources/public/files/congr15/mc/Coccetti.pdf

  12. #12 Karl Mistelberger
    mistelberger.net
    9. Oktober 2020

    Apropos: Stan Ulam, John von Neumann and the Monte Carlo Method

    http://www-star.st-and.ac.uk/~kw25/teaching/mcrt/MC_history_3.pdf

  13. #13 Fluffy
    10:22
    9. Oktober 2020

    kappa = ||A|| ||A^-1||

    Wie ist das mit nicht-hermiteschen Matrizen?

  14. #14 Thilo
    9. Oktober 2020

    Die Matrizen sind reell und invertierbar, sonst aber beliebig.

  15. #15 Karl-Heinz
    9. Oktober 2020

    @Karl Mistelberger zu #11

    Beneidenswert, die sind doch wirklich mit dem
    Monte-Carlo-Wagen zwei Jahre durch die Gegend gefahren. 😉

  16. #16 Fluffi
    9. Oktober 2020

    O.k. es sollte , anschaulich formuliert
    gemäß der üblichen Euklidischen Norm ||x||² = x* x
    X* der konjugiert komplexe Wert, analog dann für Matritzen
    ||A||² = Maximaler Eigenwert von A*.A,
    A* transponiert-konjugierte Matrix (adjungierte)
    Da A*A positiv definit ist dann
    kappa = ||A|| ||A^-1|| die Wurzel aus dem Quotienten von maximalem und minimalem Eigenwert von A*A

  17. #17 Thilo
    9. Oktober 2020

    Ein einfaches Beispiel einer nicht-Hermiteschen Matrix wäre eine Dreeicksmatrix. Nehmen wir der Einfachheit halber eine 2×2-Dreiecksmatrix mit Einsen auf der Diagonale und einer 10 rechts oben. Dann ist die Operatornorm ungefähr 10,05, also viel größer als der größte Eigenwert.

  18. #18 Rufus Quintex
    12. Oktober 2020

    Selbst John von Neumann konnte als einer der größten Mathematiker seiner Zeit Einstein’s vierdimenionales Weißgold, Einstein verschmolz die jeweils reinen Körperelemente x,y,z und i*c*t zu einem Mischkörper, nicht in ein Differenzengleichungssystem umwandeln, weil das mathematisch unmöglich ist.
    Und so mussten Arnowitt-Deser-Misner zu Lebzeiten Neumanns in den 50ern die 3+1-Zerlegung durchführen, um mit Differenzengleichungen im R3 rechnen zu können.

    Thilos folgender Satz ist richtig, wenn Differenzengleichungen gebildet werden können, was im reinen Rn immer möglich ist:

    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.

    Offtopic
    Natalia Kiriushcheva und Sergei V. Kuzmin schreiben im Artikel The Hamiltonian formulation of general relativity: myths and reality, dass die Differentialgleichungen von Einstein streng hyperbolisch (SH) aber die entsprechenden Differenzengleichungen von Arnowitt-Deser-Misner (ADM, 3+1-Zerlegung) schwach hyperbolisch (WH) sind.
    SH-Systeme konvergieren. WH-Systeme divergieren in der Regel, weswegen in ADM Nebenbedingungen (constraints) oder spezielle lapse- und shift-Funktionen verwendet werden müssen.

  19. #19 Norris Kozinski
    8. Januar 2021

    An impressive share, I just with all this onto a colleague who was doing a small analysis on this. And that he in reality bought me breakfast due to the fact I came across it for him.. smile. So permit me to reword that: Thnx for that treat! But yeah Thnkx for spending enough time to go over this, I’m strongly regarding this and enjoy reading more on this topic. When possible, as you become expertise, can you mind updating your website with additional details? It really is extremely great for me. Huge thumb up because of this short article!

    http://hfsrhjlihu.com

  20. […] Der Satz von Chern-Gauß-Bonnet Der Eilenberg-Steenrod-Eindeutigkeitssatz Die Leray-Spektralsequenz Konditionierung linearer Gleichungssysteme Das Simplex-Verfahren Das WKS-Abtasttheorem Adelische Poisson-Summation Der Vergleichssatz von […]