Fixpunktiteration < Numerik < Hochschule < Mathe < Vorhilfe
|
Status: |
(Frage) beantwortet | Datum: | 17:37 Fr 17.12.2010 | Autor: | dennis2 |
Aufgabe | Gegeben sei die Funktion [mm] f(x)=x^3-x-1 [/mm] mit einer Nullstelle im Bereich [1,2].
a) Warum versagt die Fixpunktiteration [mm] x_{i+1}=f(x_i)+x_i [/mm] mit dem Startwert [mm] x_0=2?
[/mm]
b) Formulieren Sie die Iterationsvorschrift um, um für [mm] i\rightarrow\infty [/mm] Konvergenz zu erreichen.
c) Schätzen Sie mit Hilfe von [mm] x_0 [/mm] und [mm] x_1 [/mm] ab, nach wie vielen Schritten der umformulierten Iterationsvorschrift der Fixpunkt mit einem Restfehler von [mm] 10^{-6} [/mm] gefunden wird. |
Hallo!
Zu a):
[mm] x_{i+1}=f(x_i)+x_i=x_i^3-x_i-1+x_i=x_i^3-1
[/mm]
Das bedeutet, die zugehörige Iterationsfunktion [mm] \phi [/mm] lautet [mm] \phi(x)=x^3-1.
[/mm]
Ich habe mir nun überlegt (motiviert durch ein Beispiel in der Vorlesung), dass man überprüfen könnte, ob die Funktion [mm] \phi [/mm] kontrahierend ist.
Dies ist sie für den Startwert [mm] x_0=2 [/mm] nicht, denn
[mm] |\phi'(x)|=|3x^2| [/mm] und dies nimmt für [mm] x_0=2 [/mm] den Wert 12 an, der größer als 1 ist.
Aus diesem Grund versagt die Fixpunktiteration hier.
Ist das korrekt?
Zu b):
Hier muss man jetzt den Ausdruck aus a) so umformen, dass Kontraktion gilt. Aber mir will nicht die richtige Idee kommen. Sieht hier jemand, wie man umformen könnte?
Zu c):
Hier verwende ich eine Apriori-Fehlerabschätzung, mit der man die Anzahl k der Iterationen abschätzen kann, nämlich:
[mm] ||\overline{x}-x^k||\le \bruch{q^k}{1-q}||x_1-x_0||.
[/mm]
Doch ich benötige ja die Iterationsvorschrift aus b), um rechnen zu können.
Darum wäre es sehr nett, wenn mir jemand eine Idee für eine Umformulierung geben könnte.
LG Dennis
|
|
|
|
Hallo dennis2,
> Gegeben sei die Funktion [mm]f(x)=x^3-x-1[/mm] mit einer Nullstelle
> im Bereich [1,2].
>
> a) Warum versagt die Fixpunktiteration [mm]x_{i+1}=f(x_i)+x_i[/mm]
> mit dem Startwert [mm]x_0=2?[/mm]
>
> b) Formulieren Sie die Iterationsvorschrift um, um für
> [mm]i\rightarrow\infty[/mm] Konvergenz zu erreichen.
>
> c) Schätzen Sie mit Hilfe von [mm]x_0[/mm] und [mm]x_1[/mm] ab, nach wie
> vielen Schritten der umformulierten Iterationsvorschrift
> der Fixpunkt mit einem Restfehler von [mm]10^{-6}[/mm] gefunden
> wird.
>
> Hallo!
>
> Zu a):
>
> [mm]x_{i+1}=f(x_i)+x_i=x_i^3-x_i-1+x_i=x_i^3-1[/mm]
>
> Das bedeutet, die zugehörige Iterationsfunktion [mm]\phi[/mm]
> lautet [mm]\phi(x)=x^3-1.[/mm]
>
> Ich habe mir nun überlegt (motiviert durch ein Beispiel in
> der Vorlesung), dass man überprüfen könnte, ob die
> Funktion [mm]\phi[/mm] kontrahierend ist.
>
> Dies ist sie für den Startwert [mm]x_0=2[/mm] nicht, denn
>
> [mm]|\phi'(x)|=|3x^2|[/mm] und dies nimmt für [mm]x_0=2[/mm] den Wert 12 an,
> der größer als 1 ist.
>
> Aus diesem Grund versagt die Fixpunktiteration hier.
> Ist das korrekt?
Ja.
>
> Zu b):
>
> Hier muss man jetzt den Ausdruck aus a) so umformen, dass
> Kontraktion gilt. Aber mir will nicht die richtige Idee
> kommen. Sieht hier jemand, wie man umformen könnte?
Schreibe mal f(x) so: [mm]\psi^{3}\left(x\right)-x-1=0[/mm]
und löse nach [mm]\psi\left(x\right)[/mm] auf.
[mm]\psi\left(x\right)[/mm] ist dann die neue Iterationsfunktion.
Es gilt dann: [mm]x_{i+1}=\psi\left(x_{i}\right)[/mm]
>
> Zu c):
>
> Hier verwende ich eine Apriori-Fehlerabschätzung, mit der
> man die Anzahl k der Iterationen abschätzen kann,
> nämlich:
>
> [mm]||\overline{x}-x^k||\le \bruch{q^k}{1-q}||x_1-x_0||.[/mm]
>
> Doch ich benötige ja die Iterationsvorschrift aus b), um
> rechnen zu können.
>
> Darum wäre es sehr nett, wenn mir jemand eine Idee für
> eine Umformulierung geben könnte.
>
>
>
> LG Dennis
Gruss
MathePower
|
|
|
|
|
Status: |
(Frage) beantwortet | Datum: | 18:13 Fr 17.12.2010 | Autor: | dennis2 |
$ [mm] \psi^{3}\left(x\right)-x-1=0 [/mm] $
Ich verstehe das leider nicht, begriffsstutzig wie immer.
f(x)=$ [mm] \psi^{3}\left(x\right)-x-1=0 [/mm] $ ??
|
|
|
|
|
Hallo dennis2,
> [mm]\psi^{3}\left(x\right)-x-1=0[/mm]
>
> Ich verstehe das leider nicht, begriffsstutzig wie immer.
>
> f(x)=[mm] \psi^{3}\left(x\right)-x-1=0[/mm] ??
Die gegebene Iterationsvorschrift [mm]\phi\left(x\right)[/mm] ist nicht
kontrahierend für den Startwert [mm]x_{0}=2[/mm], daher ist
die inverse Funktion [mm]\psi\left(x\right)[/mm] einzuführen.
Gruss
MathePower
|
|
|
|
|
Status: |
(Frage) beantwortet | Datum: | 18:39 Fr 17.12.2010 | Autor: | dennis2 |
Aufgabe | Hm, es geht mir immer noch kein Licht auf.
Inverse?? Wovon? |
Tut mir leid.
|
|
|
|
|
Hallo dennis2,
> Hm, es geht mir immer noch kein Licht auf.
>
> Inverse?? Wovon?
Die Inverse der Iterationsfunktion [mm]\phi\left(x\right)[/mm].
> Tut mir leid.
Gruss
MathePower
|
|
|
|
|
Status: |
(Frage) beantwortet | Datum: | 19:02 Fr 17.12.2010 | Autor: | dennis2 |
Aufgabe | Das wäre dann:
[mm] \phi(x)^{-1}=\bruch{1}{x^3-1}
[/mm]
Und das ist nun die neue Iterationsfunktion, mit der das konvergiert? |
Denn [mm] x=x^3-1=\phi(x)\gdw \phi(x)^{-1}=\bruch{1}{x^3-1}??
[/mm]
Und daher nimmt man halt diese inverse Funktion, für die ja offensichtlich gilt, dass sie für [mm] x_0=2 [/mm] kontrahierend ist?
|
|
|
|
|
Hallo dennis2,
> Das wäre dann:
>
> [mm]\phi(x)^{-1}=\bruch{1}{x^3-1}[/mm]
Das ist nicht die Inverse zu [mm]\phi\left(x\right)[/mm]
Löse doch die Gleichung
[mm]\phi\left(x\right)=x^{3}-1[/mm]
nach x auf.
>
> Und das ist nun die neue Iterationsfunktion, mit der das
> konvergiert?
Das sollte so sein.
>
> Denn [mm]x=x^3-1=\phi(x)\gdw \phi(x)^{-1}=\bruch{1}{x^3-1}??[/mm]
>
> Und daher nimmt man halt diese inverse Funktion, für die
> ja offensichtlich gilt, dass sie für [mm]x_0=2[/mm] kontrahierend
> ist?
Gruss
MathePower
|
|
|
|
|
Status: |
(Frage) beantwortet | Datum: | 19:46 Fr 17.12.2010 | Autor: | dennis2 |
Aufgabe | Achja, die Umkehrfunktion ist ja gesucht...
Wie blöd von mir!
[mm] \phi(x)^{-1}=(1+x)^{\bruch{1}{3}} [/mm] |
Okay und nun die Ableitung:
Diese lautet [mm] \bruch{1}{3(x+1)^{\bruch{2}{3}}}.
[/mm]
Dieser Ausdruck ist dann für [mm] x_0=2 [/mm] <1.
|
|
|
|
|
Hallo dennis2,
> Achja, die Umkehrfunktion ist ja gesucht...
> Wie blöd von mir!
>
> [mm]\phi(x)^{-1}=(1+x)^{\bruch{1}{3}}[/mm]
> Okay und nun die Ableitung:
>
> Diese lautet [mm]\bruch{1}{3(x+1)^{\bruch{2}{3}}}.[/mm]
>
> Dieser Ausdruck ist dann für [mm]x_0=2[/mm] <1.
>
Stimmt.
Gruss
MathePower
|
|
|
|
|
Status: |
(Mitteilung) Reaktion unnötig | Datum: | 20:59 Fr 17.12.2010 | Autor: | dennis2 |
Hier nochmal abschließend die Lösung im Überblick:
a)
[mm] x_{i+1}=f(x_i)+x_i=x_i^3-x_i-1+x_i=x_i^3-1
[/mm]
Die zugehörige Iterationsfkt. lautet demnach
[mm] \phi(x)=x^3-1.
[/mm]
Der Startwert sei [mm] x_0=2.
[/mm]
[mm] |\phi(2)'|=12>1, [/mm] d.h. die Funktion ist nicht kontrahierend. Darum versagt hier die Fixpunktiteration.
b)
Umformulierung:
[mm] x=\phi(x)=x^3-1\gdw \phi(x)^{-1}=(1+x)^{1/3}
[/mm]
Setze daher [mm] \psi(x)=(1+x)^{1/3}.
[/mm]
Mit [mm] \psi(x)'=\bruch{1}{3(x+1)^{2/3}} [/mm] folgt dann:
[mm] |\psi(2)'|=0.16025<1.
[/mm]
Zudem gilt [mm] \psi([1,2])\subseteq [/mm] [1,2] und somit "funktioniert" das Iterationsverfahren hier.
c)
Man verwende die Apriori-Fehlerabschätzung (*):
[mm] ||\overline{x}-x^k||\le \bruch{q^k}{1-q}||x^1-x^0||.
[/mm]
Wobei sich die Anzahl k der nötigen Iterationsschritte ergibt aus:
[mm] k=\log(\bruch{\epsilon (1-q)}{||x^1-x^0||})/\log(q).
[/mm]
[mm] max_{x\in [1,2]}|\psi(x)'|=\underbrace{0,16025}_{=q};
[/mm]
[mm] \epsilon=10^{-6}; [/mm]
[mm] x_0=2, x_1=\psi(2)=1.44225
[/mm]
Diese Werte eingesetzt in (*) ergeben, dass ungefähr 7,3 Iterationsschritte nötig sind: Dann ist der Fixpunkt im Intervall [1,2] bis auf einen Restfehler von [mm] 10^{-6} [/mm] approximiert.
|
|
|
|