[WS] Fixpunktiterationen

Neue Frage »

17.08.2007, 12:58

tigerbine

Auf diesen Beitrag antworten »

[WS] Fixpunktiterationen

Gliederung

Fixpunktsatz von Banach

1a. Beweisstruktur

1b. Anziehender und Abstoßender Fixpunkt

1c. Konvergenzordnung von Fixpunktiterationen

1d. Lineare Konvergenzrate bei Fixpunktiterationen stetig differenzierbarer Funktionen
Fixpunktiterationen und Nullstellenprobleme
Beispiele

3a. Variante 1 - g(x)=x-f(x)

3b. Variante 2 - f nach x auflösen

3c. Variante 3 - Newton-Verfahren
Bezug zum Lösen von Linearen Gleichungssystemen

4a. Fixpunktiteration und die Splitting-Verfahren

4b. Konvergenz von Splitting Verfahren
Kettenbrüche

17.08.2007, 12:58

tigerbine

Auf diesen Beitrag antworten »

1. Fixpunktsatz von Banach
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*}$

17.08.2007, 12:58

tigerbine

Auf diesen Beitrag antworten »

1a. Beweisstruktur
Lehrer

Die genauen Schritte sind einem ausführlichen Beweis zu entnehmen. Dies dient lediglich als Gedankenstütze

$\begin{eqnarray*} \Phi \text{ ist Kontraktion }&& \Rightarrow \{x_k\}_k \text{ ist Cauchyfolge in } X \subseteq V \\&& \Rightarrow \text{Wegen Banachraum konvergiert die Folge gegen ein } x* \in V \\&& \Rightarrow \text{Da X abgeschlossen ist, liegt x* in X } \end{eqnarray*}$

$\begin{eqnarray*} \Phi \text{ ist Kontraktion }&& \Rightarrow \text{x* ist ein Fixpunkt von } \Phi \end{eqnarray*}$

$\begin{eqnarray*} \Phi \text{ ist Kontraktion }&& \Rightarrow \text{x* ist der eindeutige Fixpunkt von } \Phi \end{eqnarray*}$

19.08.2007, 13:53

tigerbine

Auf diesen Beitrag antworten »

1b. Anziehender und Abstoßender Fixpunkt
Definition

Sei x* ein Fixpunkt einer stetig differenzierbaren Funktion g.

Er heißt anziehend, wenn |g'(x*)|<1 ist, da es dann eine Umgebung um x* gibt, in der das Iterationsverfahren für jeden Startwert gegen x* konvergiert.
Er heißt abstoßend, wenn |g'(x*)| > 1 ist, da das Verfahren dort i.A. nicht gegen x* konvergiert.

Im Falle b reicht die Angabe zweier Beispiele. Im Falle a ist ein Beweis nötig.

Fall a:

Sei x* ein Fixpunkt einer stetig differenzierbaren Funktion g und es gelte |g(x*)|<1. D.h. es gilt:

$\begin{eqnarray*} \lim_{x\to x^*} ~|\frac{g(x)-g(x^*)}{x-x^*} |=|g'(x^*) | < 1 \end{eqnarray*}$
Da g' stetig ist, existiert eine Umgebung $\begin{eqnarray*} K_r(x^*) \end{eqnarray*}$ , so dass für alle x in dieser Umgebung gilt:

$\begin{eqnarray*} |g'(x)| < 1,~\forall ~ x \in K_r(x^*) \end{eqnarray*}$ (#)
Mit dem Mittelwertsatz der Differentialrechnung folgt durch einen Widerspruchsbeweis:

Angenommen, es gäbe in dieser Umgebung ein in $\begin{eqnarray*} x \in K_r(x^*) \end{eqnarray*}$ mit

$\begin{eqnarray*} |\frac{g(x)-g(x^*)}{x-x^*}| \geq 1 \end{eqnarray*}$

Dann gibt es ein $\begin{eqnarray*} \xi \in \hat K_r(x^*) \subseteq K_r(x^*) \end{eqnarray*}$ mit

$\begin{eqnarray*} |\frac{g(x)-g(x^*)}{x-x^*}| = |g'(\xi)| \geq 1 \end{eqnarray*}$

was im Widerspruch zu (#) steht.
Somit gilt:

$\begin{eqnarray*} |\frac{g(x)-g(x^*)}{x-x^*}| \leq c < 1,~\quad c \in (0,1), \forall x \in K_r(x^*) \end{eqnarray*}$

Damit folgt die (mindestens lineare) Konvergenz:

$\begin{eqnarray*} |g(x)-x^*| \leq c \cdot |x-x^*| \end{eqnarray*}$

Ein Beispielthread

19.08.2007, 14:16

tigerbine

Auf diesen Beitrag antworten »

1c. Konvergenzordnung von Fixpunktiterationen
In einem anderen Workshop wird der Begriff der Ordnung einer Iteration erklärt.

Sei g in einer Umgebung eines Fixpunktes x* p-mal stetig differenzierbar mit p > 1. Dann gilt:

$\begin{eqnarray*} g'(x^*) = ... = g^{(p-1)}(x^*)= 0,~g^{(p)}(x^*) \neq 0~ \Leftrightarrow \text{ Fixpunktiteration } x_{k+1} = g(x_k) \text{ hat die Ordnung p} \end{eqnarray*}$

Beweis:

$\begin{eqnarray*} \Rightarrow: \end{eqnarray*}$

Sei also $\begin{eqnarray*} g'(x^*) = ... = q^{(p-1)}(x^*)= 0,~g^{(p)}(x^*) \neq 0 \end{eqnarray*}$ . Dann gilt mit der Taylotentwicklung p-ter Ordnung um x*:

$\begin{eqnarray*} |x_{k+1}-x^*| &&= |g(x_k) - g(x^*)| = |g(x^*)+\sum_{i=1}^{p-1}~\frac{(x_k-x^*)^i}{i!}\cdot \underbrace{g^{(i)}(x^*)}_{=0}+\underbrace{ \frac{(x_k-x^*)^p}{p!} \cdot g^{(p)}(\xi_k)}_{\text{Restglied}} - g(x^*)| \\&& \leq \frac{1}{p!} \cdot \max |{g^{(p)}(x)}| \cdot |x_k-x^*|^p \end{eqnarray*}$

$\begin{eqnarray*} \Leftarrow: \end{eqnarray*}$

Sei also die Iteration von p-ter Ordnung, d.h. es gilt $\begin{eqnarray*} |x_{k+1}-x^*| \leq C \cdot |x_k-x^*|^p \end{eqnarray*}$ (1)

Annahme:

Es gibt ein $\begin{eqnarray*} m \leq p-1 \end{eqnarray*}$ mit $\begin{eqnarray*} g^{(m)} \neq 0 \end{eqnarray*}$ , aber $\begin{eqnarray*} g'(x) = ... = q^{(m-1)}(x*)= 0 \end{eqnarray*}$ . Dann konvergiert nach vorherigem Beweis ("=>") jede Folge von Iterierten $\begin{eqnarray*} \{x_k\} \end{eqnarray*}$ für $\begin{eqnarray*} x_0 \end{eqnarray*}$ nahe genug bei x* wie

$\begin{eqnarray*} |x_{k+1}-x^*| = |\frac{1}{m!}\cdot g^{(m)}(\xi_k)|\cdot |x_k-x^*|^m \end{eqnarray*}$ (2)

Nun gilt aber

$\begin{eqnarray*} \xi_k \in (x_k;x^*),~x_k \to x^* \end{eqnarray*}$

$\begin{eqnarray*} |g^{(m)}(x^*)| = \lim_{k \to \infty} |g^{(m)}(\xi_k)| \stackrel{(1),(2)} \leq m! \cdot C \cdot \underbrace{\lim_{k \to \infty} |x_k-x^*|^{p-m}}_{=0}=0 \end{eqnarray*}$

was im Widerspruch zu $\begin{eqnarray*} g^{(m)}(x^*) \neq 0 \end{eqnarray*}$ steht. Somit folgt die Behauptung.

19.08.2007, 23:31

tigerbine

Auf diesen Beitrag antworten »

1d. Lineare Konvergenzrate bei Fixpunktiterationen stetig differenzierbarer Funktionen
Lautet die Iterationsvorschrift einer konvergenten Fixpunktiteration

$\begin{eqnarray*} x_{k+1}:=g(x_k),~x^* = g(x^*) \end{eqnarray*}$

mit einer stetig differenzierbaren Funktion g, so folgt:

$\begin{eqnarray*} \begin{vmatrix} \frac{x_{k+1} -x^*}{x_k - x^*} \end{vmatrix} = \begin{vmatrix} \frac{g(x_k) -g(x^*)}{x_k - x^*} \end{vmatrix} \end{eqnarray*}$

In einer Grenzwertbetrachtung liefert dies:

$\begin{eqnarray*} \lim_{k \to \infty}~\begin{vmatrix} \frac{g(x_k) -g(x^*)}{x_k - x^*} \end{vmatrix} = |g'(x^*)| \end{eqnarray*}$

D.h. hier ist die lineare Konvergenzrate asymptotisch gleich g'(x*). Im Falle g'(x*)=0 liegt also (mindestens) superlineare Konvergenz der Fixpunktiteration vor.

20.08.2007, 00:13

tigerbine

Auf diesen Beitrag antworten »

2. Fixpunktiterationen und Nullstellenprobleme
Variante 1:

Betrachten wir die Funktionen f und g mit:

$\begin{eqnarray*} f(x):=x-g(x). \end{eqnarray*}$

Dann gilt:

$\begin{eqnarray*} \text{x* ist ein Fixpunkt der Funktion g } && \Leftrightarrow x^* = g(x^*) \\ && \Leftrightarrow f(x^*)=x^*-g(x^*) = 0 \\ \text{x* ist Nullstelle von f} && \Leftrightarrow \end{eqnarray*}$

Oder anderesherum definiert. Betrachtet man die Funktionen f und g mit:

$\begin{eqnarray*} g(x):=x-f(x) \end{eqnarray*}$

so folgt offensichtlich, dass die Nullstelle x* von f ein Fixpunkt der Funktion g ist.

Variante 2:

Soll die Nullstelle einer Funktion f bestimmt werden, so ist folgende Gleichung zu Lösen:

$\begin{eqnarray*} 0 = f(x) \end{eqnarray*}$

Durch umstellen nach x (vergleiche Beispiel 3) kann man dann eine Funktion g erhalten, deren Fixpunkt zu bestimmen ist.

Variante 3:

Bei der Nullstellenbestimmung mittels Newton-Verfahren betrachtet man folgende Rekursion:

$\begin{eqnarray*} x_{k+1} := x_{k} - \frac{f(x_k)}{f'(x_k)} \end{eqnarray*}$

Konvergiert das Verfahren, so gilt im Punkt x*, der gesuchten (hier einfachen) Nullstelle von f:

$\begin{eqnarray*} x^* - \frac{f(x^*)}{f'(x*)} = x^* - \frac{0}{f'(x^*)} = x^* \end{eqnarray*}$

D.h. x* ist Fixpunkt der wie folgt definierten Funktion g:

$\begin{eqnarray*} g(x):=x - \frac{f(x)}{f'(x)} \end{eqnarray*}$

27.08.2007, 02:50

tigerbine

Auf diesen Beitrag antworten »

3a. Beispiel Variante 1 - g(x):=x-f(x)
Gesucht sei nun die positive Nullstelle der folgenden Funktion f:

$\begin{eqnarray*} f:~\mathbb R \to \mathbb R,~f(x):=x + \ln(x) \end{eqnarray*}$

In (2) haben wir gesehen, dass sich dieses Problem äquivalent wie folgt formulieren lässt. Somit ist die gesuchte Nullstelle x* > 0 Fixpunkt der Funktion:

$\begin{eqnarray*} g(x):= x - f(x) = -\ln(x) \end{eqnarray*}$

Ist der Fixpunkt x* anziehend oder abstoßend?

D.h., auch wenn man x* nicht explizit kennt, so kann man zeigen, dass gilt:

$\begin{eqnarray*} |g'(x*)| > 1 \end{eqnarray*}$

Somit handelt es sich um einen abstoßenden Fixpunkt.

Ist die Nullstelle von f also nicht durch Iteration bestimmbar? (zur Antwort) (weiteres Beispiel)

27.08.2007, 12:06

tigerbine

Auf diesen Beitrag antworten »

3b. Beispiel Variante 2 - f nach x auflösen
Geht man die Checkliste für den Fixpunktsatz von Banach durch, so werden der Banachraum V und die Abbildung $\begin{eqnarray*} \Phi \end{eqnarray*}$ durch die Aufgabenstellung gegeben sein.

Ds Hauptproblem liegt darin, eine abgeschlossene Teilmenge X von V derart zu finden, dass $\begin{eqnarray*} \Phi \end{eqnarray*}$ dort tatsächlich eine kontrahierende Selbstabbildung ist.

Gesucht sei nun die postive Nullstelle der folgenden Funktion f:

$\begin{eqnarray*} f:~\mathbb R \to \mathbb R,~f(x):=e^x-3\cdot x^2 \end{eqnarray*}$

In (2) haben wir gesehen, dass dieses Problem äquivalent wie folgt formulieren lässt. Somit gilt für die gesuchte Nullstelle x* > 0

$\begin{eqnarray*} 0 = e^{x^{*}}-3\cdot (x^*)^2 && \Leftrightarrow 3(x^*)^2 = e^{x^*} \\&& \Leftrightarrow x^* = \frac{e^{x^*}}{3x^*} \end{eqnarray*}$

D.h. die Nullstelle von f ist Fixpunkt von:

$\begin{eqnarray*} g(x):=\frac{e^x}{3x} \end{eqnarray*}$

Was wir nun dem Plot entnehmen können, ist z.B. gilt:

$\begin{eqnarray*} f([0;2]) \subset [0,2] \end{eqnarray*}$

Jedoch verläuft der Graph nahe 0 sehr steil, so dass keine Kontraktion vorliegt. Betrachten wir hierzu die Ableitung von f:

$\begin{eqnarray*} f'(x) = \frac{x-1}{3x^2} \cdot e^x \end{eqnarray*}$

Im Intervall $\begin{eqnarray*} X:=[0.6,2] \end{eqnarray*}$ gilt nun:

$\begin{eqnarray*} f([0.6;2]) \subset [0.6;2] \end{eqnarray*}$ (Selbstabbildung)

Die Kontraktion kann man mit dem Mittelwertsatz der Differentialrechung bestätigen:

$\begin{eqnarray*} |f(x)-f(y)| \leq \max_{\xi \in X}~|f'(\xi)| \cdot |x-y| =:\kappa \cdot |x-y|,~\forall x,y \in X \end{eqnarray*}$

$\begin{eqnarray*} \kappa:=\max_{\xi \in X}~|f'(\xi)| = f'(0.6) \approx 0.67 < 1 \end{eqnarray*}$

Somit sind die Voraussetzungen des Fixpunktsatzes (1) erfüllt.

27.08.2007, 12:07

tigerbine

Auf diesen Beitrag antworten »

3c. Beispiel Variante 3 - Newton-Verfahren
Gesucht sei nun die positive Nullstelle der folgenden Funktion f:

$\begin{eqnarray*} f:~\mathbb R \to \mathbb R,~f(x):=x + \ln(x) \end{eqnarray*}$

In (2) haben wir gesehen, dass sich dieses Problem (im Falle einer Nullstelle einer stetig differenzierbaren Funktion), äquivalent wie folgt formulieren lässt. Somit ist die gesuchte Nullstelle x* > 0 Fixpunkt der Funktion:

$\begin{eqnarray*} g(x):= x - \frac{f(x)}{f'(x)} = x - \frac{x + \ln(x)}{1+\frac{1}{x}} \end{eqnarray*}$

Welche Art von Fixpunkt liegt nun hier vor?

$\begin{eqnarray*} g'(x) = \frac{f(x)f''(x)}{[f'(x)]^2} =\frac{\left(x+\ln(x)\right)\cdot\left(-\frac{1}{x^2}\right)}{\left[1+\frac{1}{x}\right]^2} \end{eqnarray*}$

Es gilt also

$\begin{eqnarray*} |g'(x^*)| < 1 \end{eqnarray*}$

und der Fixpunkt ist anziehend. Nicht wirklich verwunderlich, da die Fixpunktiteration hier dem Newton-Verfahren für eine einfache Nullstelle einer C²-Funktion entspricht. Von dem man weiß, dass es eine Umgebung um x* gibt, so dass das Verfahren mindestens quadratisch konvergiert. (Zum allgemeinen Beweis)

Wir können das aber auch in der Fixpunktgestalt überprüfen. Schreiben wir es einmal allgemein auf, für eine einfache Nullstelle einer C² Funktion:

$\begin{eqnarray*} g(x)=x-\frac{f(x)}{f'(x)} \end{eqnarray*}$

$\begin{eqnarray*} g'(x)=1-\frac{f'(x)^2-f(x)f''(x)}{f'(x)^2}=\frac{f(x)f''(x)}{f'(x)^2} = 0 \end{eqnarray*}$

Im Allgemeinen wird die zweite Ableitung von Null verschieden sein. Somit ist p=2 und wir erhalten wie gewünscht die Konvergenz der Ordnung 2.

29.08.2007, 00:37

tigerbine

Auf diesen Beitrag antworten »

4a. Fixpunktiteration und die Splitting-Verfahren
Im [Workshop - Lineare Gleichungssysteme 3] wird sich mit Iterativen Verfahren zur Lösung von regulären Linearen Gleichungssystemen beschäftigt.

$\begin{eqnarray*} Ax=b,~A \in \text{GL}(n) \end{eqnarray*}$

Dabei wurden iterative Verfahren der folgenden allgemeinen Gestalt betrachtet (Index hier im Exponent, um Verwechslung mit Vektorkomponente zu vermeiden):

$\begin{eqnarray*} x^{k+1}:=\Phi(x^k),~k=0,1,2,...\quad (*) \end{eqnarray*}$

Das Verfahren soll ja nun möglichst gegen die eindeutige Lösung x* des LGS konvergieren, somit ist (*) wieder eine Form der Fixpunktiteration. Betrachten wir nun einmal das Präkonditionieren /Splitten aus obigen Workshop,

Zitat:

[Workshop - Lineare Gleichungssysteme 3]

$\begin{eqnarray*} Ax&& = b \\ Px + Ax - Px &&= b \\ Px + (A-P)x &&= b \\ x &&=P^{-1}(P-A)x + P^{-1}b \\ x&&=(I-P^{-1}A)x + P^{-1}b \end{eqnarray*}$

so können wir aus der letzen Zeile wie folgt eine Fixpunktiteration erhalten

$\begin{eqnarray*} x^{k+1}:=(I-P^{-1}A)x^k + P^{-1}b \end{eqnarray*}$

$\begin{eqnarray*} x^{k+1}:=Mx^{k} + c \quad \text{mit } M:=(I-P^{-1}A),~c:=P^{-1}b \end{eqnarray*}$

Die Matrix M wird dabei als Iterationsmatrix des sogenannten Splitting Verfahrens genannt.

29.08.2007, 00:50

tigerbine

Auf diesen Beitrag antworten »

4b. Konvergenz von Splitting Verfahren
Wann konvergiert ein Splitting-Verfahren nun?

Die durch obige Definition erhaltene Folge $\begin{eqnarray*} \{x^k\} \end{eqnarray*}$ konvergiert für jeden Startwert $\begin{eqnarray*} x^0 \in \mathbb R^n \end{eqnarray*}$ gegen die Lösung x* des LGS Ax=b., sofern es eine induzierte Matrixnorm ||.|| gibt, für die $\begin{eqnarray*} \|M\|< 1 \end{eqnarray*}$ gilt.

Beweis:

Aus der Definition der Folge ergibt sich unmittelbar:

$\begin{eqnarray*} ||x^{k+1}-x^*|| &&= ||(Mx^k+c)-(Mx^*+c)|| \\ && = ||M(x^k-x^*)|| \\ && \leq ||M|| \cdot ||x^k-x^*|| \end{eqnarray*}$

Nun arbeiten wir noch ein bisschen an der Optik und setzen:

$\begin{eqnarray*} \kappa:=||M|| \end{eqnarray*}$
$\begin{eqnarray*} \Phi (x):= Mx+c \end{eqnarray*}$
$\begin{eqnarray*} X:= \mathbb R^{n} \end{eqnarray*}$

Somit steht nun da:

$\begin{eqnarray*} ||x^{k+1}-x^*|| \leq \kappa \cdot ||x^{k}-x^*||,~\kappa(0,1) \end{eqnarray*}$

Und die Behauptung folgt aus dem Fixpunktsatz von Banach. $\begin{eqnarray*} \Box \end{eqnarray*}$

11.12.2008, 18:11

tigerbine

Auf diesen Beitrag antworten »

5. Kettenwurzeln und Kettenbrüche
Zum Abschluss wollen wir uns noch die Frage stellen, wie man denn die folgende Kettenwurzel berechnen könnte.

$\begin{eqnarray*} b:=\underbrace{\sqrt{2+\sqrt{2+\sqrt{2+...\sqrt{2}}}}}_{\text{n Wurzeln}} \end{eqnarray*}$

Dazu verwandeln wir die Kettenwurzel in eine rekursive Folge:

$\begin{eqnarray*} x_{n+1}:=\Phi(x_n) \end{eqnarray*}$

$\begin{eqnarray*} x_0:=\sqrt{2} \end{eqnarray*}$

$\begin{eqnarray*} x_{n+1}:=\sqrt{2+x_n} \end{eqnarray*}$

Dann überprüfen wir die Voraussetzungen für den Fixpunktsatz von Banach.

Die Funktion ist auf dem reellen abgeschlossenen Intervall [0,5] eine Selbstabbildung. Die Ableitung der Funktion lautet:

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

Somit handelt es sich auch um eine Kontraktion. Etwas besser abgeschätzt erhalten wir:

$\begin{eqnarray*} 0<\Phi'(x)=0.5\cdot \frac{1}{\sqrt{2+x}} < \Phi'(0) \approx 0.36 = \kappa \end{eqnarray*}$

Der Plot verrät uns schon die Lösung. Rechnen wir sie aber dennoch nach.

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:
25:
26:
27:

Fixpunkt Berechnung mit Banach
 
Intervallgrenzen [a,b] eingeben: [0,5]
 
Startwert eingeben.                  x0 = sqrt(2)
Genauigkeit eingeben.               eps = 10^(-8)
Kontraktionskonstante eingebeben. kappa = 0.36
N =
    18
 
Index    Funktionswert    a-posteriori
=======================================
  1        1.414214       100.000000 
  2        1.847759       0.243869 
  3        1.961571       0.064019 
  4        1.990369       0.016199 
  5        1.997591       0.004062 
  6        1.999398       0.001016 
  7        1.999849       0.000254 
  8        1.999962       0.000064 
  9        1.999991       0.000016 
  10        1.999998       0.000004 
  11        1.999999       0.000001 
  12        2.000000       0.000000 
  13        2.000000       0.000000 
  14        2.000000       0.000000 
  15        2.000000       0.000000

Lassen sich auf ähnliche Weise auch Kettenbrüche berechnen?

$\begin{eqnarray*} b:=\frac{1}{1+\frac{1}{1+\frac{1}{1+...}}} \end{eqnarray*}$

Dazu verwandeln wir die Kettenwurzel in eine rekursive Folge:

$\begin{eqnarray*} x_{n+1}:=\Phi(x_n) \end{eqnarray*}$

$\begin{eqnarray*} x_0:=1 \end{eqnarray*}$

$\begin{eqnarray*} x_{n+1}:=\frac{1}{1+x} \end{eqnarray*}$

$\begin{eqnarray*} 0 < |\Phi'(x)|=|-\frac{1}{(1+x)^2}| \leq 1 \end{eqnarray*}$

$\begin{eqnarray*} |\phi(0.5)| =0.45 \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:
25:
26:
27:
28:
29:
30:
31:
32:

Fixpunkt Berechnung mit Banach
 
Intervallgrenzen [a,b] eingeben: [0.5,1]
 
Startwert eingeben.                  x0 = 0.5
Genauigkeit eingeben.               eps = 10^(-8)
Kontraktionskonstante eingebeben. kappa = 0.45
N =
    22
 
Index    Funktionswert    a-posteriori
=======================================
  1        0.500000       100.000000 
  2        0.666667       0.136364 
  3        0.600000       0.054545 
  4        0.625000       0.020455 
  5        0.615385       0.007867 
  6        0.619048       0.002997 
  7        0.617647       0.001146 
  8        0.618182       0.000438 
  9        0.617978       0.000167 
  10        0.618056       0.000064 
  11        0.618026       0.000024 
  12        0.618037       0.000009 
  13        0.618033       0.000004 
  14        0.618034       0.000001 
  15        0.618034       0.000001 
  16        0.618034       0.000000 
  17        0.618034       0.000000 
  18        0.618034       0.000000 
  19        0.618034       0.000000 
  20        0.618034       0.000000

Neue Frage »

Antworten »

[WS] Fixpunktiterationen

Verwandte Themen