Fixpunktiteration < Nichtlineare Gleich. < Numerik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Unter anderem:
f(x) = [mm] e^{-x}-x
[/mm]
Nullstellen bestimmen mittels Fixpunktiteration bis absoluten Fehler 0.01. Voraussetzungen prüfen, a-priori und a-posterori Abschätzung.
Hinweis: Zeigen Sie beim Fixpunktverfahren zunächst, dass ein geeignetes Intervall I = [a,b] (siehe Bisektionsverfahren) auf ein Teilintervall abgebildet wird. Wenn ein Fixpunkt existiert, dann kann dieser nur im Teilintervall (I's,a's,b's mit Schlange habs mal überall "Teilintervall" genannt) liegen. Es genügt also, die Kontraktivität im Teilintervall nachzuweisen. Für entsprechende Fehlerabschätzungen muss dann aber auch konsequenterweise ein Startwert aus dem Teilintervall gewählt werden. |
Beim Bisektionsverfahren hab ich den Startwert 0 und 1 gewählt. Das würd sich auch als Intervall eignen weil es Selbstabbildend ist.
Das Fixpunktverfahren ist mir ganz suspekt ich hab viele Formeln gesehen oder Formulierungen man muss die Funktion auf die Form F(x)=x bringen ...? Wie soll das denn gehen.
Die beiden a-Abschätzungen sind ja zwei Formeln mich wundert es aber das ich die beiden Abschätzungen für zwei Verfahren machen soll (Bisektion, Fix) - wo in den Formeln kommt denn "das Verfahren" ins Spiel? Logisch ist es ja allemal das man bei verschiedenen Verfahren wahrscheinlich unterschiedlich viele Schritte braucht.
|
|
| |
|
> Unter anderem:
> f(x) = [mm]e^{-x}-x[/mm]
>
> Nullstellen bestimmen mittels Fixpunktiteration bis
> absoluten Fehler 0.01. Voraussetzungen prüfen, a-priori
> und a-posterori Abschätzung.
>
> Hinweis: Zeigen Sie beim Fixpunktverfahren zunächst, dass
> ein geeignetes Intervall I = [a,b] (siehe
> Bisektionsverfahren) auf ein Teilintervall abgebildet wird.
> Wenn ein Fixpunkt existiert, dann kann dieser nur im
> Teilintervall [mm]\tilde{I}=[\tilde{a},\tilde{b}][/mm]
> liegen. Es genügt also, die
> Kontraktivität im Teilintervall nachzuweisen. Für
> entsprechende Fehlerabschätzungen muss dann aber auch
> konsequenterweise ein Startwert aus dem Teilintervall
> gewählt werden.
>
> Beim Bisektionsverfahren hab ich den Startwert 0 und 1 ![[ok]](/images/smileys/ok.gif "[ok]")
> gewählt. Das würd sich auch als Intervall eignen weil es
> Selbstabbildend ist.
Das wäre ja noch zu begründen. Kontraktivität solltest du ja auch zeigen.
Es gäbe ja zwei Möglichkeiten:
$|g'(x)|=L<1 [mm] \forall x\in [/mm] I$ oder die schwächere Form.
[mm] $\exists \alpha [/mm] < 1 [mm] \;|\; g(x_1)-g(x_2)\leq \alpha (x_1-x_2)\qquad \forall x_1,x_2\in [/mm] I$
>
> Das Fixpunktverfahren ist mir ganz suspekt ich hab viele
> Formeln gesehen oder Formulierungen man muss die Funktion
> auf die Form F(x)=x bringen ...? Wie soll das denn gehen.
Die Formeln stimmen schon, da sollte nichts suspekt sein 
Du willst die Nullstelle von f haben, also f(x)=0. Dann gibt es doch (meistens) eine Funktion g mit f(x)=g(x)-x, wobei f(x)=0 <=> g(x)=x gilt.
Das ist nicht einmal eindeutig:
[mm]g_1(x)=e^{-x}[/mm]
[mm]g_2(x)=-\ln (x)[/mm]
Allgemein setzt du die Funktion f gleich Null und löst nach einem x aus.
>
> Die beiden a-Abschätzungen sind ja zwei Formeln mich
> wundert es aber das ich die beiden Abschätzungen für zwei
> Verfahren machen soll (Bisektion, Fix) - wo in den Formeln
Gedankenlesen funktioniert nicht gerade wirklich gut. Meinst du diese:
[mm]|\xi-x_n|\leq \frac{q}{1-q}|x_n-x_{n-1}|\leq \frac{q^n}{1-q}|x_1-x_0|[/mm] (Fehlerabschätzung Fixpunktsatz)
Wobei [mm]\xi[/mm] der Fixpunkt wäre
Und für das Intervallhalbierungsverfahren:
[mm]d(I_n(f),f)\leq 0.5^{n+1}*(b-a)[/mm]
Bezeichungen sind bei dir bestimmt anders.
> kommt denn "das Verfahren" ins Spiel? Logisch ist es ja
> allemal das man bei verschiedenen Verfahren wahrscheinlich
> unterschiedlich viele Schritte braucht.
Ich denke schon das da unterschiedliche Werte herauskommen. Das Bisektionsv. sollte aber einer gewissen epsilon-Umgebung deutlich langsamer konvergieren.
|
|
|
| |
|
DANKE!
> Das wäre ja noch zu begründen. Kontraktivität solltest
> du ja auch zeigen.
> Es gäbe ja zwei Möglichkeiten:
> [mm]g'(x)=L<1 \forall x\in I[/mm] oder die schwächere Form.
> [mm]\exists \alpha < 1 \;|\; g(x_1)-g(x_2)\leq \alpha (x_1-x_2)\qquad \forall x_1,x_2\in I[/mm]
Ja, da kenn ich erstmal nur dieses Epsilon-Delta ähnliche Verfahren. Also das zweite von dir.
> > Das Fixpunktverfahren ist mir ganz suspekt ich hab viele
> > Formeln gesehen oder Formulierungen man muss die Funktion
> > auf die Form F(x)=x bringen ...? Wie soll das denn gehen.
> Die Formeln stimmen schon, da sollte nichts suspekt sein
>
> Du willst die Nullstelle von f haben, also f(x)=0. Dann
> gibt es doch (meistens) eine Funktion g mit f(x)=g(x)-x,
> wobei f(x)=0 <=> g(x)=x gilt.
> Das ist nicht einmal eindeutig:
> [mm]g_1(x)=e^{-x}[/mm]
> [mm]g_2(x)=-\ln (x)[/mm]
> Allgemein setzt du die Funktion f gleich
> Null und löst nach einem x aus.
Achso! Wieso schreiben das alle in so einem fachchinsisch auf, wenn man es auch einfach formulieren kann. Wie kann ich dann mit dem g weiterrechnen, also wie mach ich die Iterationen?
> > Die beiden a-Abschätzungen sind ja zwei Formeln mich
> > wundert es aber das ich die beiden Abschätzungen für zwei
> > Verfahren machen soll (Bisektion, Fix) - wo in den Formeln
> Gedankenlesen funktioniert nicht gerade wirklich gut.
> Meinst du diese:
> [mm]|\xi-x_n|\leq \frac{q}{1-q}|x_n-x_{n-1}|\leq \frac{q^n}{1-q}|x_1-x_0|[/mm]
> (Fehlerabschätzung Fixpunktsatz)
Ja, das sieht danach aus. Wie kommt man an das q?
> Wobei [mm]\xi[/mm] der Fixpunkt wäre
>
> Und für das Intervallhalbierungsverfahren:
> [mm]d(I_n(f),f)\leq 0.5^{n+1}*(b-a)[/mm]
Also die obere Fehlerabschätzung ist nicht für das Bisektionsverfahren geeignet? Ich dacht das wär was Allgemeines.
|
|
|
| |
|
> DANKE!
>
> > Das wäre ja noch zu begründen. Kontraktivität solltest
> > du ja auch zeigen.
> > Es gäbe ja zwei Möglichkeiten:
> > [mm]g'(x)=L<1 \forall x\in I[/mm] oder die schwächere Form.
> > [mm]\exists \alpha < 1 \;|\; g(x_1)-g(x_2)\leq \alpha (x_1-x_2)\qquad \forall x_1,x_2\in I[/mm]
>
> Ja, da kenn ich erstmal nur dieses Epsilon-Delta ähnliche
> Verfahren. Also das zweite von dir.
> > > Das Fixpunktverfahren ist mir ganz suspekt ich hab
> viele
> > > Formeln gesehen oder Formulierungen man muss die Funktion
> > > auf die Form F(x)=x bringen ...? Wie soll das denn gehen.
> > Die Formeln stimmen schon, da sollte nichts suspekt
> sein
> >
> > Du willst die Nullstelle von f haben, also f(x)=0. Dann
> > gibt es doch (meistens) eine Funktion g mit f(x)=g(x)-x,
> > wobei f(x)=0 <=> g(x)=x gilt.
> > Das ist nicht einmal eindeutig:
> > [mm]g_1(x)=e^{-x}[/mm]
> > [mm]g_2(x)=-\ln (x)[/mm] [geht nicht]
> > Allgemein setzt du die Funktion f
> gleich
> > Null und löst nach einem x aus.
>
> Achso! Wieso schreiben das alle in so einem fachchinsisch
> auf, wenn man es auch einfach formulieren kann. Wie kann
> ich dann mit dem g weiterrechnen, also wie mach ich die
> Iterationen?
Du wendest den algorithmus an:
[mm]g_1(0.5)=x_1[/mm]
[mm]g_1(x_1)=x_2[/mm]
[mm]g_1(x_{k+1})=x_k[/mm]
Es kommt so eine Folge heraus:| 1: | 0.106530659712633 = x_1
| | 2: | 0.898947486267112 = x_2
| | 3: | 0.406997805165797
| | 4: | 0.665645651281760
| | 5: | 0.513941593512693
| | 6: | 0.598133327909194
| | 7: | 0.549837044210839
| | 8: | 0.577043835352892
| | 9: | 0.561555967185657
| | 10: | 0.570320972389076
| | 11: | 0.565343949776419
| | 12: | 0.568164693027198
| | 13: | 0.566564304507705
| | 14: | 0.567471753457951
| | 15: | 0.566957035386489
| | 16: | 0.567248933534527
| | 17: | 0.567083378785090
| | 18: | 0.567177269903620
| | 19: | 0.567124019495253
| | 20: | 0.567154219884970
| | 21: | 0.567137091865138
| | 22: | 0.567146805883686
| | 23: | 0.567141296635852
| | 24: | 0.567144421166419
| | 25: | 0.567142649109108
| | 26: | 0.567143654119276
|
>
> > > Die beiden a-Abschätzungen sind ja zwei Formeln mich
> > > wundert es aber das ich die beiden Abschätzungen für zwei
> > > Verfahren machen soll (Bisektion, Fix) - wo in den Formeln
> > Gedankenlesen funktioniert nicht gerade wirklich gut.
> > Meinst du diese:
> > [mm]|\xi-x_n|\leq \frac{q}{1-q}|x_n-x_{n-1}|\leq \frac{q^n}{1-q}|x_1-x_0|[/mm]
> > (Fehlerabschätzung Fixpunktsatz)
>
> Ja, das sieht danach aus. Wie kommt man an das q?
Das q ist das L. Du löst alles nach einander auf.
[mm]|x_{n+1}-x_n|=|g(x_n)-g(x_{n-1})|\leq L |x_{n-1}-x_{n-2}|=|g(x_{n-2})-g(x_{n-3})|\leq L * L |x_{n-2}-x_{n-3}|...[/mm]
zum bestimmen setzte du [mm]L:=\sup |g_1'(x)|[/mm] Wenn du den Mittelwertsatz anwendest, siehst du, dass die Bedingung mit $g'(x)=L<1$ ein bisschen schärfer als die Lipschitz-Bedingung ist.
> > Wobei [mm]\xi[/mm] der Fixpunkt wäre
> >
> > Und für das Intervallhalbierungsverfahren:
> > [mm]d(I_n(f),f)\leq 0.5^{n+1}*(b-a)[/mm]
>
> Also die obere Fehlerabschätzung ist nicht für das
> Bisektionsverfahren geeignet? Ich dacht das wär was
> Allgemeines.
|
|
|
| |
|
> Das q ist das L. Du löst alles nach einander auf.
> [mm]|x_{n+1}-x_n|=|g(x_n)-g(x_{n-1})|\leq L |x_{n-1}-x_{n-2}|=|g(x_{n-2})-g(x_{n-3})|\leq L * L |x_{n-2}-x_{n-3}|...[/mm]
>
> zum bestimmen setzte du [mm]L:=\sup |g_1'(x)|[/mm] Wenn du den
> Mittelwertsatz anwendest, siehst du, dass die Bedingung mit
> [mm]g'(x)=L<1[/mm] ein bisschen schärfer als die
> Lipschitz-Bedingung ist.
Aso!, aber was ist denn das Supremum von [mm] e^{-x}? [/mm] Danke, die Iteration hab ich jetzt hingekriegt auch wenn ich andere Werte hatte als du, mit 0.5 als Startwert.
edit:
q bzw. L lässt sich einfach berechnen denn man beachtet nur das Teilintervall. In diesem Falle: I=[0.3678791,1]
max | g'(x) | = -g'(0.367) = 0.6928
für die a-priori Abschätzung:
[mm] \frac{L^k}{1-L}|x_1-x_0| [/mm] = [mm] \varepsilon
[/mm]
[mm] (\varepsilon [/mm] Genauigkeit [mm] \varepsilon=0.01)
[/mm]
nach n umformen:
n = [mm] \frac{ln\frac{\varepsilon(1-L)}{|x_1-x_0|}}{ln(L)}
[/mm]
n = 9.66, bzw. 10 Iterationen
|
|
|
| |
|
> > Das q ist das L. Du löst alles nach einander auf.
> > [mm]|x_{n+1}-x_n|=|g(x_n)-g(x_{n-1})|\leq L |x_{n-1}-x_{n-2}|=|g(x_{n-2})-g(x_{n-3})|\leq L * L |x_{n-2}-x_{n-3}|...[/mm]
>
> >
> > zum bestimmen setzte du [mm]L:=\sup |g_1'(x)|[/mm] Wenn du den
> > Mittelwertsatz anwendest, siehst du, dass die Bedingung mit
> > [mm]g'(x)=L<1[/mm] ein bisschen schärfer als die
> > Lipschitz-Bedingung ist.
>
> Aso!, aber was ist denn das Supremum von [mm]e^{-x}?[/mm] Danke, die
> Iteration hab ich jetzt hingekriegt auch wenn ich andere
> Werte hatte als du, mit 0.5 als Startwert.
Ja ich hatte auch nicht 0.5 als Startwert, sondern f(0.5) Ist aber im Prinzip egal. Hauptsache der Wert liegt im Intervall.| 1: | function fixpo( )
| | 2: | format long;
| | 3: | c=25;
| | 4: | x =zeros(c,1);
| | 5: | x(1)= 0.5;
| | 6: | for i=1:c
| | 7: | x(i+1)= exp(-x(i));
| | 8: | end
| | 9: | x
| | 10: | end
|
>
> edit:
>
> q bzw. L lässt sich einfach berechnen denn man beachtet
> nur das Teilintervall. In diesem Falle: I=[0.3678791,1]
> max | g'(x) | = -g'(0.367) = 0.6928
Genau du nimmst die Funktion und bildest das Supremum über das Intervall. Wenn du das Intervall [0.3678791,1] nimmst, dann ist [mm]\sup_{x\in[0.3678791,1]}|g'(x)|=|g'(0.3678791)|=|e^{-0.3678791}|=0.6928\ldots[/mm]
Damit konvergiert die Folge.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:43 Fr 14.01.2011 | | Autor: | DrNetwork |
[mm] \sup_{x\in[0.3678791,1]}|g'(x)|=|g'(0.3678791)|=|e^{-0.3678791}|=0.6928\ldots
[/mm]
Danke! :)
|
|
|
|
