Numerik von ESV (1)

17.07.2009, 03:41

tigerbine

Numerik von ESV (1)

So, versuche nun mal meine Gedanken zu diesem Thema zu sortieren. Wäre nett, wenn sich ein "Gesprächspartner" finden würde. Augenzwinkern

Ziel: numerische Lösung des AWPs

$\begin{eqnarray*} y' = f(x,y),~y(x_0) = y_0 \end{eqnarray*}$

Gleich mal eine Frage zur Notation. Warum steht beim f ein "x drinnen", bei y aber nicht? Weil es um die Funktion y' "an sich geht? Und f (.,.) soll eine Verkettung von Funktionen ausdrücken? Ist "x" dann die Identität und man muss es halt so schreiben um es kenntlich zu machen?

Wie arbeitet nun so ein ESV? Ich schreibe mal die Vorschrift (*) hin:

$\begin{eqnarray*} \eta_0 :=y_0 \end{eqnarray*}$

$\begin{eqnarray*} \eta_{i+1} :=\eta_i + h \cdot \Phi(x_i,\eta_i;h;f) \end{eqnarray*}$

$\begin{eqnarray*} x_{i+1}:=x_i+h \end{eqnarray*}$

Das liefert dann Wertepaare $\begin{eqnarray*} (x_i, \eta_i) \end{eqnarray*}$ die als Approximation für $\begin{eqnarray*} (x_i,y(x_i)) \end{eqnarray*}$ angesehen werden können. Dabei nennt man $\begin{eqnarray*} \Phi \end{eqnarray*}$ die Verfahrensfunktion, und da man nur auf einen Vorgängerwert zurückgreift das ganze eben ESV. Nun ist das typische Einstiegsbeispiel das Eulersche Polygonzugverfahren (=explizites Eulerverfahren?).

Nun werden in den Bildern zu dem Verfahren gerne die mit (*) berechneten Punkte linear verbunden. Das steht aber so doch nicht in der Berechnungsvorschrift. Macht man das also immer so? Würde ja Sinn machen, da man die Approximationsfunktion nutzen will, um die eigenliche Funktion y an beliebigen Stellen auswerten zu können, oder?

Wenn man also so etwas programmieren würde, würde man eine stückweise lineare Funktion (lin. Spline) abspeichern?

Problem: Wahl der Verfahrensfunktion

Das wirft gleich einmal ein paar Fragen auf:

Wie misst man die Güte des Verfahrens?
Wie klein muss man h wählen um gute Näherungen zu erhalten und bringt Verkleinerung von h immer Verbessung?
Hängt die Güte des Verfahrens von der gesuchten Funktion y ab?

Zitat:

... Sei nun y(x) die exakte Lösung des AWP... (z.B. Stoer-Burlisch 2)

Hier bin ich verwirrt (ja, nicht nur hier ). Warum wird die gesuchte Lösungsfunktion plötzlich in dieser Notation angegeben? Gerade hier müßte es doch um die Funktion an sich gehen, und so steht da der Wert an der Stelle x?

lokaler Diskretisierungsfehler

$\begin{eqnarray*} y_i :=y(x_0+ih) \end{eqnarray*}$

$\begin{eqnarray*} \tau_i:=\tau(x_i,y_i;h):&&=\frac{1}{h} \left(y_{i+1}-y_i - h \Phi \left( x_i,y_i;h \right) \right) &&=\frac{1}{h}\left(y_{i+1}-\left(y_i + h \Phi \left( x_i,y_i;h \right) \right) \right) \end{eqnarray*}$

D.h. Ich betrachte die Differenz des wahren Wertes in $\begin{eqnarray*} x_{i+1} \end{eqnarray*}$ und dem Wert, den das Verfahren liefern würde, wenn ich in einem exaktem Punkt starte. Warum wird das noch durch h geteilt?

Was wird man von einem Verfahren fordern? Dass dieser Fehler für $\begin{eqnarray*} h \to 0 \end{eqnarray*}$ gegen 0 geht? Wenn das für alle Punkte x aus [a,b] gilt nennt man das Verfahren konsistent? Warum nicht "konvergent"?

(Konsistenz)Ordnung eines ESV

$\begin{eqnarray*} |\tau_i| \leq c \cdot h^p \quad \text{ für } y \in C^{p+1}([x_0,b])^h \end{eqnarray*}$

Hier ist dann also die Frage, wie schnell das Verfahren "konvergiert"?

Bestimmmung der Konsistenzordnung

Hier kommt ja immer das Stichwort "Taylorentwicklung" ins Spiel. Woher weiß ich denn nun, wie weit ich entwickeln muss/kann/soll?

... to be continued.... answers welcome... Schläfer

17.07.2009, 10:06

Dunkit

Auf diesen Beitrag antworten »

Guten Morgen!
Wie du ja vllt weißt habe ich mich in den letzten Semestern auch ein wenig mit Numerik beschäftigt. Daher verwudnert es mich etwas, dass ich doch nicht auf alle deine Fragen auf Anhieb exakte Antowrten weiß, aber ich möchte es trotzdem versuchen. Gemeinsam werden sich hier dann schon alle Antworten ergeben...

Zu der Notationsfrage: Ich denke das ist tatsächlich nur eine "Abkürzung". y' hängt ja sicherlich auch von x ab und f eben von x und y, wobei man vllt ganz korrekt schreiben müsste(?): $\begin{eqnarray*} y'(x) = f(x,y(x)) \end{eqnarray*}$

Zitat:

Nun ist das typische Einstiegsbeispiel das Eulersche Polygonzugverfahren (=explizites Eulerverfahren?).

Nein, es gibt auch ein implizites Eulersches Polygonzugverfahren. Während das explizite EPV ja auf dem vorwärts genommenen Differenzenquotienten basiert, basiert das implizite EPV auf dem rückwärts genommenen Differenzenquotienten. Die Verfahrensvorschrift ist dann
$\begin{eqnarray*} \eta_{i+1} = \eta_i + hf(x_{i+1}, \eta_{i+1}) \end{eqnarray*}$ .
Hierbei muss man dann natürlich entweder in jedem Schritt eine (i.A.) nicht-lineare Gleichung lösen, um an $\begin{eqnarray*} \eta_{i+1} \end{eqnarray*}$ zu kommen, oder man verwendet den sog. Prädiktor-Korrektor Ansatz. (genauere Erläuterung auf Nachfrage Augenzwinkern

Zitat:

Nun werden in den Bildern zu dem Verfahren gerne die mit (*) berechneten Punkte linear verbunden. Das steht aber so doch nicht in der Berechnungsvorschrift. Macht man das also immer so? Würde ja Sinn machen, da man die Approximationsfunktion nutzen will, um die eigenliche Funktion y an beliebigen Stellen auswerten zu können, oder?

Was man aus den ausgerechneten diskreten Werten der Funktion mach hängt sicherlich davon ab, was man mit dem Ergebnis überhaupt anfangen will. Das Erstellen eines Streckenzuges erscheint mir bei hinreichend vielen Punkten (d.h. hinreichend kleinem h) auch sinnvoll. Theoretisch könnte ich mir aber auch vorstellen, die Lösung durch Interpolation der berechneten Punkte zu bekommen. Bei vielen Punkten eignet sich hier sicher nciht die Polynominterpolation, aber vielleicht andere Verfahren wie zB (je nach Aufgabe) trigonometrische Interpolation oder kubische Splines etc.

Zitat:

Wie misst man die Güte des Verfahrens?

Die Güte eines Verfahrens hängt von der Konvergenzordnung ab (und natürlich dem Rechenaufwand, der dafür betrieben werden muss). Soll heißen i.d.R. bevorzugt man Verfahren mit hoher Konvergenzordnung gegenüber denen mit niedriger Konvergenzordnung, da man bei solchen Verfahren meist sehr viele Iterationen durchführen muss. Mein Prof sprach mal davon, dass ein Verfahren schon mindestens Konvergenzordnung 4 haben sollte.

Zitat:

Wie klein muss man h wählen um gute Näherungen zu erhalten und bringt Verkleinerung von h immer Verbessung?

Bei ESV bringen kleinere Werte von h immer Verbesserungen, die Frage ist halt nur, ob es den zusätzlichen Rechenaufwand Wert ist. Wie gut die Verbesserung ist, hängt natürlich auch wieder von der Konvergenzordnung hab. Habe ich ein Verfahren mit Konvergenzordnung 2 und halbiere die Schrittweite h, wird sich der Fehler um den Faktor 1/4 verringern. Wann eine Näherung nun hinreichend gut ist, hängt natürlich auch maßgeblich von der Anwendung ab.
Ob es in dieser Richtung irgendwelche Fehlerabschätzungen gibt (wie bei iterativen Lösungsverfahren von LGS zum Beispiel) kann ich dir so auf Anhieb leider nicht sagen.

Zitat:

Hängt die Güte des Verfahrens von der gesuchten Funktion y ab?

Ich weiß nicht, ob du das meinst, aber ich kann dir sagen, dass die Güte eines solchen Verfahrens mit Sicherheit von der Glattheit der Lösung abhängt. Betrachtet man zum Beispiel das Eulersche Polygonzugverfahren wird recht schnell klar, dass wenn die Lösung sehr "wild" ist, auch der Fehler recht groß werden kann. Die Glattheit der Lösung hängt natürlich auch von der Glattheit der rechten Seite f ab...

Zitat:

Zitat: ... Sei nun y(x) die exakte Lösung des AWP... (z.B. Stoer-Burlisch 2)

Ja, das ist in der Tat verwirrend. Ist vielleicht wirklich eine Unregelmäßigkeit in der Notation. Wo steht das denn? Bzw welche Ausgabe des Buches hast du, dann kann ich mal mit meiner vergleichen...

Nun zu deinem letzten Block "Konsistenz": Man wird von einem Verfahren sicherlich fordern, dass der lokale Diskretisierungsfehler für $\begin{eqnarray*} h \to 0 \end{eqnarray*}$ gegen 0 geht. Dann nennt man das Verfahren Konsistent. Man stelle sich vor, der lokale Fehler ginge nicht gegen 0: Wie sollte dann der globale Fehler gegen 0 gehen? Wenn der globale Fehler gegen 0 geht, nennt man das Verfahren konvergent. Man kann zeigen, dass für ESV (ACHTUNG: Nicht für Mehrschrittverfahren) Konsistenz p-ter Ordnung äquivalent ist zur Konvergenz p-ter Ordnung. Das Schöne: Die Konsistenz ist einem direkt zugänglich (zB über Taylor-Entwicklung). Kann man also die Konsistenzordnung eines ESV bestimmen, so liefert das die Konvergenzordnung gleich mit! Bei MSV hingegen kommen noch Stabilitätsbedingungen ins Spiel.

So, ich hoffe ich konnte fürs erste weiterhelfen und warte auf eine anregende Diskussion ;-)

Gruß,
Fabian

17.07.2009, 12:50

tigerbine

Auf diesen Beitrag antworten »

Zitat:

Original von Dunkit
Guten Morgen!
Wie du ja vllt weißt habe ich mich in den letzten Semestern auch ein wenig mit Numerik beschäftigt. Daher verwudnert es mich etwas, dass ich doch nicht auf alle deine Fragen auf Anhieb exakte Antowrten weiß, aber ich möchte es trotzdem versuchen. Gemeinsam werden sich hier dann schon alle Antworten ergeben...

Finde ich super!

Zitat:

Zu der Notationsfrage: Ich denke das ist tatsächlich nur eine "Abkürzung". y' hängt ja sicherlich auch von x ab und f eben von x und y, wobei man vllt ganz korrekt schreiben müsste(?): $\begin{eqnarray*} y'(x) = f(x,y(x)) \end{eqnarray*}$

Das ist halt die Frage. Wenn man mal den Thread Die ewigen Mathe-Fehler heranzieht ist hier nun die Frage, was die Gleichung sagen soll: Die Funktion y' ist gleich der Funktion f(x,y) oder man kann die Abbildungsvorschrift von y', also y'(x) durch f(x,y(x)) darstellen? Oder eben nur, dass in einem Punkt x aus [a,b] eben diese Gleichung gilt.

Das wäre alles imho noch vertretbar und sinnvoll. Nur was ist eigentlich gesucht? Doch eine Funktion. Und die heißt y und nicht y(x). Da es später auftauchte: Quelle ist der Stoer-Burlisch 5. Auflage. Wird in meinem Skript aber genauso gemacht.

Zitat:

Nun ist das typische Einstiegsbeispiel das Eulersche Polygonzugverfahren (=explizites Eulerverfahren?).

Hier mißverstehst du mich ggf. Ich wollte wissen, was sich hinter dem Namen "Eulersches Polygonzugverfahren" verbirgt. Wieder in meinem Buch Skript ist das imho das explizite Eulerverfahren. Das es ein implizites gibt weiß ich, bin bei meiner Nachbearbeitung noch nicht da. Augenzwinkern

Zitat:

Also speichert so ein Verfahren nur die Datenpaare. Nach meinem Wissen über Polynominterpolation würde ich ja eher einen Spline durchlegen. Aber ok, das wäre, je nach dem was also so als "Datenkurve" rauskommt also eine neue Aufgabe

Zitat:

Wie misst man die Güte des Verfahrens?

Die Güte eines Verfahrens hängt von der Konvergenzordnung ab

Dier Begriff der Konvergenzordnung taucht bei mir nun nicht auf, sondern nur konvergent und von der Konsistenzordnung. Könntest du da mal die beiden Definitionen bei dir vergleichen?

Zitat:

Wie klein muss man h wählen um gute Näherungen zu erhalten und bringt Verkleinerung von h immer Verbesserung?

Ok, hier also "theoretisch" ggf Konvergent aber praktisch kann man lange darauf warten. Oder es treten z.B. numerische Probleme auf.

Zitat:

Hängt die Güte des Verfahrens von der gesuchten Funktion y ab?

Zitat:

Nun zu deinem letzten Block "Konsistenz": Man wird von einem Verfahren sicherlich fordern, dass der lokale Diskretisierungsfehler für $\begin{eqnarray*} h \to 0 \end{eqnarray*}$ gegen 0 geht. Dann nennt man das Verfahren Konsistent. Man stelle sich vor, der lokale Fehler ginge nicht gegen 0: Wie sollte dann der globale Fehler gegen 0 gehen? Wenn der globale Fehler gegen 0 geht, nennt man das Verfahren konvergent. Man kann zeigen, dass für ESV (ACHTUNG: Nicht für Mehrschrittverfahren) Konsistenz p-ter Ordnung äquivalent ist zur Konvergenz p-ter Ordnung. Das Schöne: Die Konsistenz ist einem direkt zugänglich (zB über Taylor-Entwicklung). Kann man also die Konsistenzordnung eines ESV bestimmen, so liefert das die Konvergenzordnung gleich mit! Bei MSV hingegen kommen noch Stabilitätsbedingungen ins Spiel.

Ich denke dieser Absatz ist gerade wichtig für mich. Sind die nächsten Seiten im Buch, damit werde ich mich heute Abend beschäftigen. Aber da habe ich gleich mal die Frage nach einem einfachen Beispiel. Also konsistent aber nicht konvergent

Lieben Gruß,
..bine

17.07.2009, 13:54

Dunkit

Auf diesen Beitrag antworten »

Hi,

also die Notationsfrage ist wohl eher eine allgemeine (bzw eine DGL) Sache. Leider war mein Prof da immer etwas schlampig. Ich würde intuitiv aber immer $\begin{eqnarray*} y'(x) = f(x,y(x)) \end{eqnarray*}$ schreiben. Ich bitte aber um Aufklärung, ob das vllt garnicht dem Sachverhalt entspricht...

Bei dem eulerschen Polygonzugverfahren habe ih dich tatsächlich missverstanden. Wenn mir jemand "Eulersches Polygonzugverfahren" sagt denke ich auch zunächst an das explizite, ob es Menschen gibt, die darunter gleich das implizite oder beide verstehen, weiß ich nicht Augenzwinkern

Zur Konvergenzordnung:
Man definiert sich den globalen Diskretisierungsfehler als
$\begin{eqnarray*} e(x,h) = e(x,h) := u(x) - \eta(x,h) \end{eqnarray*}$ , wobei $\begin{eqnarray*} u \end{eqnarray*}$ die exakte Lösung des AWP ist.

Außerdem definiert man
$\begin{eqnarray*} e^*(h) := \sup_{x \in \overline{\Omega}_h} |e(x,h)| \end{eqnarray*}$
(ich hoffe die Notationen erklären sich von selbst, sonst bitte nachfragen!)
Soviel zur Vorbereitung.
Definition (Konvergenz, Konvergenzordnung): Das Verfahren heißt nun konvergent, falls
$\begin{eqnarray*} e^*(h) \to 0, h\to 0 \end{eqnarray*}$
Das Verfahren heißt konvergent von der Ordnung $\begin{eqnarray*} p \end{eqnarray*}$ , falls
$\begin{eqnarray*} e^*(h) = O(h^p) \end{eqnarray*}$

Als Bemerkung haben wir dann notiert, dass Konvergenz und Konsistenz bei ESV äquivalent sind.
Bei MSV kann es aber passieren, dass die Konvergenzordnung unter der Konsistenzordnung (nie darüber!) liegt bzw dass das Verfahren zwar konsistent aber nicht konvergent ist.

Als Beispiel für ein nicht-konvergentes, aber konsistentes MSV gebe ich einfahc mal eins aus unserer VL, wenn ich ein eigenes mache geht das eh schief ;-)
Die Verfahrensvorschrift sei $\begin{eqnarray*} \eta_{j+2} + 9 \eta_{j+1} - 10 \eta_{j} = \frac{h}{2}(13f_{j+1} + 9 f_j) \end{eqnarray*}$ (Anm. $\begin{eqnarray*} f_j = f(x_j) \end{eqnarray*}$ )
Offensichtlich handelt es sich um ein lineares 2-Schritt-Verfahren. Es ist explizit und hat Konsistenzordnung 2 (das kann man mit sonem Satz recht schnell zeigen). Angewandt auf das AWP
$\begin{eqnarray*} u' \equiv 0 \end{eqnarray*}$
$\begin{eqnarray*} u(0) = 1 \end{eqnarray*}$
ergibt sich dann aber mit Schrittweite $\begin{eqnarray*} \epsilon h^2 \end{eqnarray*}$ :
$\begin{eqnarray*} \eta_j = 1+ \frac{1}{11}\epsilon h^2 - \frac{1}{11} \epsilon h^2 (-10)^j \end{eqnarray*}$
Damit hast du einen oszillierenden Term ganz am Ende und das ganze Verfahren kann garnicht konvergieren...

17.07.2009, 22:12

tigerbine

Auf diesen Beitrag antworten »

Zitat:

Original von Dunkit
Hi,

also die Notationsfrage ist wohl eher eine allgemeine (bzw eine DGL) Sache. Leider war mein Prof da immer etwas schlampig. Ich würde intuitiv aber immer $\begin{eqnarray*} y'(x) = f(x,y(x)) \end{eqnarray*}$ schreiben. Ich bitte aber um Aufklärung, ob das vllt garnicht dem Sachverhalt entspricht...

Das müssen wir wohl in einem neuen Thread klären.

Das mit der Konvergenzordnung werde ich mir nun mal durchlesen und auch im Buch weiter machen und dann meine Fragen einstellen.

18.07.2009, 01:37

tigerbine

Auf diesen Beitrag antworten »

Bestimmmung der Konsistenzordnung

Vorab einmal. Die Verfahrensfunktion $\begin{eqnarray*} \Phi \end{eqnarray*}$ beinhaltet doch die Funktion f aus der Differentialgleichung.

$\begin{eqnarray*} y' = f(x,y) \end{eqnarray*}$ (*)

Also hängt das Verfahren ja von der "Differentialgleichung" ab. Wieso kann ich dann, ohne f zu kennen, die Ordnung eines Verfahrens angeben? Ferner woher weiß ich denn (ohne Angabe) wie oft f stetig differenzierbar ist? Ich nehme hier mal das explizite euer-Verfahren als Beispiel und zitiere:

Zitat:

$\begin{eqnarray*} \Phi(x,y;h):=f(x,y) \end{eqnarray*}$

$\begin{eqnarray*} \tau_i\stackrel{0}:=\tau(x_i,y_i;h):&&=\frac{1}{h} \left(y_{i+1}-y_i - h \Phi \left( x_i,y_i;h \right) \right) && \stackrel{1}=\frac{1}{h}\left(y_{i+1}-hf(x_i,y_i) \right) && \stackrel{2}= \frac{1}{h}(y_i + hf_i+\frac{1}{2}h^2(f_{x,i}+f_{y,i}f_i)+O(h^3)-y_i-hf_i) && \stackrel{3}= \frac{1}{2} h (f_{x,i} + f_{y,i}f_i) + O(h^2) \end{eqnarray*}$

Also p=1 für explizites Eulerverfahren

Das habe ich nun nicht so richtig verstanden. Also (0) ist die Definition. (1) ist das Einsetzen der Verfahrensfunktion. Was wird dann gemacht? Wir haben vorher auch noch eine wilde Rechnung zur Taylorentwicklung.

$\begin{eqnarray*} y_{i+1} = y_i + h y_i' + \frac{1}{2}h^2y_i'' + \frac{1}{6}h^3y_i''' + O(h^4) \end{eqnarray*}$ (**)

Da Frage ich mich, warum sollte y denn so oft differenzierbar sein? Aufgrund von (*) kann ich doch mal höchstens 1mal differenzierbar annehmen. verwirrt

Gut, in der Definition der Ordnung steckt ja die Annahme über die Differenzierbarkeit drinnen. D.h. also wenn ich sage, ein ESV hat die Konsistenzordnung 5, dass ich damit voraussetze im Untertitel "für $\begin{eqnarray*} f \in C^{5} \end{eqnarray*}$ . Ist aber schon was seltsam, will ich mit dem Verfahren doch gerade eine unbekannte Funktion y annähern.... verwirrt

Aber woher weiß ich denn bei einem Verfahren, wie weit ich entwickeln muss? Ferner nervt mich dass es nun plötzlich $\begin{eqnarray*} y_i \end{eqnarray*}$ statt $\begin{eqnarray*} y(x_i) \end{eqnarray*}$ heißt. Gerade bei Taylor war ich da eine andere Schreibweise gewohnt. Mag sein, dass das hier eben "abkürzend" ist, aber dieses "hin und her" der Schreibweisen gefällt mir nicht. unglücklich

Ich versuche (**) nun mal selber ... Entwickelt werden soll nun also y im Punkt $\begin{eqnarray*} x_i \end{eqnarray*}$ und ausgewertet im Punkt $\begin{eqnarray*} x_{i+1} \end{eqnarray*}$

$\begin{eqnarray*} y(x_{i+1}) &&=T_1(x_{i+1};x_i) = y(x_{i}) + \frac{y'(x_{i})}{1}(x_{i+1}-x_i) + R_1(x_{i+1}) &&= y(x_i) + y'(x_i) \cdot h + O(h^2) &&= y(x_i) + h\cdot f(x_i,y(x_i)) + O(h^2) \end{eqnarray*}$

Dann komme ich bei dem lokalen Diskretisierungsfehler auf:

$\begin{eqnarray*} \tau_i &&=\frac{1}{h}(\underbrace{y(x_i) + h\cdot f(x_i,y(x_i)) + O(h^2)}_{y(x_{i+1})} - y(x_i) - h \cdot f(x_i,y(x_i)) && = O(h) \end{eqnarray*}$

Ist nun so wie bei der "numerischen Integration", dass ich solange weiter mache, bis die Bedingung eben nicht mehr erfüllt ist?

$\begin{eqnarray*} y(x_{i+1}) &&=T_2(x_{i+1};x_i) = y(x_{i}) + \frac{y'(x_{i})}{1}(x_{i+1}-x_i) +\frac{y''(x_i)}{2}(x_{i+1}-x_i)^2+ R_2(x_{i+1}) &&= y(x_i) + y'(x_i) \cdot h + \frac{1}{2}y''(x_i)h^2+O(h^3) \end{eqnarray*}$

Nun muss ich die Ableitungen ja durch f ausdrücken. Bei y' war das klar. Wie ist dann nun bei y''? Warum gilt dann

Zitat:

$\begin{eqnarray*} y''=\frac{d}{dx}f(x,y(x)) = f_x+f_yf \end{eqnarray*}$

Also diese abkürzenden Schreibweisen machen mich noch.. Forum Kloppe

Also es ist $\begin{eqnarray*} f:~[a,b] \times \mathbb R \to \mathbb R \end{eqnarray*}$ . Aber wie wurde nun abgleitet? Mit Verallgemeinerter Kettenregel?

$\begin{eqnarray*} y''(x)=f'(\varphi(x)) \cdot \varphi'(x) \end{eqnarray*}$ mit

$\begin{eqnarray*} \varphi(x)=(\underbrace{x}_{x},\underbrace{y(x)}_{y}) \end{eqnarray*}$

$\begin{eqnarray*} \varphi'(x) = \begin{pmatrix}1 \\ y'(x) \end{pmatrix} \stackrel{\text{Def.}}= \begin{pmatrix} 1 \\ f(x,y(x)) \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} f'(x,y)=\begin{pmatrix} \frac{\partial f}{\partial x} & \frac{\partial f}{\partial y} \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} y''(x) &&=\begin{pmatrix} \frac{\partial f}{\partial x} & \frac{\partial f}{\partial y} \end{pmatrix}\begin{pmatrix} 1 \\ f(x,y(x)) \end{pmatrix} &&= \frac{\partial f}{\partial x} \cdot 1 + \frac{\partial f}{\partial y} \cdot f(x,y(x)) &&=f_x + f_yf \end{eqnarray*}$

Dann komme ich bei dem lokalen Diskretisierungsfehler auf:

$\begin{eqnarray*} \tau_i &&=\frac{1}{h}(\underbrace{ y(x_i) + y'(x_i) \cdot h + \frac{1}{2}y''(x_i)h^2+O(h^3)}_{y(x_{i+1})} - y(x_i) - h \cdot f(x_i,y(x_i)) && =\frac{1}{h}(0.5h^2(f_x(x_i,y(x_i)) + f_y(x_i,y(x_i)f(x_i,y(x_i)) + O(h^3) && = 0.5h \underbrace{(f_x(x_i,y(x_i)) + f_y(x_i,y(x_i)f(x_i,y(x_i))}_{=\text{konstant?}} + O(h^2) && \stackrel{?}= O(h) \end{eqnarray*}$

Was ist hier denn nun das c? Also warum hat das Verfahren nun die Ordnung 1? Augenzwinkern

Siehe meine (?) Umformung.

Puh, und um dann Ordnung 2 zu prüfen, muss ich ja noch eine Ableitung mehr berechnen...Die Abkürzenden Schreibweisen sind da sicher auf dauer "nett", aber mit ihnen sehe ich nicht, wie man hierauf kommt. Man wird sicher Satz von schwarz brauchen...

Zitat:

$\begin{eqnarray*} y_i'''=f_{xx}+2f_{xy}f+f_{yy}f^2+f_yf_x + f^2_yf \end{eqnarray*}$

Mit einer etwas wilden Rechnung analog zu oben komme ich (wenn ich mir Vektoren Transponiere wie ich es mag auch darauf). aber mal eine richtige Erläuterung wäre gut.

$\begin{eqnarray*} y'''(x)&&=f''(\varphi(x)) \cdot \varphi'(x)\cdot \varphi'(x) + f'(\varphi(x))\varphi''(x) &&=\left(\begin{pmatrix}f_{xx} & f_{xy} \\ f_{yx} & f_{yy} \end{pmatrix} \begin{pmatrix}1\\f \end{pmatrix}\right)^T\begin{pmatrix}1\\f \end{pmatrix} + \begin{pmatrix} f_x & f_y \end{pmatrix} \begin{pmatrix} 0 \\ y'' \end{pmatrix} &&=f_{xx} + f_{xy}f + f_{yx}f + f_{yy}f^2 + f_y(f_x + f_yf) \end{eqnarray*}$

edit:

Ich glaube ich habe diese Verallgemeinerte Regel nun verstanden, auch wie man dass dann gleich in einer Summe umsetzten kann. Übung macht eben den Lehrling. Augenzwinkern

Dann also nun zurück zu der Frage, warum das explizite Eulerverfahren nur die Ordnung 1 hat. Ich stelle also wieder den lokalen Diskretisierungsfehler auf.

$\begin{eqnarray*} \tau_i &&=\frac{1}{h}(\underbrace{ y + y' \cdot h + \frac{1}{2}y''h^2+ \frac{1}{6}y'''h^3 +O(h^4)}_{y(x_{i+1})} - y(x_i) - h \cdot f(x_i,y(x_i)) && = \frac{1}{h}(\frac{1}{2}\underbrace{y''}_{\text{i.A.}\neq 0}h^2+ \frac{1}{6}y'''h^3 +O(h^4)) && =O(h) \end{eqnarray*}$

Da die Untersuchung für höhere Ordnung ja immer die "alten Terme" mitschleppt, sieht man das also ggf. schon aus der Untersuchung für die Ordnung 1?

19.07.2009, 14:43

tigerbine

Auf diesen Beitrag antworten »

Der Post ist zwar lang geworden, freue mich, wenn jemand in dennoch durchliest und kommentiert. Danke. Wink

19.07.2009, 14:58

Dunkit

Auf diesen Beitrag antworten »

Hoi,

ich wollte grade anfangen, muss nu aber wech Big Laugh

Werde mich morgen mal damit beschäftigen, das Semester geht ja eh langsam zu Ende. Vielleicht findet sich aber ja auchnoch jemand neues für die Diskussion? ;-)

20.07.2009, 12:08

Dunkit

Auf diesen Beitrag antworten »

Hi,

also zunächst mal

Zitat:

Da die Untersuchung für höhere Ordnung ja immer die "alten Terme" mitschleppt, sieht man das also ggf. schon aus der Untersuchung für die Ordnung 1?

Das trifft es glaube ich ganz gut. Würdest du weiter Taylor-entwickeln, ändern sich ja die führenden Terme nicht. Woran man IM VORFELD erkennen kann, wie weit man die Taylor-Entwicklung braucht, kann ich dir auch nicht sagen, muss man wahrscheinlich ausprobieren... In den Aufgaben die ich kenne heißt es bisher immer nur "Zeigen Sie, dass das Verfahren ... die Ordnung ... hat" Augenzwinkern

Zum Problem mit der Glattheit: Wenn man die Konsistenzordnung über die Taylorentwicklung bestimmt, fordert man natürlich implizit, dass f hinreichend glatt ist. Ist f "nicht sehr glatt", dann wird auch das Verfahren i.d.R. schlechtere Ergebnisse liefern (siehe oben)

Zitat:

Ist aber schon was seltsam, will ich mit dem Verfahren doch gerade eine unbekannte Funktion y annähern....

Da verstehe ich nicht ganz was du meinst. Die Funktion y ist sicher unbekannt, allerdings kann man doch sagen, wenn man zB $\begin{eqnarray*} y'(x) = f(x,y(x)) \end{eqnarray*}$ und $\begin{eqnarray*} f \in C^4 \end{eqnarray*}$ hat, dass $\begin{eqnarray*} y \in C^5 \end{eqnarray*}$ sein muss. Im Zusammenhang mit pDGLn kann man zwar an dieser Stelle noch den Begriff der "schwachen Lösung" einführen, aber hier geht das glaube ich nicht...

20.07.2009, 12:29

tigerbine

Auf diesen Beitrag antworten »

OK. Meine Fragen zu Taylor habe ich in einen anderen Thread ausgegliedert. Aber die "Idee" passt also. Nun nur noch richtig berechnen Augenzwinkern

Sicherlich stimmt es, dass wenn ich f kenne, ich auch etwas über y sagen kann. Aber bei der Beurteilung der Verfahren ist f doch genauso unbekannt. Augenzwinkern

20.07.2009, 18:23

Dunkit

Auf diesen Beitrag antworten »

Achso: Also ich verstehe das so, dass man zB nur sagen kann, dass das Eulerverfahren Konvergenz/Konsistenzordnung 1 hat, wenn f so und so oft (habe die Zahl gerade vergessen Augenzwinkern

) stetig diffbar ist...

20.07.2009, 19:05

tigerbine

Auf diesen Beitrag antworten »

Das meinte ich mit "Untertitel" bzw. "Kleingedrucktem"

21.07.2009, 00:59

tigerbine

Auf diesen Beitrag antworten »

Konvergenz und Konvergenzordnung
Ok, die Konsistenzordnung eines ESV kann nun bestimmt werden. wie mir mein Buch sagt, ist die Überprüfung höherer Ordnungen doch recht aufwendig. Augenzwinkern

Nächster Schritt wären dann wohl die Runge-Kutta Verfahren und deren Notation im Butcher Schema.

Dann bliebe der Begriff der Konsistenz eines ESV. Definition:

$\begin{eqnarray*} \phi(x,y;0) = f(x,y(x)) \quad \forall x \in [a,b] \end{eqnarray*}$

Dabei ist jedes ESV mit einer Konsistenzordnung $\begin{eqnarray*} p \geq 1 \end{eqnarray*}$ und stetiger Verfahrensfunktion konsistent. Für die Runge Kutta Verfahren kann man Konsistenz durch die Summierung der "Stufenkoeffizienten" überprüfen. Es muss gelten

$\begin{eqnarray*} \Phi(x,y,h;f):=c_1k_1 + ...+ .c_sk_s,~\sum_{i=1}^sc_i = 1 \end{eqnarray*}$

Ws gibt es keine nette Möglichkeit, die Ordnung aus dem Tableau abzulesen. (?) Brauchen werden wir die KSO um die KVO "einfach" bestimmen zu können? Du hattest da ja schon so was angesprochen.

Konvergenzordnung

Dabei ist nun der globale Diskretisierungsfehler

$\begin{eqnarray*} e(x;h) = \eta(x;h)-y(x),\quad \text{mit } \eta(x;h):=\eta_i \end{eqnarray*}$

Dabei heißt das ESV konvergent, wenn

$\begin{eqnarray*} \lim_{n \to \infty}~e(x;h_h)=0 \quad \text{mit } h_n:=\frac{x-x_0}{n} \end{eqnarray*}$

Stellt man an f noch ein paar Bedingungen, so folgt dass für Verfahren der KSO p>0 dass sie konvergent sind und es gilt:

$\begin{eqnarray*} e(x;h_n)=O(h_n^p) \end{eqnarray*}$

Nun kommt wohl die entscheidende Frage, wie man h wählen muss, um y bis auf eine vorgegebene Genauigkeit zu approximieren. Der Kommentar zu dem Hauptsatz sagt aber, dass der so def/ber. globale Fehler nicht dafür geeinget ist

24.07.2009, 09:24

Dunkit

Auf diesen Beitrag antworten »

Hallo!
Die Runge-Kutta Formeln sind ja allgemein gegeben durch
$\begin{eqnarray*} \Phi_f(x,y,h) = \sum_{i=0} ^n \gamma_i k_i(x,y,h) \end{eqnarray*}$
mit
$\begin{eqnarray*} k_0 (x,y,h) = f(x,y) \end{eqnarray*}$
...
$\begin{eqnarray*} k_n (x,y,h) = f(x+ \alpha_n \cdot h, y + h\sum_{j=0}^{n-1} \beta_{nj} k_j(x,y,h)) \end{eqnarray*}$
Daraus lassen sich theoretisch Verfahren beliebig komplizierte Verfahren konstruieren. Ziel sollte es natürlich sein, die Konstanten $\begin{eqnarray*} \alpha_i, \beta_{ij}, \gamma_i \end{eqnarray*}$ so zu wählen, dass die Konsistenzordnung möglichst hoch wird.
Diese Konstanten kann man dann in diesem Butcher-Schema anordnen (wobei wir das garnicht so genannt haben), aber ob man an diesem Schema unmittelbar die Ordnung ablesen kann wage ich zu bezweifeln. Jedenfalls ist mir sowas nicht bekannt.
Für die Konsistenzordnung $\begin{eqnarray*} p \end{eqnarray*}$ gitl im Übrigen $\begin{eqnarray*} n+1 \geq p \end{eqnarray*}$ und die Gleichheit ist nur für $\begin{eqnarray*} p \leq 5 \end{eqnarray*}$ zu erreichen.
Als Bemerkung habe ich im Übrigen auch hier stehen, dass Verfahren mit solch hohen Ordnungnen nur Sinn machen, falls alle relevanten Funktionen hinreichend glatt sind. Das bestätigt ja nochmal deine Überlegungen von oben.
Da die Runge-Kutta Formeln ja ein ESV sind gilt hier die Äquivalenz Konsistenzordnung p $\begin{eqnarray*} \Leftrightarrow \end{eqnarray*}$ Konvergenzordnung p.

Ich habe übrigens eine Fehlerabschätzung für Verfahren mit Lipschitz-stetiger Verfahrensfunktion gefunden, die aber meiner Meinung nach eher von theoretischem Nutzen ist: Es gilt nämlich
$\begin{eqnarray*} |\eta_j - u^*(x_j)| \leq \frac{e^{j\cdot hL}-1}{Lh} \cdot Kh^{p+1} \end{eqnarray*}$
wobei:
$\begin{eqnarray*} u^* \end{eqnarray*}$ die exakte Lösung des AWP
$\begin{eqnarray*} L \end{eqnarray*}$ die Lipschitzkonstante der Verfahrenfunktion bzgl $\begin{eqnarray*} y \end{eqnarray*}$ (d.h. die Verfahrensfunktion muss eine globale Liptschitzbedingung erfüllen)
$\begin{eqnarray*} K \end{eqnarray*}$ eine Konstante, so dass für den lokalen Diskretisierungsfehler gilt $\begin{eqnarray*} |\tau [u^*](x,h) \leq K h^p \end{eqnarray*}$ (hier liegt auch der Knackpunkt: Diese Konstante sollte in der Praxis schwer zu ermitteln sein (?)).
$\begin{eqnarray*} p \end{eqnarray*}$ dementsprechend die Konsistenzordnung des Verfahrens.
Insbesondere lierfert diese Abschätzung natürlich die Konvergenz p-ter Ordnung für das Verfahren!

Ich hoffe ich konnte diesen Thread etwas erhellen und Stoff für eine weitere Diskussion liefern Augenzwinkern

19.08.2009, 12:04

Dunkit

Auf diesen Beitrag antworten »

Hallo!

Ich möchte nochmal kurz was zu dem Problem "Was mache ich mit meinen berechneten (diskreten) Werten?" sagen.

Bei meiner Vorbereitung zu meinem Vortrag über "Runge-Kutta Formeln und Kollokationsverfahren" habe ich nämlich herausgefunden, dass Kollokationsverfahren nicht nur diskrete Wertemengen, sondern auch eine Approximation des tatsächlichen Ergebnisses liefern. Hier könnte man also nochmal weitere Nachforschungen anstellen Augenzwinkern

Kann noch nicht wirklich viel dazu sagen, da ich es auch gerade erst gelesen habe...

Neue Frage »

Antworten »

Numerik von ESV (1)

Verwandte Themen