Wiederholung: Landau-Notation und Taylor-Entwicklung
Landau-Notation: Seien
Man schreibt
Man schreibt
Beispiel:
Satz (Taylor-Entwicklung):
Seien
Dann gilt
Motivation, Beispiele
Bemerkung: Gegeben seien eine Funktion
Beispiel: Sei
Beispiel: Die DGL
Beispiel: Eine DGL, mit der das aktuelle Bevölkerungswachstum beschrieben werden kann, lautet
Beispiel: Wird die Menge einer radioaktiven Substanz durch
Theoretische Grundlagen
Anfangswertproblem: Seien
Beispiel: Im Räuber-Beute-Modell wird mit
Existenz und Eindeutigkeit der Lösung des Anfangswertproblems
Satz (Peano): Seien
Dann hat das Anfangswertproblem auf
Satz (Picard-Lindelöf): Sei zusätzlich
Dann existiert für
Satz (Banachscher Fixpunktsatz): Seien
Behandlung von Anfangswertproblemen höherer Ordnung
Bemerkung: Ein Anfangswertproblem höherer Ordnung ist ein Anfangswertproblem der Form
Es kann in ein System 1. Ordnung umgeformt werden, indem
Beispiel: Die elastische Schwingung eines fest eingespannten Federpendels, an dem ein Körper mit Masse
Lösung durch Trennung der Variablen
Bemerkung: Eine DGL hat trennbare Veränderliche, falls sie die Form
Satz (Korrektheit der Trennung der Veränderlichen): Seien
Spezielle Typen von DGL 1. Ordnung
autonom: Eine DGL
linear: Eine DGL
Eine lineare DGL heißt homogen, falls
Satz (eindeutige Lösbarkeit linearer DGLs):
Sei
Dann hat das Anfangswertproblem genau eine Lösung in
Satz (Lösungen linearer DGLs): Unter den Voraussetzungen von eben gilt:
Die Lösungen der homogenen DGL
bilden einen -dimensionalen Unterraum mit einer Basis , , .
Die normierte Fundamentalmatrix ist .Die Lösungen der inhomogen DGL
bilden einen affinen Unterraum mit einer speziellen Lösung . Für die Lösung gilt
(dabei sei .Ist die DGL autonom, d. h. ist
, so gilt .
Beispiel:
Wegen
Beispiel: Für
Die bestehenden Möglichkeiten sind nun einerseits das Anwenden einer Quadraturformel für das Integral, zum anderen numerische Verfahren für das Ausgangsproblem.
Einzelschrittverfahren
Einzelschrittverfahren: Angenommen, das Anfangswertproblem besitzt eine eindeutige Lösung
Ein Schrittweitenvektor ist ein Vektor
Das Gitter
Das Gitter heißt äquidistant, falls
Die Gitterweite ist
Das Ziel ist die Bestimmung einer Gitterfunktion
Das Eulersche Polygonzugverfahren
Bemerkung: Zur Vereinfachung setzt man
Für die exakte Lösung
Mittels
explizites Euler-Verfahren:
Das explizite Euler-Verfahren hat die Iterationsvorschrift
Beispiel: Für
Allgemeine Definition, Beispiele
explizites Einschrittverfahren: Es seien ein Gitter
Beispiel: Im Euler-Verfahren setzt man
Man kann dies auch anders approximieren:
Dieses Verfahren nennt sich modifiziertes explizites Euler-Verfahren.
Beispiel: Ein anderes Verfahren ergibt sich wie folgt:
Das sogenannte Verfahren von Heun hat also die Iterationsvorschrift
explizites Euler-Verfahren: Die Inkrementfunktion des expliziten Euler-Verfahrens ist
modifiziertes explizites Euler-Verfahren: Die Inkrementfunktion des
modifizierten expliziten Euler-Verfahrens ist
Verfahren von Heun: Die Inkrementfunktion des Verfahrens von Heun ist
Konsistenz, Konvergenz, Stabilität, numerischer Aufwand
globale Fehlerfunktion/globaler Diskretisierungsfehler:
Die Funktion
Der globale Diskretisierungsfehler ist
lokale Fehlerfunktion/lokaler Diskretisierungsfehler:
Die Funktion
lokale Fehlerfunktion. Der lokale Diskretisierungsfehler ist
Bemerkung: Der lokale Diskretisierungsfehler gibt den Fehler an, der bei einem Schritt gemacht wird. Er kann als Differenz von der Steigung der exakten Lösung
Konvergenz: Das Einzelschrittverfahren heißt konvergent, falls
Konsistenz: Das Einzelschrittverfahren heißt konsistent zu (AWP), falls
Konsistenzordnung:
Das Einzelschrittverfahren heißt konsistent zur Ordnung
numerischer Aufwand: Der numerische Aufwand ist die Anzahl der Auswertungen von
Beispiel: Konsistenz und numerischer Aufwand der bisher betrachteten Verfahren:
explizites Euler-Verfahren:
modifiziertes Euler-Verfahren:
Verfahren von Heun:
Bemerkung: Der Aufwand pro Zeitschritt ist proportional zu
Satz (Konsistenz von Einzelschrittverfahren): Seien
Das Einzelschrittverfahren ist zu (AWP) konsistent genau dann, wenn
.Seien zusätzlich
und .
Dann ist das Einzelschrittverfahren konsistent mit der Ordnung zu (AWP) genau dann, wenn für .
Bemerkung: Was ist der Zusammenhang zwischen dem lokalen Konsistenzfehler
Raum der beschränkten Gitterfunktionen: Sei
Raum der beschränkten Gitterfunktionen.
Mit der Norm
diskreter Operator: Seien
Bemerkung:
Es gilt
Stabilität: Der Operator
Bemerkung: Sei das Einzelschrittverfahren (ESV) stabil. Dann gilt:
Die Lösung
Die Lösung
Satz (Konvergenz von Einzelschrittverfahren I):
Sei ein ESV mit Inkrementfunktion
Ist das ESV konsistent, so ist es auch konvergent.
Ist das ESV konsistent zur Ordnung
, so gilt .
Satz (Konvergenz von Einzelschrittverfahren II):
Sei ein ESV mit Inkrementfunktion
(globale Lipschitz-Bedingung an
Das ESV ist stabil.
Ist das ESV konsistent, so ist es auch konvergent.
Ist das ESV konsistent zur Ordnung
, so existiert eine Konstante , sodass für alle Gitter mit die Abschätzung gilt, wobei die Stabilitätskonstante und ist.
Bemerkung: Die Abschätzung von (iii) ist bzgl. der Stabilitätskonstanten
Beispiel: Als Beispiel betrachtet man das AWP
Satz (Konvergenz von Einzelschrittverfahren III):
Sei ein ESV mit Inkrementfunktion
(lokale Lipschitz-Bedingung an
Dann gelten (i), (ii) und (iii) aus obigem Satz:
Das ESV ist stabil.
Ist das ESV konsistent, so ist es auch konvergent.
Ist das ESV konsistent zur Ordnung
, so ist es auch konvergent zur Ordnung .
Explizite Runge-Kutta-Verfahren
Bemerkung: Seien
Kann man nun systematisch ein Einzelschrittverfahren mit Konsistenzordnung
Beispiel: Das Heun-Verfahren
explizites Runge-Kutta-Verfahren: Seien
Das Einzelschrittverfahren (ESV) mit
…,
heißt allgemeines explizites Runge-Kutta-Verfahren der Stufe
Butcher-Tableau: Die Koeffizienten eines allgemeinen Runge-Kutta-Verfahrens können in der Form einer Tabelle (Butcher-Tableau) zusammengefasst werden:
Beispiel: Das explizite Euler-Verfahren
Bemerkung: Setzt man
Beispiel: Für
Bemerkung: Man kann sich fragen, wieviele Runge-Kutta-Verfahren
Für den Fall
Es gilt
Für die Ableitung von
Aus Koeffizientenvergleich ergibt sich das nicht-lineare Gleichungssystem
Bemerkung: Allgemein muss man ein nicht-lineares Gleichungssystem lösen. Die Konsistenzordnung eines
Leider gilt i. A. nicht, dass
Bemerkung: Ein Runge-Kutta-Verfahren der Stufe
Implizite Runge-Kutta-Verfahren
Bemerkung: Man spricht von einem impliziten Einzelschrittverfahren, falls die Inkrementfunktion
Die Vorteile sind die verbesserte Stabilität und eine höhere mögliche Konsistenzordnung von bis zu
Beispiel: Das implizite Euler-Verfahren ist gegeben durch
implizites Runge-Kutta-Verfahren:
Seien
Das Einzelschrittverfahren (ESV) mit
implizites Runge-Kutta-Verfahren der Stufe
…,
erfüllt ist. Die Koeffizienten können analog zum expliziten Fall in einem Butcher-Tableau zusammengefasst werden:
Beispiel: Beim impliziten Euler-Verfahren
Das Butcher-Tableau ist folgendes:
Beispiel: Allgemeine Runge-Kutta-Verfahren der Stufe
Für die Konsistenz muss
Konkret erhält man also
da
Beispiel: implizites Runge-Kutta-Verfahren der Stufe
Bemerkung: Jedes implizites ESV lässt sich für
Beispiel: Wendet man das implizite Euler-Verfahren auf
Beispiel: Für die halbimpliziten Runge-Kutta-Verfahren gilt
…,
d. h. die einzelnen Gleichungen sind nacheinander lösbar. Das Butcher-Tableau hat dann folgende Form:
Zusammenhang zwischen Runge-Kutta-Verfahren und Quadraturformeln
Bemerkung: Der Zusammenhang zwischen Runge-Kutta-Verfahren und Quadraturformeln gibt einen weiteren Weg zur systematischen Konstruktion von Runge-Kutta-Verfahren zu einer vorgegebenen Konsistenzordnung
Bemerkung: Gegeben sei das allgemeine Runge-Kutta-Verfahren
Im Folgenden wird versucht, eine notwendige Bedingung für die Konsistenzordnung
Dies ist ein Quadraturproblem (Gewichte
Bemerkung: Das Einsetzen der exakten Lösung in das Runge-Kutta-Verfahren ergibt
Wegen der Gleichung von eben sollte für schon gegebene
Dies motiviert den folgenden Satz.
Satz (Butcher, Kunzmann, 1969): Es sei ein Runge-Kutta-Verfahren mit
für und für und .
Dann ist das Runge-Kutta-Verfahren konsistent mit der Ordnung
Exaktheit einer Quadraturformel: Es seien
Sei
(
Satz (Fehler einer Quadraturformel mit Peano-Kern): Seien
Dann gilt
Legendre-Polynom: Für
Beispiel: Es gilt
Lemma (Nullstellen und Orthogonalität der Legendre-Polynome):
Das Legendre-Polynom
besitzt paarweise verschiedene Nullstellen
mit .Für
mit gilt .
Satz (Gauß-Quadratur): Seien
Gauß-Quadraturformel mit den Stützstellen
Dann gilt
d. h. die Gauß-Quadratur ist exakt vom Grad
Bemerkung: Nun kann man analysieren, wie gut das Runge-Kutta-Verfahren ist, das durch die Gauß-Quadratur bestimmt wird. Dazu wendet man den Satz von Butcher und Kunzmann an.
Mit
, gilt
, da die Gauß-Quadratur exakt vom Grad ist. Daraus folgt
aufgrund der Beschränktheit von (bei jeder Ableitung von kommt ein Faktor hinzu). Dabei ist und für , weil .Analog wie eben ist
. Daraus folgt wieder
mit
und wegen .
Somit ergibt sich eine Konsistenzordnung von
Mehrschrittverfahren
Definitionen und Beispiele
Bemerkung: Um die Genauigkeit von Einzelschrittverfahren zu erhöhen, verwendet man nicht nur die letzte, sondern die letzten
Mehrschrittverfahren: Seien
Weiter seien
Bemerkung: Falls
Ein explizites
Bemerkung: Um die Verfahrensgleichung lösen zu können, müssen zunächst die Startwerte
lineares MSV: Falls die Verfahrensfunktion
Lineare MSV haben also die Form
Bemerkung: Auch MSV lassen sich durch Quadraturformeln herleiten. Die Integralgleichung
Beispiel: Verwendet man die Trapezregel
Bemerkung: Eine Idee für weitere Verfahren ist eine bessere Approximation der Integralgleichung durch Ersetzung des Integranden
Die Interpolationspolynome
Da man dafür allerdings die exakte Lösung
Beispiel: Ein Beispiel für ein so erhaltenes lineares
Es heißt Adams-Bashforth-Verfahren der Stufe
Bemerkung: Bei jedem Zeitschritt ist nur eine neue Auswertung von
(und zwar in
Beispiel: Ein implizites Verfahren lässt sich analog konstruieren, nur bezieht man dabei
Diese Verfahren heißen Adams-Moulton-Verfahren.
Ein Beispiel für
Bemerkung: Bei den sog. Prädiktor-Korrektor-Verfahren kombiniert man implizite und explizite Verfahren. Seien also
Man berechnen nun zuerst den Prädiktor
Man muss also keine nicht-linearen Gleichungen lösen, sondern man verwendet den Prädiktor als Schätzwert für den wahren Wert
Alternativ lässt sich der Prädiktor auch als Startwert für eine Fixpunktiteration verwenden, d. h.
Konsistenz und Konvergenz von Mehrschrittverfahren
Fehler von linearen Mehrschrittverfahren:
Es sei
Bemerkung: Die Koeffizienten
Verschwindet der Ausdruck in Klammern, so hat das Verfahren die Konsistenzordnung
Satz (Konsistenz von MSV): Falls die Koeffizienten eines linearen
Dabei ist
Bemerkung: Diese Bedingungen entsprechen einem LGS mit
Damit das Gleichungssystem nicht überbestimmt ist, soll es höchstens so viele Gleichungen wie Variablen geben. Mit der Normierungsbedingung ist dann
Bei expliziten Verfahren ist
Beispiel: Für
Stabilität von Mehrschrittverfahren
erzeugende Polynome:
Sei ein lineares
Dann heißen die Polynome
alternative Schreibweise von linearen MSV: Sei
Bemerkung: Nicht jedes konsistente lineare MSV ist konvergent. Es wird eine zusätzliche Stabilitätsbedingung benötigt.
Beispiel: Ein Beispiel für ein instabiles lineares
Sei
Für spezielle Lösungen betrachtet man die Nullstellen
Für die allgemeine Lösung setzt man
Daraus ergibt sich
Bemerkung: Die Vorgehensweise lässt sich auf allgemeine
Satz (Lösungen der homogenen Rekursion): Sei
, , …,
sind spezielle Lösungen der homogenen Rekursion.Die allgemeine Lösung der homogenen Rekursion ist eine Linearkombination der insgesamt
speziellen Lösungen aus (i).
(Für jede Nullstelle von erhält man entsprechend der Vielfachheit viele spezielle Lösungen, d. h. insgesamt viele Lösungen.)
Bemerkung: Sei
Für
stabil: Ein
Wegen der Testgleichung
stark/schwach stabil: Das
Bemerkung:
Bei konsistenten
Die Adams-Verfahren (Adams-Bashforth und Adams-Moulton) sind stark stabil, denn hier ist
Satz (Dahlquist-Barriere – maximale Konvergenzordnung stabiler linearer MSV):
Ein lineares
für gerade, für ungerade und für (insbesondere für explizite Verfahren).
Die Ordnung
Beispiel: Für
Das Adams-Bashforth-Verfahren (
Satz (Konvergenz von MSV): Falls ein lineares MSV die Konsistenzordnung
Adaptive Schrittweitensteuerung
Bemerkung: Sei ein Einzelschrittverfahren zur Lösung des Anfangswertproblems (AWP) gegeben. Für ein gegebenes Gitter
Die Aufgabe ist nun, ein Gitter
Man weiß nicht, ob
Satz (Fehlerentwicklung): Seien
Dann existiert eine Funktion
Es gibt zusätzlich eine Funktion
Bemerkung: Führt man für ein festes
Somit ist
d. h.
Man erhält also für den Fehler der halben Gitterweite die Formel
selbstadaptiver Algorithmus mit
Startschrittweite
Fehlertoleranz
Verfahrensordnung