[WS] A-Stabilität

Neue Frage »

system-agent Auf diesen Beitrag antworten »
[WS] A-Stabilität
Ein kleiner Abriss zum Thema A-Stabilität. Augenzwinkern

system-agent Auf diesen Beitrag antworten »
Die Idee der A-Stabilität und die Dahlquist-Testgleichung
Angenommen wir haben eine Differentialgleichung
mit wobei ein offenes Intervall und differenzierbar und erfüllt die Lipschitzbedingung [damit die Voraussetzung für den Existenz- und Eindeutigkeitssatz über die Lösung von Anfangswertproblemen erfüllt ist] mit der Anfangsbedigung . Sei nun die exakte Lösung des Anfangswertproblems. Wir linearisieren zunächst :

Bei (*) haben wir eine Taylorapproximation gemacht. Beachte, ist eine Konstante ! Setze nun .
Dann ist


Das bedeutet wobei die Jacobimatrix von an der Stelle ist. Nehme nun an, dass eine konstante ist [lokal ist das approximativ OK] und auch diagonalisierbar ist, dann betrachte


Auf der linken Seite steht und auf der rechten Seite steht mit obigem und da die exakte Lösung ist, gilt . Es folgt

als das neue approximative Problem. Nutzen wir nun noch, das diagonalisierbar ist, dann gibt es also eine invertierbare Matrix so, dass mit diagonal. Man kann also die Koordinaten mit der Abbildung transformieren und erhält mit


In jeder Komponente bleibt nun also eine Gleichung der Form

stehen mit einer Zahl [hier ist wieder eine skalare Funktion].

Man nennt die Gleichung
wobei und eine differenzierbare Funktion mit Anfangsbedingungen die Dahlquist Testgleichung.

In der obigen Diskussion hat man viele Annahmen gemacht, wie zum Beispiel dass man die Jacobimatrix als eine konstante Matrix ansieht und dass die Jacobimatrix diagonalisierbar ist. Das sind Annahmen um alles einfacher zu gestalten. Ich weiss allerdings nicht, ob es sinnvoll ist alles ohne diese vielen Annahmen zu betrachten, also ob man dann noch brauchbare Aussagen ableiten kann.
system-agent Auf diesen Beitrag antworten »
Was passiert nun mit der Numerik?
Betrachten wir zunächst das explizite Eulerverfahren. Es ist für das Anfangswertproblem mit gegeben durch

und eine konstante Schrittweite. Wende nun das Verfahren auf die Dahlquist Testgleichung an:


Da in der Testgleichung folgt


Die exakte Lösung der Testgleichung ist bekanntlich

für alle . Zerlege nun in den Real- und Imaginärteil , dann bekommt man

Da [Einheitskreis !!] entscheidet also der Realteil von darüber, ob die exakte Lösung explodiert oder nicht. Genauer: Falls gilt für und für ist beschränkt für .

Man will nun, dass die numerische Lösung beschränkt bleibt falls die exakte Lösung beschränkt bleibt. Im Fall des expliziten Euler-Verfahrens hatte man

und das bleibt beschränkt falls . Setze zur Vereinfachung , dann bekommt man

und man nennt die Stabilitätsfunktion [des betrachteten Verfahrens].

Wir haben gesehen, dass für die exakte Lösung beschränkt bleibt und die numerische für .
Man nennt die Menge

das Stabilitätsgebiet eines Verfahrens. Beachte: Das ist die korrekte Definition des Stabilitätsgebietes für explizite Runge-Kutta Verfahren !!! Für lineare Mehrschrittverfahren wird leicht anders definiert [dort ist dann diese Definition mit enthalten]. Definiere noch die "linke Halbebene" in .


Die Idee nochmals kurz zusammengefasst:
Man findet eine sehr einfache Gleichung [die Dahlquist Testgleichung] und untersucht wann ein numerisches Verfahren bei dieser Gleichung unbeschränkte numerische Lösungen produziert. Da die Gleichung aus sehr allgemeinen Betrachtungen gewonnen wurde ist die Meinung, dass wenn das Verfahren bei der Testgleichung diese unerwünschten numerischen Lösungen produziert, dann auch bei anderen Gleichungen.
system-agent Auf diesen Beitrag antworten »
Was ist also A-Stabilität?
Wie schon gezeigt bleibt die exakte Lösung beschränkt, falls , also gerade für .

Hingegen ist die numerische Lösung beschränkt falls . Da man nun haben will, dass die numerische Löung beschränkt bleibt falls es die exakte Lösung ist, definiert man:

Ein numerisches Verfahren heisst A-Stabil falls , also wenn das Stabilitätsgebiet des Verfahrens die ganze linke Halbebene enthält.

Nochmals:
Die numerische Lösung eines A-Stabilen Verfahrens bleibt beschränkt, für jeden Wert von , da falls hat man weiter oben gesehen, dass es sowieso immer beschränkt bleibt und falls ist in , also eben auch in wegen der A-Stabilität, genau dem Stabilitätsgebiet des Verfahrens und dort bleibt die numerische Lösung schliesslich auch beschränkt !
system-agent Auf diesen Beitrag antworten »

Ist ein Verfahren A-Stabil, dann ist die Schrittweite mit der man arbeitet nicht so wichtig, denn dann ist immer noch entweder in [wo sich jede Diskussion erübrigt hat] oder in und das ist im Stabilitätsgebiet enhalten, also dem Gebiet, in welchem die numerische Lösung ebenfalls beschränkt ist.

Nun wie sieht aus im Falle des expliziten Eulerverfahrens? Es muss gelten , also und das ist genau ein Kreis um -1 mit Radius 1 in der komplexen Ebene. Also kann niemals gelten für explizit Euler !
Falls zum Beispiel , dann muss man mindestens so klein wählen, dass gilt, also und das ist der Fall für .

Im angehängten Plot sieht man zuerst einmal was passiert mit einer Schrittweite von und beim zweiten Bild mit . Beide male gibt es zwar Oszillationen, das liegt an der überhaupt sehr grossen Schrittweite, aber beim zweiten Bild sieht man, dass es "entlang" der exakten Lösung geht und vor allen Dingen dass die numerische Lösung beschränkt bleibt, ganz anders als beim ersten Bild !
system-agent Auf diesen Beitrag antworten »
Was ist mit implizit Euler?
Nun werden wir zuerst einmal das implizite Eulerverfahren ausprobieren ! Das implizite Eulerverfahren ist

Wenden wir es nun auf die Dahlquist Testgleichung an:

Mit folgt

wobei wieder ist. Also ist die Stabilitätsfunktion


Die Menge aller mit ist wie man nachrechnen kann ein Kreis mit Radius 1 um 1. Also wird in zwei Gebiete zerteilt, einmal der Kreis um 1 und das Komplement davon. Das bedeutet entweder ist das innere dieses Kreises oder das Komplement. Da

muss das Komplement des Kreises sein und daher gelten. Es folgt dass das Verfahren A-Stabil ist!

[Beachte: oben habe ich gesagt dass die gegebene Definition von die richtige ist für explizite Runge-Kutta Verfahren. Wir können sie hier auch für implizit Euler anwenden, denn wenn man das Verfahren auf die Testgleichung anwendet, dann bekommt man ein Ausdruck der Form

also bestimmt hier auch die Funktion darüber, ob die numerische Lösung explodiert oder nicht.
Natürlich geht das so nicht mehr, falls man Mehrschrittverfahren hat !]

Als Interpretation davon dass das implizite Eulerverfahren A-Stabil ist sei gesagt, dass man also beim lösen der Testgleichung nicht auf die Schrittweite aufpassen muss, damit die numerische Lösung beschränkt bleibt !
 
 
system-agent Auf diesen Beitrag antworten »
Wie findet man R(z) ?
Bisher war es recht mühsam die Stabilitätsfunktion zu finden, aber für explizite Runge-Kutta-Verfahren erledigt das ein kleines Lemma:

Zitat:
Lemma:
Nehmen wir ein explizites Runge-Kutta-Verfahren mit dem Butcher-Schema wobei die Koeffizientenmatrix ist [im expliziten Fall ist es eine untere Dreiecksmatrix mit Nullen auf der Hauptdiagonalen]. Dann gilt: wobei die Einheitsmatrix ist und der "Einsvektor".



Beispielsweise ist für das Verfahren von Runge mit dem Butcher-Schema

gerade

und mit Nachrechnen bekommen wir


Ist dieses Verfahren von Runge auch A-Stabil?
Für betrachte für und man stellt fest, dass , also sicher bleibt es nicht kleiner als 1 für grosse negative reelle Werte. Da aber alle negativen reellen Werte auch in liegen, kann niemals gelten, was auch immer genau sein mag. Also ist das Verfahren von Runge nicht A-Stabil.

Allgemeiner kann man zeigen, dass alle expliziten Verfahren nicht A-Stabil sind!


Lassen wir auch implizite Runge-Kutta Verfahren zu [das heisst die Koeffizientenmatrix darf voll besetzt sein], dann kann man das obige Lemma allgemeiner formulieren:

Zitat:
Lemma:
Sei das Runge-Kutta Verfahren mit dem Butcher-Schema gegeben. Dann gilt:

wobei wieder die Einheitsmatrix ist und der "Einsvektor".


Als einfaches Beispiel betrachten wir das Gauss-Verfahren mit Butcher-Schema

Dann ist der Zähler gleich

und der Nenner gleich


Es folgt und das Verfahren ist A-Stabil.
Da die Trapezregel

die gleiche Stabilitätsfunktion besitzt wie das Gauss-Verfahren, ist sie auch A-Stabil.
system-agent Auf diesen Beitrag antworten »
A-Stabilität für lineare Mehrschrittverfahren
Ein lineares Mehrschrittverfahren für Schritte kann man in der Form

mit gewissen Koeffizienten und schreiben [Bemerke: für ein explizites Verfahren ist immer ].

Wir definieren noch zwei Polynome die zu einem gewissen Verfahren gehören:

und


Diese Polynome dürften schon bekannt sein aus der Frage nach der Konsistenz von linearen Mehrschrittverfahren.
system-agent Auf diesen Beitrag antworten »
Lineares Mehrschrittverfahren und die Testgleichung
Nun werden wir untersuchen was passiert, wenn man das lineare Mehrschrittverfahren

auf die Dahlquist Testgleichung anwendet.

Es ist mit

also

Nun ist fest [das heisst durch die konkrete Wahl in der Testgleichung festgelegt] und wir wollen diese lineare Differenzengleichung lösen. Wir setzen und damit bekommt man


Wir sind an der nichttrivialen Lösung der Differentialgleichung interessiert, also nehmen wir an, dass und wir können dividieren:


Bemerke noch, dass mit den obigen Definitionen der charakteristischen Polynome hier gerade

steht !

Mit einem Satz über lineare Differenzengleichung folgt, dass die gesuchte numerische Lösung von der Form

ist, wobei () die Nullstellen des Polynoms

sind und die sind Koeffizienten. Beachte die hervorgehobene Abhängigkeit der Koeffizienten und der Nullstellen des Polynoms vom "Parameter" bzw. . Das bedeutet für jeden Wert von bekommt man andere Nullstellen und dazu passende Koeffizienten.
system-agent Auf diesen Beitrag antworten »
Definition Stabilitätsgebiet & A-Stabilität für lineare Mehrschrittverfahren
Man sieht von der obigen Diskussion, dass die numerische Lösung beschränkt bleibt, falls alle Nullstellen betragsmässig kleiner als 1 sind. Die Nullstellen hängen aber vom gewählten ab. Setzen wir noch dann definiere das Stabilitätsgebiet eines linearen Mehrschrittverfahrens als


Auch hier heisst das lineare Mehrschrittverfahren A-Stabil, falls .
system-agent Auf diesen Beitrag antworten »
Theorem: Explizite Verfahren
Mit dieser Definition kann man schon etwas über das Stabilitätsgebiet beweisen:

Zitat:
Theorem:
Falls das lineare Mehrschrittverfahren explizit ist, dann ist beschränkt.


Das bedeutet insbesondere, dass niemals die unbeschränkte Menge in enthalten sein kann, also das Verfahren nicht A-Stabil ist.
Anders ausgedrückt ist jedes explizite Runge-Kutta Verfahren nicht A-Stabil und wenn man mit einem solchen Verfahren eine Differentialgleichung löst muss man aufpassen, dass man die Schrittweite klein genügend nimmt, da ansonsten die numerische Lösung unbeschränkt ist [bzw sehr wahrscheinlich ist dass so etwas passiert].
system-agent Auf diesen Beitrag antworten »
Wie zeichnet man das Stabilitätsgebiet?
Nun gehen wir der Frage nach, wie man das Stabilitätsgebiet zeichnen könnte. Bemerke, dass die Nullstellen vom Polynom stetig vom Parameter abhängen. Mit dieser Bemerkung kann man nun weiter machen:

Wir betrachten den Rand des Stabilitätsgebietes . Für ein muss es also ein geben so, dass , da für alle Punkte innerhalb von immer gilt und für alle Punkte ausserhalb von immer . Dieses ist eine Nullstelle, also erfüllt es die Gleichung

Also gibt es ein so, dass und damit auch

oder

Da man das für jedes machen kann folgt das Lemma:

Zitat:
Lemma:
Sei der (geschlossene) Weg

Dann gilt .


Man nennt die Root Locus Curve. Das Lemma sagt also, dass man die Root Locus Curve zeichnen soll und diese zerlegt in gewisse Gebiete [da die Kurve geschlossen ist]. Nun kann man aus jedem der Gebiete einen Punkt nehmen und testen was mit den Nullstellen von passiert. Falls alle Nullstellen betragsmässig kleiner als 1 sind und alle mehrfachen Nullstellen betragsmässig echt kleiner als 1 sind, dann gehört das gerade betrachtete, von begrenzte, Gebiet zu . Falls man aber eine Nullstelle findet die das nicht erfüllt, dann gehört es zu .
system-agent Auf diesen Beitrag antworten »

Betrachten wir das Verfahren

Dieses Verfahren hat die charakteristischen Polynome

und


Ein Bild der Spur vom Weg ist im Anhang angehängt. Man sieht dass die komplexe Ebene in zwei Komponenten zerlegt und mit dem Lemma wissen wir, dass eine davon ist. Also nehme zum Beispiel und bestimme mit zb. MatLab die Nullstellen des Polynoms

und wir finden dass es eine Nullstelle vom Betrag grösser als 11 hat. Das heisst kann nicht in liegen und daher ist das "äussere" Gebiet. Insbesondere sieht man, dass , also das Verfahren tatsächlich A-Stabil ist.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »