Fixpunkt, Konvergenz...

06.12.2008, 12:34

Svenja1986

Auf diesen Beitrag antworten »

Fixpunkt, Konvergenz...

Hey

Wink

Bei folgender Aufgabe habe ich ziemlich Probleme:

(a)
Es sei $\begin{eqnarray*} f: \mathbb{R} \rightarrow \mathbb{R} \end{eqnarray*}$ eine sog. kontrahierende Selbstabbildung der reellen Zahlen, d. h. es gebe eine LIPSCHITZ-Konstante $\begin{eqnarray*} L \in [0;1) \end{eqnarray*}$ , so dass

$\begin{eqnarray*} |f(x) - f(y)| \leq L \cdot |x-y| \end{eqnarray*}$

für alle x und y aus $\begin{eqnarray*} \mathbb{R} \end{eqnarray*}$ gilt.
Zeigen Sie bitte, dass f einen Fixpunkt besitzt, also einen Punkt $\begin{eqnarray*} x \in \mathbb{R} \end{eqnarray*}$ mit f(x)=x, gegen den die rekursiv duch $\begin{eqnarray*} x_{n+1} := f(x_n) \end{eqnarray*}$ zu einem beliebigen Startwert $\begin{eqnarray*} x_0 \in \mathbb{R} \end{eqnarray*}$ erklärte Folge $\begin{eqnarray*} (x_n)_{n \in \mathbb{N}_0} \end{eqnarray*}$ konvergiert.

(b)
Weisen Sie bitte die Konvergenz der rekursiv definierten Folge
$\begin{eqnarray*} a_{n+1} := \sqrt{1+a_n}, a_0 \geq -1 \end{eqnarray*}$
nach und bestimmen Sie bitte auch deren Grenzwert!

Meine 1. Frage: Was ist eine kontrahierende Selbstabbildung? verwirrt

verwirrt

2. Frage: Wie gehe ich an die Aufgabe am besten ran?

06.12.2008, 12:37

tigerbine

Auf diesen Beitrag antworten »

RE: Fixpunkt, Konvergenz...
Lies die mal den Fixpunktsatz von Banach durch. Bis später Wink

Wink

Zitat:

Original von tigerbine
Für weitere Betrachtungen von Fixpunktiterationen, benötigen wir den Banachschen Fixpunktsatz.

Voraussetzungen

V ist ein Banachraum
$\begin{eqnarray*} \Phi:~X \to X \end{eqnarray*}$ ist eine Selbstabbildung,d.h. $\begin{eqnarray*} \text{Im}(\Phi) \subseteq X \end{eqnarray*}$
X ist eine abgeschlossene Teilmenge von V
$\begin{eqnarray*} \Phi:~X \to X \end{eqnarray*}$ ist eine Kontraktion

$\begin{eqnarray*} ||\Phi(x)-\Phi(y)|| \leq \kappa \cdot ||x-y|| \quad x,y \in X,~\kappa(0,1) \end{eqnarray*}$

Folgerungen

$\begin{eqnarray*} \Phi \end{eqnarray*}$ besitzt genau einen Fixpunkt $\begin{eqnarray*} x^x \in X,~\Phi(x^*)=x^* \end{eqnarray*}$
$\begin{eqnarray*} x_{k+1}:=\Phi(x_k),~k=0,1,2,... \end{eqnarray*}$

$\begin{eqnarray*} \{x_k\} \to x^* \end{eqnarray*}$
Fehlerabschätzung:

$\begin{eqnarray*} \text{a priori: } ||x_k-x^*|| \leq \frac{\kappa^k}{1-\kappa}\cdot ||x^0-x^1|| \end{eqnarray*}$

$\begin{eqnarray*} \text{a posteriori: } ||x_{k+1}-x^*|| \leq \frac{\kappa}{1-\kappa}\cdot ||x^{k+1}-x^{k}|| \end{eqnarray*}$

06.12.2008, 13:05

tigerbine

Auf diesen Beitrag antworten »

Aufgabe b.

Zitat:

$\begin{eqnarray*} a_{n+1} := \sqrt{1+a_n}, a_0 \geq -1 \end{eqnarray*}$

Machen wir eine Iterationsfunktion daraus. Die soll auf Fixpunkt(e) untersucht werden.

$\begin{eqnarray*} g(x):=\sqrt{1+x} \end{eqnarray*}$

Nun können wir (Argumente sicherlich erwünscht - Kleine Kurvendiskussion - Ich benutze den Plot) uns auf ein Kompaktes Intervall des Banachraums IR beschränken. Es gibt nur einen Fixpunkt, grob sieht man dass er im Intervall [1,2] liegt. Es ist

$\begin{eqnarray*} g(1)=\sqrt{2} > 1 \end{eqnarray*}$

$\begin{eqnarray*} g(2)=\sqrt{3} < 2 \end{eqnarray*}$

Die Funktion ist(auf dem Intervall) streng monoton steigend

$\begin{eqnarray*} g'(x)=\frac{1}{2} \cdot \frac{1}{\sqrt{1+x}} >0 \end{eqnarray*}$

Liegt nun eine Kontraktion vor?

$\begin{eqnarray*} g'(1)=\frac{1}{2} \cdot \frac{1}{\sqrt{2}} \approx 0.36 \end{eqnarray*}$

$\begin{eqnarray*} g'(2)=\frac{1}{2} \cdot \frac{1}{\sqrt{3}} \approx 0.29 \end{eqnarray*}$

Also können wir wählen:

$\begin{eqnarray*} \kappa = 0.36 \end{eqnarray*}$

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:

Fixpunkt Berechnung mit Banach
 
Intervallgrenzen [a,b] eingeben: [1,2]
 
Startwert eingeben.                  x0 = 1
Genauigkeit eingeben.               eps = 10^(-5)
Kontraktionskonstante eingebeben. kappa = 0.36
N =
    11
 
Index    Funktionswert    a-posteriori
=======================================
  1        1.000000       100.000000 
  2        1.414214       0.232995 
  3        1.553774       0.078503 
  4        1.598053       0.024907 
  5        1.611848       0.007759 
  6        1.616121       0.002404 
  7        1.617443       0.000743 
  8        1.617851       0.000230 
  9        1.617978       0.000071 
  10        1.618017       0.000022 
  11        1.618029       0.000007

Analytisch hätten wir folgendes zu lösen gehabt. (Stoff Klasse 9, quadr. Gleichungen)

$\begin{eqnarray*} x=\sqrt{1+x} \end{eqnarray*}$

$\begin{eqnarray*} x^2=1+x \end{eqnarray*}$

$\begin{eqnarray*} x^2-x-1=0 \end{eqnarray*}$

$\begin{eqnarray*} x_{1,2} = \frac{1\pm\sqrt{1+4}}{2} \end{eqnarray*}$

Es kommt nur eine Lösung in Frage. (quadr. ist keine Äquivalenzumformung)

$\begin{eqnarray*} x_1=0.5 + 0.5\cdot \sqrt{5} \approx 1.618033989 \end{eqnarray*}$

07.12.2008, 11:17

Svenja1986

Auf diesen Beitrag antworten »

RE: Fixpunkt, Konvergenz...

Zitat:

Original von tigerbine
Lies die mal den Fixpunktsatz von Banach durch.

Ok, und wie wende ich den jetzt auf die Aufgabe an?
Also, wie kann ich zeigen, dass f einen Fixpunkt besitzt? verwirrt

verwirrt

unglücklich

07.12.2008, 11:46

Soz.Päd.

Auf diesen Beitrag antworten »

Guten Tag,

mein Vorschlag:
formuliere zunächst
Betrag ( f(x(n+1) - f(x(n) ) < L ( x(n+1) - x(n) )
laut der gegebenen Definition von x(n+1) um. Dachach überlegen, wie man durch die Dreieckungleichung den Term
" Betrag ( f(x(n+1) - f(x(0) ) "
abschätzen könnte (Hinweis: "geometrische Reihe"); daraus folgern, dass die definierte Folge x(n) konvergiert.

Wie könnte man nun folgern, für
x := lim (n gegen unendlich) x(n)
gilt: x = f(x) ?

Weiterhin stellt sich die Frage: Muss man nachweisen, dass f genau einen (also nicht mehrere) Fixpunkte hat? Wenn ja, wie wäre das möglich?

Gruß
Soz.Päd.

07.12.2008, 11:52

tigerbine

Auf diesen Beitrag antworten »

@ Soz Päd:

Auf welche Aufgabe beziehst du dich? Bei a ist imho die Folge nicht bekannt. Der Beweis soll allgemein sein.

GRuß Wink

Wink

Anzeige

07.12.2008, 11:56

Soz.Päd.

Auf diesen Beitrag antworten »

Guten Tag,

an tigerbiene:
Ja, das hätte ich genauer sagen müssen; ich beziehe mich auf a).
Der Beweis, so denke ich, ist aber so O.K, denn man kann ein beliebiges x0 wählen, die Folge konveriert immer gegen x, so dass
f(x) = x.

Gruß
Soz.Päd.

07.12.2008, 11:58

tigerbine

Auf diesen Beitrag antworten »

Es ging mir um diesen Wortlaut

Zitat:

laut der gegebenen Definition von x(n+1) um.

Diese vermute ich mal, gibt es da nicht. Aus dem Gegebenen würde ich vermuten, dass man entweder auf Banach verweisen kann oder in den Beweis des Fixpunktsatzes schaut.

Gruß

07.12.2008, 12:02

Svenja1986

Auf diesen Beitrag antworten »

Zitat:

Original von Soz.Päd.
mein Vorschlag:
formuliere zunächst
Betrag ( f(x(n+1) - f(x(n) ) < L ( x(n+1) - x(n) )
laut der gegebenen Definition von x(n+1) um.

Wie meinst du das genau?

$\begin{eqnarray*} |f(x_{n+1}) - f(x_n)| \leq L \cdot | x_{n+1} - x_n | \end{eqnarray*}$

Und das jetzt umformulieren?

07.12.2008, 12:02

Soz.Päd.

Auf diesen Beitrag antworten »

Guten Tag,

ja, ich meinte, für
x(n+1) setzen: f(x(n).

Nun dann mit der Dreiecksunglichung rumhantieren.

Gruß
Soz.Päd.

07.12.2008, 12:08

Svenja1986

Auf diesen Beitrag antworten »

$\begin{eqnarray*} |f(x_{n+1}) - f(x_n)| \leq L \cdot | f(x_n) - x_n | \end{eqnarray*}$

So? Oder habe ich das falsch verstanden?

07.12.2008, 12:16

Soz.Päd.

Auf diesen Beitrag antworten »

Guten Tag,

O.K, ich versuche mal genauer zu zeigen, was ich meine:
Nehmen wir mal ein beliebiges m e N. Dann gilt für alle n> m:
Ich zuvor für m = 0 gewält, weil ich dachte, man sieht dann besser, dass es auf die Eigenschaften einer geometrischen Reihe hinausläuft... .

Betrag ( f(xn) - f(xm) ) = Betrag ( f(xn) - f(xn-1) + f(xn-1)) ... - f(xm) ) <=
Betrag ( f(xn) - f(xn-1) ) + Betrag (fxn-1) - f(xn-2) + ...
Betrag (f(xm+1) - f(xm)) ...

Nun Versuche, diese einzelnen Terme "rekursiv" abzuschätzen.
Gruß
Soz.Päd.

07.12.2008, 12:25

Soz.Päd.

Auf diesen Beitrag antworten »

Guten Tag,

vielleicht noch ein kleiner Hinweis:

versuche doch, den Ausdruck
" Betrag ( f(xn+1) - f(xn) ) "
abzuschätzen, indem du dies in Abhängigkeit von
" Betrag (x1 - x0) = Betrag ( f(x0) - x0) "
tust (in der Reihe also immer weiter "zurückgehen").

Gruß
Soz.Päd.

07.12.2008, 13:31

Svenja1986

Auf diesen Beitrag antworten »

Ich danke schon mal für eure Hilfe und Bemühungen smile

smile

Irgendwie stehe ich aber gerade leider voll auf dem Schlauch...
Weiß gerade nicht so wirklich was mit euren Tipps anzufangen unglücklich

unglücklich

Wahrscheinlich ist es gar nicht mal so schwer, aber irgendwie klappt gerade gar nichts verwirrt

verwirrt

07.12.2008, 13:39

tigerbine

Auf diesen Beitrag antworten »

Also Aufgabe b steht ja schon komplett da. unglücklich

unglücklich

07.12.2008, 13:53

Svenja1986

Auf diesen Beitrag antworten »

Zitat:

Original von tigerbine
Also Aufgabe b steht ja schon komplett da. unglücklich

unglücklich

Ja, ich weiß. Danke smile

smile

Aber die a macht mir Probleme unglücklich

unglücklich

07.12.2008, 14:02

tigerbine

Auf diesen Beitrag antworten »

Zitat:

Original von Svenja1986
Ja, ich weiß. Danke smile

smile

Hast du denn auch verstanden, warum das so geht?

07.12.2008, 14:03

Soz.Päd.

Auf diesen Beitrag antworten »

Guten Tag,

Betrag (f(xn+1) - f(xn) ) < L * ( x(n+1) - x(n) ) =
L * ( f(xn) - f(xn-1) ) <
L * ( L * ( (x(n) - x(n-1)) =
L * (L * ( f(xn-1) - f(xn-2) < ....

Gruß
Soz.Päd.

07.12.2008, 14:17

Svenja1986

Auf diesen Beitrag antworten »

Zitat:

Original von Soz.Päd.
L * (L * ( f(xn-1) - f(xn-2) < ....

$\begin{eqnarray*} L \cdot ( L \cdot ( L \cdot | x_{n-1}-x_{n-2}|)) \end{eqnarray*}$ = $\begin{eqnarray*} L \cdot ( L \cdot ( L \cdot | f(x_{n-2})-f(x_{n-3})|)) < ... \end{eqnarray*}$ usw.

verwirrt

verwirrt

07.12.2008, 14:36

Soz.Päd.

Auf diesen Beitrag antworten »

Guten Tag,

ja, so könnte man nun weitermachen. Für jeden Term
"Betrag ( f(xn+1) - f(xn)) .... " hat man nun Abschätzungen, die an die Glieder der geometrischen Reihe erinnern.

L ist ja konstant ist, so dass man sich eine geometrische Reihe "zusammensetzen" kann;

Dadurch könntest du den Ausdruck
" Betrag ( f(n) - f(m) ) " für ein festes m e N, für alle n > m
abschätzen (siehe vorherige Beiträge, indem man sich die Dreiecksungleichung zu Hilfe nimmt).

Gruß
Soz.Päd.

07.12.2008, 15:31

Svenja1986

Auf diesen Beitrag antworten »

Zitat:

Original von Soz.Päd.
Dadurch könntest du den Ausdruck
" Betrag ( f(n) - f(m) ) " für ein festes m e N, für alle n > m
abschätzen (siehe vorherige Beiträge, indem man sich die Dreiecksungleichung zu Hilfe nimmt).

$\begin{eqnarray*} |f(n) - f(m)| \leq |f(n)| + |f(m)| \end{eqnarray*}$

07.12.2008, 18:25

Soz.Päd.

Auf diesen Beitrag antworten »

Guten Tag,

Nochmals zusammengefasst:

Es sei ein festes m e N. Dann gilt für alle n > m.

Ungleichung 1:
Betrag ( f(xn) - f(xm) ) = Betrag ( f(xn) - f(xn-1) + f(xn-1)) ... - f(xm) ) <=
Betrag ( f(xn) - f(xn-1) ) + Betrag (fxn-1) - f(xn-2) + ...
Betrag (f(xm+1) - f(xm)) ...

Nun können wir
"Betrag ( f(xn) - f(xn-1) ) + Betrag (fxn-1) - f(xn-2) + ...
Betrag (f(xm+1) - f(xm)) "

wie zuvor abschätzen, also:
Betrag (f(xm+1) - f(xm)) < L * Betrag ( x(m+1) - x(m) ) =
L * Betrag ( f(xm) - x(m) )

Betrag (f(xm+2) - f(xm+1)) < L * Betrag ( x(m+2) - x(m+1) ) =
L * Betrag ( (f(xm+1) - f(xm) ) <
L * (L * Betrag ( x(m+1) - x(m) ) =
L * (L * Betrag ( f(xm) - x(m) )

usw. bis zu "n" .

Daraus könnte man nun "Ungleichung 1" wie bei den Giedern einer geometrischen Reihe abschätzen. Die "Konstante"
" Betrag ( (f(xm) - x(m) ) "
könnte man nun auf gleiche Weise wie bei dieser Prodezur abschätzen, indem man bis auf x0 zurückgeht.

Nun folgere, dass die Folge x(n) konvergiert und für den Grenzwert x gelten muss:
f(x) = x.

Gruß
Soz.Päd.

10.12.2008, 17:53

Svenja1986

Auf diesen Beitrag antworten »

Zitat:

Original von tigerbine
Hast du denn auch verstanden, warum das so geht?

Warum kann man denn $\begin{eqnarray*} a_n \end{eqnarray*}$ einfach durch x ersetzen?

10.12.2008, 17:56

tigerbine

Auf diesen Beitrag antworten »

Naja, wie man es nennt ist doch egal. Wichtig ist nur, dass die Beziehung erhalten bleibt.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »