Wie viele Iterationen benötigt man, damit der Fehler auf jeden Fall kleiner ist als \varepsilon:=0.001?

Question

Aufgabe:

Betrachte das Iterationsverfahren
$x_{k+1}=\phi\left(x_{k}\right),$
mit der Abbildung $\phi: \mathbb{R}^{n} \rightarrow \mathbb{R}^{n}$
$\phi(x)=C x+d$
und einem Startwert $x_{0} \in \mathbb{R}^{n}$, wobei $d \in \mathbb{R}^{n}$ und $C \in \mathbb{R}^{n \times n}$ mit $L:=\|C\|<1$.

a) Zeigen Sie für $k \in \mathbb{N}_{0}$
$\left\|x_{k+1}-x_{k}\right\| \leq L^{k}\left\|x_{1}-x_{0}\right\|,$
für verträgliche Matrix- und Vektornormen.

b) Sei $x^{*}:=\lim \limits_{k \rightarrow \infty} x_{k} .$ Begründen Sie, warum der Grenzwert $x^{*}$ existiert und zeigen Sie weiter
$\left|x_{k}-x^{*}\right| \leq \frac{L^{k}}{1-L}\left\|x_{1}-x_{0}\right\| .$

c) Sei
$C=\left(\begin{array}{cc} \frac{1}{4} & \frac{1}{5} \\ \frac{1}{5} & \frac{3}{4} \end{array}\right), \quad d=\left(\begin{array}{l} 1 \\ 1 \end{array}\right) \quad \text { und } \quad x_{0}=\left(\begin{array}{l} 1 \\ 2 \end{array}\right)$
Wie viele Iterationen benötigt man, damit der Fehler auf jeden Fall kleiner ist als $\varepsilon:=0.001$, also damit gilt
$\left\|x_{k}-x^{*}\right\|_{2}<\varepsilon ?$

Problem/Ansatz:

a.) und b.) habe ich bereits gemacht und kann man leicht mit dem Banachscher Fixpunktsatz zeigen/beweisen.

Aber wie funktioniert c.)? Wie kann man davon die Anzahl der benötigten Iterationen bestimmen?

Hier ist ein altes Skript, wo man den Banachschen Fixpunktsatz, sowie eine Idee zu c.) nachlesen kann:

https://www.uni-ulm.de/fileadmin/website_uni_ulm/mawi.inst.070/ss17/…

Satz 5.6.1 (Banach’scher Fixpunktsatz) ist auf Seite 83 und die Bemerkung 5.6.2 b.) kann wahrscheinlich weiterhelfen, wie das Beispiel 5.6.5 .

Leider weiß ich noch nicht, wie ich das umsetzen soll :/

Comments

Für den Anfang bräuchte ich erstmal das entsprechende System, aber wie setzt man das richtig in die Abbildung $\phi: \mathbb{R}^{n} \rightarrow \mathbb{R}^{n}$$\phi(x)=C x+d$ ein?

Answer 1

Hallo

x0 ist gegeben das mit dem gegebenen C multiplizieren und d addieren gibt x1

danach hast du die Abschätzung aus b) um den Fehler kleiner 0,001 zu machen. k ist dann die Anzahl der Interaktionen die du aus L^k hast.

Gruß lul

Comments

Also ich habs mal versucht durchzurechnen und kommen so bei 43 Schritten raus. Ist das realistisch?

Hier sind ein paar Zwischenlösungen:

x1 = (33/20 , 27/20)

||x1-x0||_2 = $\sqrt{365}$ /20

L:=||D||_2 = $\sqrt{\lambda_{max}(D^tD)}$ = 0.82