Fixpunkt / Fixpunktiteration

21.06.2009, 14:04

pi_mal_Daumen

Auf diesen Beitrag antworten »

Fixpunkt / Fixpunktiteration

Hallo!

Wink

Ich sitzte gerade an einer Aufgabe, bei der ich allerdings nicht ganze sicher bin, was ich zu tun habe. Sie lautet wie folgt:

$\begin{eqnarray*} \textbf{Sei }g: \mathbb{R}^2 \rightarrow \mathbb{R}^2 \textbf{ eine Abbildung mit } g(x_1,x_2) = \frac{1}{5} \begin{pmatrix} 2x_2 && - && x_1x_2 &&+ && 1 \\ x_1^2 && - && x_2 && + && 3 \end{pmatrix} \end{eqnarray*}$

$\begin{eqnarray*} \textbf{a) Zeigen sie, dass die Abbildung g auf der Menge }D = [-1,1] \times [-1,1] \subset \mathbb{R}^2 \textbf{ genau einen Fixpunkt } \overline{x} \in D \textbf{ besitzt} \end{eqnarray*}$

$\begin{eqnarray*} \textbf{b) Berechnen Sie }x^1 = g(x^0) \textbf{ mit } x^0 = (0.5, 0.5)^T \end{eqnarray*}$
$\begin{eqnarray*} \textbf{ Wieviele Iterationen k benötigt man, um die Genauigkeit } \Vert \overline{x} - x^k \Vert \leq 0.01\textbf{ für den Fixpunkt } \overline{x} \in D \textbf{ zu erzielen?} \end{eqnarray*}$

Bei a) würde ich nun zeigen, dass alle Voraussetzungen für den Banachschen Fixpunktsatz erfüllt sind, also dass D abgeschlossen ist (sollte klar sein) und dass g eine Kontraktion ist, also in sich selbst abbildet und die Lipschitzbedingung erfüllt.
Liege ich damit ungefähr richtig?

Bei b) Wie genau ich vorgehen muss, ist mir bislang leider noch nicht ganz klar. Ich hoffe, dass es mir nach dem Lesen gleich bewusster ist. Hat hier vll. jemand einen Tipp? verwirrt

verwirrt

Wäre echt supi!

21.06.2009, 17:06

system-agent

Auf diesen Beitrag antworten »

Zu a)
Banach ist genau die richtige Idee !

Zu b)
Hier ist die Fragestellung ein bischen unklar:
Soll man das numerisch lösen oder eine Abschätzung der Iterationsschritte herleiten. Numerisch sollte kein Problem darstellen, eine Abschätzung müsste ich mir erst noch Gedanken darüber machen.

21.06.2009, 22:55

tigerbine

Auf diesen Beitrag antworten »

[WS] Fixpunktiterationen

Ist bei b) vielleicht die Verwendung der Abschätzung aus dem Fixpunktsatz gemeint?

22.06.2009, 15:43

pi_mal_Daumen

Auf diesen Beitrag antworten »

Danke schonmal für eure Anregungen!

Zu b) denke ich schon, dass das ganze numerisch zu lösen ist.

Also bei a) hätte ich ja nun 3 Sachen zu zeigen:

Abgeschlossenheit von D. Dies setzte ich nun einfach mal so als Vorwissen aus Ana2 vorraus, da D ja nunmal als kartesisches Produkt von abgeschlossenen Intervallen abgeschlossen ist.
g ist eine Selbstabbildung, also es gilt $\begin{eqnarray*} g(D) \subset D \end{eqnarray*}$
Es existiert ein $\begin{eqnarray*} 0 \leq \theta < 1 \end{eqnarray*}$ , sodass gilt: $\begin{eqnarray*} \Vert g(x_1,x_2) - g(y_1,y_2) \Vert \leq \theta \cdot \Vert (x_1,x_2)^T - (y_1,y_2)^T \Vert \end{eqnarray*}$

Verstehe leider noch nicht ganz, wie ich 2 und 3 zeigen soll.
Vor allem bei 3: Stelle ich das ganze nur nach Theta um, und zeige so, dass dieses kleiner als 1 sein muss? Ist es egal, welche Norm man hierbei verwendet?
Und wie gehe ich bei 2. am klügsten vor?
Irgendwie dämmerts leider noch nicht so recht bei mir. unglücklich

unglücklich

22.06.2009, 15:50

tigerbine

Auf diesen Beitrag antworten »

Die Checkliste ist richtig. Ich würde für die Selbstabbildung versuche, ob man schon mit groben Abschätzung hinkommt.

$\begin{eqnarray*} g(x_1) = \frac{1}{5} (2x_2 - x_1x_2 + 1) \leq \frac{1}{5} (2+1+1) = \frac{4}{5} < 1 \end{eqnarray*}$

$\begin{eqnarray*} g(x_1) = \frac{1}{5} (2x_2 - x_1x_2 + 1) \geq \frac{1}{5} (-2-1+1) = -\frac{2}{5} >- 1 \end{eqnarray*}$

22.06.2009, 16:14

pi_mal_Daumen

Auf diesen Beitrag antworten »

Ach du meinst also so, dass ich die Funktionswerte versuche möglichst groß/klein zu machen, und dass diese dann in dem geforderten Intervall liegen? Klingt ja eigentlich recht intuitiv.

Also habe ich mal die zu erwartenden maximalen/minimalen Funktionwerte berechnet, und bekomme herraus:
$\begin{eqnarray*} <br /> g(1,1) = \frac{1}{5} \begin{pmatrix} 2-1+1 \\ 1-1+3 \end{pmatrix} = \begin{pmatrix} \frac{2}{5} \\ \frac{3}{5} \end{pmatrix} \in D<br /> <br /> g(1,-1) = \frac{1}{5} \begin{pmatrix} -2+1+1 \\ 1+1+3 \end{pmatrix} = \begin{pmatrix} 0 \\ 1 \end{pmatrix} \in D<br /> <br /> g(-1,1) = \frac{1}{5} \begin{pmatrix} 2+1+1 \\ 1-1+3 \end{pmatrix} = \begin{pmatrix} \frac{4}{5} \\ \frac{3}{5} \end{pmatrix} \in D<br /> <br /> g(-1,-1) = \frac{1}{5} \begin{pmatrix} -2-1+1 \\ 1+1+3 \end{pmatrix} = \begin{pmatrix} -\frac{2}{5} \\ 1 \end{pmatrix} \in D \end{eqnarray*}$

Größer und kleiner können die Werte auch nicht werden. Das zeigt letztendlich ja, dass die Funktion in D abbildet.

Fehlt also noch die Kontraktionseigenschaft.
Kann ich denn ähnlich vorgehen, wie oben beschrieben? Ich versuch einfach mal bisschen was zu berechnen...

Anzeige

22.06.2009, 16:21

tigerbine

Auf diesen Beitrag antworten »

Zitat:

Original von pi_mal_Daumen
Ach du meinst also so, dass ich die Funktionswerte versuche möglichst groß/klein zu machen, und dass diese dann in dem geforderten Intervall liegen? Klingt ja eigentlich recht intuitiv.

Ja, das muss nicht immer klappen. Aber eh ich in 2D eine "Kurvendiskussion" mache, lohnt sich imho ein solcher Versuch. Wenn es dann schon klappt, ist man fertig. Aber beachte, ich habe x1 x2 in jedem Auftreten unabhängig maximiert/minimiert. Also durchaus denkbar, dass ich sowas mache:

$\begin{eqnarray*} x_2-2x_2 \leq 1 -2(-1) = 1+2=3 \end{eqnarray*}$

Du checkst nur 4 Punkte. Das reicht nicht aus. Ich schätze die Kombinationen der Punkte sehr großzügig ab. Damit habe ich die Funktion auf der ganzen Menge abgeschätzt.

22.06.2009, 16:42

pi_mal_Daumen

Auf diesen Beitrag antworten »

Aber im Prinzip können meine Werte ja nicht größer/kleiner werden, wenn ich einen der Parameter meiner 4 Punkte (innerhalb des gültigen Intervals) abändere.
Wäre einer der Parameter $\begin{eqnarray*} \notin \lbrace -1, 1 \rbrace \end{eqnarray*}$ , würden die einzelnen Werte, da die sich aus einer Protenz / eines Produktes ergeben, ja nur weniger zum Wachsen bzw. Schrumpfen der Summe beitragen.

Aber gut... das geht bestimmt in die Richtung Beweis durch Beispiel

Kann ich denn überhaupt so formal korrekt argumentieren, wenn ich nur $\begin{eqnarray*} g(x_1) \end{eqnarray*}$ schreibe? Immerhin benötige ich ja ein Argument aus $\begin{eqnarray*} D \subset \mathbb{R}^2 \end{eqnarray*}$
Wie meinst du das überhaupt genau mit diesem einzelnen Argument? Dass egal, welchen Wert man aus D nimmt, maximal/minimal folgendes gilt...?

Nebenbei: Mit den $\begin{eqnarray*} \frac{1}{5} \end{eqnarray*}$ da oben meinst du doch $\begin{eqnarray*} \frac{4}{5} \end{eqnarray*}$ , oder?

22.06.2009, 16:55

tigerbine

Auf diesen Beitrag antworten »

1. Tippfehler

2. Formale Faulheit meinersets. Ich will eben komponentenweise untersuchen, damit ich in IR bin. Man müsste das wohl so schreiben

$\begin{eqnarray*} g(x_1,x_2)_1 \end{eqnarray*}$

3. Das mit deinen Punkten haut deswegen nicht hin, weil du die Kombinationen von x1, x2 nicht berücksichtigst.

Nun mal zu meinem Ansatz. Nehmen wir nur den Term:

$\begin{eqnarray*} \frac{1}{5} (2x_2 - x_1x_2 + 1) \end{eqnarray*}$

Da kommt 2mal x2 vor und 1mal x1. Ich suche mir nun 3xmal das so aus, dass ich den Term maximal groß bekomme. Also Schritt 1:

$\begin{eqnarray*} \frac{1}{5} (2\cdot 1 - x_1x_2 + 1) \end{eqnarray*}$

Schritt 2: Produkt x1x2 muss negativ sein. Und maximal sein. Nur zum verdeutlichen wähle ich eben nun x2=-1 und x1=1.

$\begin{eqnarray*} \frac{1}{5} (2\cdot 1 - 1 \cdot (-1) + 1) \end{eqnarray*}$ (*)

Ich hätte es auch andersherum tun können. Dann hätte ich g(1,-1) bestimmt. Das wäre aber nur g an einer bestimmen Stelle. Hilft mir nicht weiter. Mit meinem (*) kann ich aber sagen, dass g in der ersten Komponente immer kleiner ist als 4/5.

Verstehst du nun den Unterschied?

22.06.2009, 17:09

pi_mal_Daumen

Auf diesen Beitrag antworten »

Ok! Habs geschnallt! Danke Augenzwinkern

Augenzwinkern

So ungefährt meinte ich auch, dass du das so meinst...

Wenn ich nun die 2. Komponente so abschätze, würde es also ca. so aussehen (sofern ich mich nicht täusche):

$\begin{eqnarray*} g(x_2) = \frac{1}{5} (x_1^2 - x_2 +3) \leq \frac{1}{5}(1+1+3) = 1 \leq 1 \end{eqnarray*}$

$\begin{eqnarray*} g(x_2) = \frac{1}{5} (x_1^2 - x_2 + 3) \geq \frac{1}{5}(1-1+3) = \frac{3}{5} \geq -1 \end{eqnarray*}$

Zumindest wäre es mir nun so klar... auch wenn die Bezeichnung $\begin{eqnarray*} g(x_2) \end{eqnarray*}$ etc.. etwas irreführens sein mag Augenzwinkern

Augenzwinkern

Aber das Prinzip ist mir denke ich klaro smile

smile

Bleibt der wohl noch schwerste Teil von allem...

22.06.2009, 17:12

tigerbine

Auf diesen Beitrag antworten »

Da stimmt noch was nicht.

$\begin{eqnarray*} g(x_2) = \frac{1}{5} (x_1^2 - x_2 + 3) \geq \frac{1}{5}(0-1+3) = \frac{2}{5} \geq -1 \end{eqnarray*}$

Wie du die Komponenten formal nennst ist *mir* egal. Schreib es so, dass es dein Korrektor versteht.

Ja, nun kommt der Kampf um die Kontraktionskonstante. Und die sollte am besten möglichst genau sein. Da man sie imho bei b) braucht.

22.06.2009, 17:41

pi_mal_Daumen

Auf diesen Beitrag antworten »

Ups... natürlich ist $\begin{eqnarray*} 0^2 \end{eqnarray*}$ kleiner als $\begin{eqnarray*} 1^2 \end{eqnarray*}$ ! Danke *g*

Ich habe nun eine vage Vermutung für die Kontraktionskonstante:

Wenn ich jetzt meine in 3. angegebene Ungleichung nach $\begin{eqnarray*} \theta \end{eqnarray*}$ umstelle, bekomme ich ja herraus:

$\begin{eqnarray*} \frac{\Vert g(x) - g(y) \Vert}{\Vert x - y \Vert} \leq \theta \end{eqnarray*}$

Jetzt erkenne ich zumindest ne starke Ähnlichkeit zum Mittelwertsatz, welche ja besagt, dass gilt:

$\begin{eqnarray*} \frac{\vert f(a) - f(b)\vert}{\vert a-b \vert} = f'(x_0) \end{eqnarray*}$

Die Ableitung von g ist ja nun die Jacobi-Matrix $\begin{eqnarray*} J_g = \begin{pmatrix} -x_2 & 2-x_1 \\ 2x_1 & 1 \end{pmatrix} \end{eqnarray*}$

Allerdings habe ich nun keine Ahnung, wie ich hiervon aus an mein genaues Theta kommen soll....

22.06.2009, 17:59

tigerbine

Auf diesen Beitrag antworten »

Ich bin nun erstmal nicht verfügbar. Wenn jemand anderes weiter machen möchte, soll er dies tun.

22.06.2009, 18:15

pi_mal_Daumen

Auf diesen Beitrag antworten »

Schade... aber danke für deine Bemühungen!

22.06.2009, 19:11

pi_mal_Daumen

Auf diesen Beitrag antworten »

Also ich habe bei der Jacobi-Matrix noch die 1/5 vergessen und nen Vorzeichenfehler entdeckt... Letztendlich bekäme ich herraus:

$\begin{eqnarray*} J_g = \begin{pmatrix} -\frac{x_2}{5} & \frac{2-x_1}{5} \\ \frac{2x_1}{5} & -\frac{1}{5} \end{pmatrix} \end{eqnarray*}$

Wenn ich auf das ganze nun die Maximumsnorm anwende und das ganze abschätze, bekomme ich herraus.

$\begin{eqnarray*} \Vert \begin{pmatrix} -x_2/5 & (2-x_1)/5 \\ (2x_1)/5 & 1/5 \end{pmatrix} \Vert_{\infty} \leq \Vert \begin{pmatrix} 1/5 & 3/5 \\ 2/5 & -1/5 \end{pmatrix} \Vert_{\infty} = \frac{4}{5} < 1 \end{eqnarray*}$

Die Frage ist: Kann ich einfach mit der Supremumsnorm argumentieren und könnte ich die 4/5 nun als mein $\begin{eqnarray*} \theta \end{eqnarray*}$ verwenden?

23.06.2009, 23:14

tigerbine

Auf diesen Beitrag antworten »

Bitte an die Kollegen mal hier zu übernehmen. Mir fehlt die Zeit und da soll der Threadsteller doch nicht drunter leiden. Danke Blumen

Blumen

24.06.2009, 13:26

tigerbine

Auf diesen Beitrag antworten »

Imho muss es nur eine induzierte Matrixnorm sein. Die kannst du also nehmen. Damit könntest du das 4/5 verwenden.

27.06.2009, 17:48

pi_mal_Daumen

Auf diesen Beitrag antworten »

Hi! Ich melde mich noch einmal, da ich es angebracht finde, die gelöste Aufgabe noch zu präsentieren.
Habe sie immerhin so gelöst bekommen, dass ich sie noch vorrechnen sollte Augenzwinkern

Augenzwinkern

Also:

Beweis zum ersten Teil:
Zu Zeigen:

D ist abgeschlossen
g ist Selbstabbildung, also $\begin{eqnarray*} f(D) \subset D \end{eqnarray*}$
$\begin{eqnarray*} \exists 0 \leq \theta < 1: \Vert g(x) - g(y) \Vert \leq \theta \Vert x-y \Vert \forall x,y \in D \end{eqnarray*}$

Sollte klar sein mit ein wenig Analysis Kenntnissen
Komponentenweise Abschätzung zur 1. Komponente:

$\begin{eqnarray*} g(x_1,x_2)_1 = \frac{1}{5}(2x_2 - x_1x_2 +1) \leq \frac{1}{5}(2+1+1) = \frac{4}{5} < 1 \end{eqnarray*}$
$\begin{eqnarray*} g(x_1,x_2)_1 = \frac{1}{5} (2x_2 - x_1x_2 + 1) \geq \frac{1}{5} (-2-1+1) = -\frac{2}{5} >- 1 \end{eqnarray*}$

Komponentenweise Abschätzung zur 2. Komponente:

$\begin{eqnarray*} g(x_1,x_2)_2 = \frac{1}{5} (x_1^2 - x_2 +3) \leq \frac{1}{5}(1+1+3) = 1 \leq 1 \end{eqnarray*}$
$\begin{eqnarray*} g(x_1,x_2)_2 = \frac{1}{5} (x_1^2 - x_2 + 3) \geq \frac{1}{5}(0-1+3) = \frac{2}{5} \geq -1 \end{eqnarray*}$
Aus der Analysis weiß man, dass D als kart. Produkt aus Intervallen eine konvexe Menge und g stetig diffbar ist.

$\begin{eqnarray*} \overset{\textbf{Lemma 4.2 (Buch Deuflhard)}}{\Rightarrow} \theta := \underset{z \in D}{\sup} \Vert g'(z) \Vert_\infty \end{eqnarray*}$

$\begin{eqnarray*} \Vert \begin{pmatrix} -x_2/5 & (2-x_1)/5 \\ (2x_1)/5 & -1/5\end{pmatrix} \Vert_\infty \overset{\textbf{Abschätzung nach oben}}{\leq} \Vert \begin{pmatrix} -x_2/5 & (2-x_1)/5 \\ (2x_1)/5 & -1/5\end{pmatrix} \Vert_\infty = \frac{4}{5} < 1 \end{eqnarray*}$

Mit 1) 2) und 3) und dem Banachschen Fixpunktsatz ergibt sich, dass $\begin{eqnarray*} g \end{eqnarray*}$ auf $\begin{eqnarray*} D \end{eqnarray*}$ einen einzigen Fixpunkt $\begin{eqnarray*} \overline{x} \in D \end{eqnarray*}$ besitzt.

Beweis zum zweiten Teil:

Sei $\begin{eqnarray*} x^0 = (0.5, 0.5)^T \end{eqnarray*}$ . Somit ergibt sich für
$\begin{eqnarray*} x^1 = g(x^0) = \frac{1}{5} \begin{pmatrix} 2*\frac{1}{2} - \frac{1}{4} +1 \\ \frac{1}{4} - \frac{1}{2} + 3 \end{pmatrix} = \begin{pmatrix} 7/20 \\ 11/20 \end{pmatrix} \end{eqnarray*}$

Die Anzahl k der Iterationen, die benötigt wird, um die Genauigkeit $\begin{eqnarray*} \Vert \overline{x} - x^k \Vert_\infty \leq 0.01 := \epsilon \end{eqnarray*}$ für $\begin{eqnarray*} \overline{x} \in D \end{eqnarray*}$ zu erzielen, berechnet man (nach Vorlesung) mit:

$\begin{eqnarray*} k \geq \frac{\log (\frac{\epsilon(1-\theta)}{\Vert x^1-x^0 \Vert})}{\log(\theta)} \approx 20 \end{eqnarray*}$

Man benötigt also ca. 20 Iterationen.

So... vll. hilfts dem einen oder anderen ja noch einmal!

Vielen Dank für die Hilfe auf jeden Fall nochmal!! Gott

Gott

28.06.2009, 00:30

tigerbine

Auf diesen Beitrag antworten »

Das nenne ich mal einen sehr lobenswerten Threadabschluss! Freude

Freude

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »