Stabilität eines Algorithmus < Numerik < Hochschule < Mathe < Vorhilfe
|
Hallo zusammen!
Ich habe hier ein Beispiel zur Stabilität eines Algorithmus, verstehe aber einige Stellen nicht. Ich schreibe es mal runter und stelle an den entsprechenden Stellen meine Fragen:
[mm] y = f(x_1,x_2) = x_1^2-x_2^2 = (x_1+x_2) \cdot (x_1-x_2) [/mm].
Problemfehler durch Rundung der Eingangsdaten: [mm] \left|\bruch{\Delta y}{y}\right| \le \summe_{j=1}^{2} \left|\bruch{\partial f}{\partial x_j} \bruch{x_j}{f}\right| \left|\bruch{\Delta x_j}{x_j}\right| \le 2 \left|\bruch{(x_1/x_2)^2 +1}{(x_1/x_2)^2 -1}\right| eps [/mm]
Wie kommt es zur letzten Ungleichung? Ich habe die Funktion abgeleitet und bekomme in Summe 2, aber wie entsteht der Bruch dahinter?
Algorithmus A: [mm] u = x_1 \odot x_1, \quad v = x_2 \odot x_2, \quad w = u \ominus v [/mm]
Zur Rundungsanalyse beachten wir, dass für Maschinenoperationen [mm] \* [/mm] gilt: [mm] a \* b = rd(a \* b) = (a \* b)(1 + \epsilon) [/mm] mit [mm] |\epsilon| \le eps [/mm].
A) [mm] u = x_1^2(1 + \epsilon_1), \quad v = x_2^2(1 + \epsilon_2), \quad
w = [x_1^2(1 + \epsilon_1) - x_2^2(1 + \epsilon_2)](1 + \epsilon_3) = x_1^2 - x_2^2 + x_1^2 \epsilon_1 - x_2^2 \epsilon_2 + (x_1^2 - x_2^2) \epsilon_3 + O(eps^2) [/mm]
[mm] \left|\bruch{\Delta y}{y}\right| \le eps \ \bruch{x_1^2 + x_2^2 + |x_1^2 - x_2^2|}{|x_1^2 - x_2^2|} = eps \ \left\{ 1 + \bruch{(x_1/x_2)^2 + 1}{(x_1/x_2)^2 - 1} \right\} [/mm]
Diese letzte Zeile verstehe ich überhaupt nicht mehr... Kann mir jemand helfen sie zu verstehen?
LG
fagottator
|
|
|
|
Status: |
(Antwort) fertig | Datum: | 02:06 Do 24.02.2011 | Autor: | Blech |
Eingabefehler: "\left" und "\right" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
Hi,
> Ich habe die Funktion abgeleitet und bekomme in Summe 2
Da sind ein paar Terme verschwunden. Ich nehm an, daß Du die Betragsstriche in der Summe übersehen hast.
> Diese letzte Zeile verstehe ich überhaupt nicht mehr... Kann mir jemand helfen sie zu verstehen?
Das Ergebnis der Maschinenrechnung ist w. Also ist
$|\Delta y| = |w-y|=$
$=\left|\left(x_1^2 - x_2^2 + x_1^2 \epsilon_1 - x_2^2 \epsilon_2 + (x_1^2 - x_2^2) \epsilon_3 + O(eps^2))- (x_1^2-x_2^2) \right|\approx \left|x_1^2 \epsilon_1 - x_2^2 \epsilon_2 + (x_1^2 - x_2^2) \epsilon_3\right|\leq \left|x_1^2 \epsilon_1\right|+\left| x_2^2 \epsilon_2 \right|+\left|(x_1^2 - x_2^2) \epsilon_3\right|$
Terme quadratischer Ordnung, soll heißen $O(eps^2)$, ignorieren wir, weil sie zu klein sind, um eine Rolle zu spielen.
ciao
Stefan
|
|
|
|
|
> Hi,
>
> > Ich habe die Funktion abgeleitet und bekomme in Summe 2
>
> Da sind ein paar Terme verschwunden. Ich nehm an, daß Du
> die Betragsstriche in der Summe übersehen hast.
Also, ich hab im Prinzip nur den ersten Betrag abgeleitet. Wenn da zwei rauskommt, sind die Betragsstriche ja überflüssig. Aber ich habe grad gar keine Vorstellung, wie [mm]\left| \bruch{\Delta x_j}{x_j} \right| [/mm] überhaupt aussieht. Somit weiß ich nicht, wie ich diesen Term ableiten soll.
>
>
> > Diese letzte Zeile verstehe ich überhaupt nicht mehr...
> Kann mir jemand helfen sie zu verstehen?
>
> Das Ergebnis der Maschinenrechnung ist w. Also ist
>
> [mm]|\Delta y| = |w-y|=[/mm]
DAS ist doch auf jeden Fall schon mal eine Erkenntnis! Danke!
> [mm]=\left|\left(x_1^2 - x_2^2 + x_1^2 \epsilon_1 - x_2^2 \epsilon_2 + (x_1^2 - x_2^2) \epsilon_3 + O(eps^2))- (x_1^2-x_2^2) \right|\approx \left|x_1^2 \epsilon_1 - x_2^2 \epsilon_2 + (x_1^2 - x_2^2) \epsilon_3\right|\leq \left|x_1^2 \epsilon_1\right|+\left| x_2^2 \epsilon_2 \right|+\left|(x_1^2 - x_2^2) \epsilon_3\right|[/mm]
OK, ich komme der Sache bedeutend näher (dank der obigen Erläuterung von [mm] \Delta y [/mm]). Aus [mm] x_1^2 \epsilon_1 - x_2^2 \epsilon_2 + (x_1^2 - x_2^2) \epsilon_3 [/mm] werden dann wahrscheinlich [mm] \epsilon_1, \epsilon_2, \epsilon_3 [/mm] rausgezogen und als "eps" vor dem Bruch dargestellt. Was mich jetzt nur noch irritiert ist der Vorzeichenwechsel [mm] \left|x_1^2 \epsilon_1 [/mm] - [mm] x_2^2 \epsilon_2 + (x_1^2 - x_2^2) \epsilon_3\right|\leq \left|x_1^2 \epsilon_1\right| [/mm] + [mm] \left| x_2^2 \epsilon_2 \right|+\left|(x_1^2 - x_2^2) \epsilon_3\right| [/mm]
>
> Terme quadratischer Ordnung, soll heißen [mm]O(eps^2)[/mm],
> ignorieren wir, weil sie zu klein sind, um eine Rolle zu
> spielen.
Aber was ist mit dem letzten Schritt? [mm] eps \ \left\{ 1 + \bruch{(x_1/x_2)^2 + 1}{(x_1/x_2)^2 - 1} \right\} [/mm] Ist der so banal, das du nicht auf den eingehst?
>
> ciao
> Stefan
LG
fagottator
|
|
|
|
|
Status: |
(Antwort) fertig | Datum: | 20:59 Do 24.02.2011 | Autor: | Blech |
Hi,
> Also, ich hab im Prinzip nur den ersten Betrag abgeleitet. Wenn da zwei rauskommt, sind die Betragsstriche ja überflüssig.
Die Ableitung will ich sehen.
> Aber ich habe grad gar keine Vorstellung, wie $ [mm] \left| \bruch{\Delta x_j}{x_j} \right| [/mm] $ überhaupt aussieht. Somit weiß ich nicht, wie ich diesen Term ableiten soll.
Was ist denn $ [mm] \left| \bruch{\Delta x_j}{x_j} \right| [/mm] $? Also jetzt mal anschaulich/logisch. Was sagt mir [mm] $\Delta x_j$?
[/mm]
> Was mich jetzt nur noch irritiert ist der Vorzeichenwechsel
Die Frage geb ich zurück.
[mm] $|a-b|\leq [/mm] |a|+|b|$
Das kannst Du mir mit ein paar elementaren Eigenschaften des Betrags erklären.
> Aber was ist mit dem letzten Schritt?
Hmm, Du hast recht. Da fehlen die Betragsstriche um den Nenner (oder den ganzen Bruch, der Zähler ist positiv)
$ eps \ [mm] \bruch{x_1^2 + x_2^2 + |x_1^2 - x_2^2|}{|x_1^2 - x_2^2|} [/mm] = eps \ [mm] \left\{ 1 +\left| \bruch{(x_1/x_2)^2 + 1}{(x_1/x_2)^2 - 1} \right|\right\} [/mm] $
Sonst wurde nur gekürzt.
ciao
Stefan
|
|
|
|
|
> Hi,
>
> > Also, ich hab im Prinzip nur den ersten Betrag abgeleitet.
> Wenn da zwei rauskommt, sind die Betragsstriche ja
> überflüssig.
>
> Die Ableitung will ich sehen.
Ich hab wohl ein wenig geschmut... Also, ich habe erst nur [mm] \bruch{\partial f_i(x)}{\partial x_j} [/mm] berechnet. Also: [mm] f(x) = x_1^2-x_2^2 \Rightarrow f_{x_1} = 2x_1, \ f_{x_2} = -2x_2 [/mm] Dann kommt glaub ich der Fehler: [mm] \left| \summe_{j=1}^{2} \bruch{\partial f_i(x)}{\partial x_j} \bruch{\Delta x_j}{y_i} \right| = \left| \bruch{2(x_^1-x_2^2)}{x_1^2-x_2^2} \right| = 2 [/mm]
>
> > Aber ich habe grad gar keine Vorstellung, wie [mm]\left| \bruch{\Delta x_j}{x_j} \right|[/mm]
> überhaupt aussieht. Somit weiß ich nicht, wie ich diesen
> Term ableiten soll.
>
> Was ist denn [mm]\left| \bruch{\Delta x_j}{x_j} \right| [/mm]? Also
> jetzt mal anschaulich/logisch. Was sagt mir [mm]\Delta x_j[/mm]?
Also [mm]\Delta x_j[/mm] ist ja die Abweichung eines (fehlerbehafteten) [mm] \tilde x [/mm] zu [mm]x[/mm]. Z.B. [mm] x-rd(x) [/mm]. Aber inwieweit steht das mit [mm] y_i [/mm] in Zusammenhang? Was also ergibt [mm] \left| \bruch{\Delta x_j}{y_i} \right| [/mm]?
>
> > Was mich jetzt nur noch irritiert ist der
> Vorzeichenwechsel
>
> Die Frage geb ich zurück.
>
> [mm]|a-b|\leq |a|+|b|[/mm]
>
> Das kannst Du mir mit ein paar elementaren Eigenschaften
> des Betrags erklären.
Weil ich selbst so nicht drauf gekommen wär, hab ich es mir bei wikipedia durchgelesen, jetzt ist es klar. Danke.
>
>
> > Aber was ist mit dem letzten Schritt?
>
> Hmm, Du hast recht. Da fehlen die Betragsstriche um den
> Nenner (oder den ganzen Bruch, der Zähler ist positiv)
>
> [mm]eps \ \bruch{x_1^2 + x_2^2 + |x_1^2 - x_2^2|}{|x_1^2 - x_2^2|} = eps \ \left\{ 1 +\left| \bruch{(x_1/x_2)^2 + 1}{(x_1/x_2)^2 - 1} \right|\right\}[/mm]
>
> Sonst wurde nur gekürzt.
Jup, ich hatte es dann auch noch rausgekriegt, aber trotzdem danke.
>
> ciao
> Stefan
LG
fagottaor
|
|
|
|
|
Status: |
(Antwort) fertig | Datum: | 15:49 Fr 25.02.2011 | Autor: | Blech |
Hi,
keine Zeit, also kurz: =)
> $ [mm] \left| \summe_{j=1}^{2} \bruch{\partial f_i(x)}{\partial x_j} \bruch{\Delta x_j}{y_i} \right|$
[/mm]
1. Die Summe ist außerhalb der Bruchstriche.
2. Der Bruch hinter der Ableitung ist [mm] $x_j/f$, [/mm] nicht [mm] $\Delta x_j$ [/mm] und was soll [mm] $y_i$ [/mm] sein?
> Also $ [mm] \Delta x_j [/mm] $ ist ja die Abweichung eines (fehlerbehafteten) $ [mm] \tilde [/mm] x $ zu $ x $.
Ja, und wo kommt bei x der Fehler her? Was ist denn x? Deine Eingabe.
> Aber inwieweit steht das mit $ [mm] y_i [/mm] $ in Zusammenhang? Was also ergibt $ [mm] \left| \bruch{\Delta x_j}{y_i} \right| [/mm] $?
Nenner ist [mm] $x_j$ [/mm] nicht [mm] $y_j$.
[/mm]
Gut, daß alles andere jetzt klar ist. Sorry wenn ich Dich mit den fehlenden Betragsstrichen beim einen verwirrt hatte. =)
ciao
Stefan
|
|
|
|