Abschätzung zu Fixpunktiterationen

28.11.2007, 16:57

Fletcher

Abschätzung zu Fixpunktiterationen

Guten Abend,

sitze gerade vor folgenden Problem und komme einfach nicht weiter.

Es sei D Teilmenge des R^n abgeschlossen, $\begin{eqnarray*} \Phi: D \rightarrow D \end{eqnarray*}$ eine kontrahierende Abbildung mit der Kontraktionszahl $\begin{eqnarray*} k \in [0,1[ \end{eqnarray*}$ und dem Fixpunkt $\begin{eqnarray*} x^* \end{eqnarray*}$ . Weiter gebe es ein $\begin{eqnarray*} \epsilon > 0 \end{eqnarray*}$ und eine Funktion $\begin{eqnarray*} \hat{\Phi}: D \rightarrow D \end{eqnarray*}$ mit

$\begin{eqnarray*} ||\hat{\Phi}(x)-\Phi(x)|| \leq \epsilon \end{eqnarray*}$ für alle x in D.

Für eine beliebigen, festen Startwert x_0 betrachten wir die beiden Fixpunktiterationsfolgen:

$\begin{eqnarray*} x_{i+1}=\Phi (x_i) \end{eqnarray*}$ und $\begin{eqnarray*} x_{i+1}=\hat{\Phi} (x_i) \end{eqnarray*}$

Zeige:

a) $\begin{eqnarray*} ||x_n-\hat{x_n}|| \leq \epsilon \sum_{i=0}^{n-1}k^i \end{eqnarray*}$

b) $\begin{eqnarray*} ||x^*-\hat{x_n}|| \leq \frac{1}{1-k}(k^n||x_0-x_1||+\epsilon(1-k^n)) \\ \leq \frac{1}{1-k}(k^n||x_0-\hat{x_1}||+\epsilon ) \end{eqnarray*}$

Bei der a) habe ich mir schon Gedanken gemacht, schließlich ist ja \Phi kontrahierend und somit kann ich diese Eigenschaft verwenden, jedoch ist mir nicht klar an welcher Stelle, ich habe versucht zusätzliche Glieder einzufügen, aber dann komme ich auch nicht weiter! Hat bitte jemand einen Tip für mich.

Bei der b) geht man ja analog vor, man muss die Kontraktionseigenschaften verwenden und die Ungleichung mit dem Epsilon von oben, aber meine Frage ist wie und wo ich das anwende?

Kann mir bitte jemand weiterhelfen?

07.12.2007, 18:08

Ambrosius

Auf diesen Beitrag antworten »

RE: Abschätzung zu Fixpunktiterationen
Muss es nicht statt

Zitat:

Original von Fletcher

$\begin{eqnarray*} x_{i+1}=\Phi (x_i) \end{eqnarray*}$ und $\begin{eqnarray*} x_{i+1}=\hat{\Phi} (x_i) \end{eqnarray*}$

eher so heißen

$\begin{eqnarray*} x_{i+1}=\Phi (x_i) \end{eqnarray*}$ und $\begin{eqnarray*} \hat{x}_{i+1}=\hat{\Phi} (x_i) \end{eqnarray*}$

Also ein Hut/Dach (wie auch immer) beim zweiten?

Falls ja, geht Teil (a) so

$\begin{eqnarray*} ||x_n - \hat{x}_n || = ||\Phi(x_n) - \hat{\Phi}(\hat{x}_n) || = ||\Phi(x_n) - \Phi(x_{n-1}) + \Phi(x_{n-1}) - \hat{\Phi}(\hat{x}_n) || \end{eqnarray*}$

Jetzt Dreiecksungleichung anwenden! auf einen Teil kontraktionseigenschaft anwenden, auf den anderen die epsiolon-eigenschaft.

Das kannst du dann so iteratriv weitermachen (oder per induktion)

Zu b):
Kommst du nun weiter? Vielleicht kann man die geometrische Reihe da anwenden? Hab mir selbst noch keine gedanbken dazu gemacht

Neue Frage »

Antworten »

Abschätzung zu Fixpunktiterationen

Verwandte Themen