Fixpunkte

Evergreens bei der Analyse von Abbildungen sind die Suche nach Fixpunkten oder Fixgeraden.

Definition 1: Fixpunkt

Ein Punkt $x^*$ heisst Fixpunkt (der Periode $1$ ) von $f$ , wenn $f(x^*) = x^*$ gilt.

Note 1

Ist $x^*$ ein Fixpunkt der Periode $1$ von $f$ , dann gilt natürlich auch $f^n(x^*) = x^*$ für jedes $n\in\mathbb{N}$ . Ferner: Seien $n\in\mathbb{N}$ und $x^*$ ein Fixpunkt der Periode $k\in\mathbb{N}$ mit $n\mod{k}\equiv0$ , dann ist $x^*$ auch ein Fixpunkt der Periode $n$ .

Example 1

$f(x) = \sqrt{x}$ hat die Fixpunkte $0$ und $1$ .
$g(x) = 2x+1$ hat den Fixpunkt $x = -1$ .
$h(x) = x-2$ hat keinen Fixpunkt.

Definition 2: Fixpunkt-Ordnung

Ein Punkt $x^*$ heisst Fixpunkt der Ordnung $k$ von $f$ , wenn

f^k(x^*) = x^*

gilt.

Example 2

Wir betrachten

f(x) = -x+1.

Dann können wir leicht nachrechnen, dass $x = 0.25$ ein Fixpunkt der Periode $2$ von $f$ ist.

Exercise 1: Fixpunkte

Gibt es noch weitere Fixpunkte?

Solution

Der Fixpunkt der Periode 1 ist $\frac{1}{2}$ . Für einen Fixpunkt der Periode 2 gilt: $-(-x+1)+1\stackrel{!}{ = }x$ , also $x = x$ . Das heisst, es gibt unendlich viele Fixpunkte der Periode 2 für $f$ ; jedes $x\in\mathbb{R}$ .

Bleibt noch die Frage, wie man Fixpunkte höherer Ordnung findet? Dazu illustrativ ein

Example 3

Wir betrachten

f(x) = 2x-1.

Einen Fixpunkt der Periode $1$ finden wir rasch via die Bedingung $f(x) = x$ , also

2x-1 = x

was unmittelbar $x = 1$ liefert.

Um nun Fixpunkte der Periode $2$ zu finden berechnen wir

f^2(x) = 2(2x-1)-1 = 4x-3

und erhalten

4x-3 = x.

Wir sind enttäuscht, weil $x = 1$ bereits wieder Lösung ist. Scheinbar gibt es hier keine reinen Fixpunkte der Periode $2$ . "Keine reinen" deshalb, weil ja ein Fixpunkt erster Periode ebenfalls Fixpunkt $n$ -ter Periode ist.

Wir vermuten anhand der obigen Rechnung, dass eine affine Funktion keine echten Fixpunkte höherer Periode hat.

Exercise 2: Fixpunkte linearer Funktion

Beweise obige Vermutung.

Solution

Wir rechnen alle Fixpunkte nach.

\begin{align*} mx+q &\stackrel{!}{ = } x\\ x(m-1) & = -q\\ x & = \frac{q}{1-m} \end{align*}

falls $m\neq1$ ; für $m = 1$ ist $q = 0$ und man hat mit $f(x) = x$ eine Fixpunktgerade. Für 2-Zyklen ist

\begin{align*} m(mx+q)+q &\stackrel{!}{ = } x\\ x(1-m^2) & = q(m+1)\\ x & = \frac{q(m+1)}{1-m^2}\\ x & = \frac{q}{1-m} \end{align*}

wobei $m\neq\pm1$ galt. Dies ist der Fixpunkt der Periode 1 und wir betrachten daher den Fall $m = -1$ separat. Daraus folgt unter der Fixpunktbedingung sofort $x = x$ , so dass jeder Punkt $x$ für $f(x) = -x+q$ ein 2-Zyklus ist.

Für 3-Zyklen:

\begin{align*} m(m(mx+q)+q)+q &\stackrel{!}{ = } x\\ m(m^2x+mq+q)+q & = x\\ q(m^2+m+1) & = x(1-m^3)\\ x & = q\frac{m^2+m+1}{1-m^3} \end{align*}

Berechne $(m^3-1)\div(m^2+m+1)$ mit Polynomdivision und sieh dann, dass $x = q\frac{m^2+m+1}{1-m^3} = \frac{q}{1-m}$ . Das heisst, es gibt keine weiteren Fixpunkte.

Die Vermutung war also nicht ganz korrekt: Fixpunkte der Periode $2$ liegen auf den Senkrechten zur Winkelhalbierenden.

Definition 3: Attraktor

Ein Fixpunkt $x$ heisst anziehend oder stabil, wenn für alle Punkte $\tilde{x}$ in einer Umgebung von $x$ gilt, dass

\lim_{n\to\infty}f^n(y) = x.

Man nennt $x$ auch etwa Attraktor.

Example 4

Beispielsweise ist für

f(x) = \sqrt{x}

der Punkt $x = 1$ ein Attraktor.

Exercise 3: Attraktor?

Starte mit den Werten $3$ und $0.2$ und betrachte deren Verhalten unter

\lim_{n\to\infty}\sqrt[n]{x}.

Wie könnte man allgemein zeigen, dass $1$ ein Attraktor für $\sqrt{x}$ ist?

Solution

Man wählt eine kleine Umgebung von $1$ , $\pm\varepsilon$ , und beobachtet das Geschehen. Einmal iteriert ist $f(1+\varepsilon) = \sqrt{1-\varepsilon}$ und $k$ Mal iteriert ergibt $\sqrt[2k]{1+\varepsilon} = (1+\varepsilon)^{\frac{1}{2k}}$ , was für $k\to\infty$ gegen den Grenzwert $(1+\varepsilon)^{0} = 1$ konvergiert. (Limit kommentiert)

Definition 4: Repeller

Ein Fixpunkt $x$ heisst abstossend oder instabil, wenn für alle Punkte $\tilde{x}\neq x$ in einer Umgebung von $x$ gilt, dass

\lim_{n\to\infty}f^n(y)\neq x.

Man nennt $x$ auch Repeller.

Example 5

Für $f(x) = x^2$ ist der Fixpunkt $x = 1$ abstossend.

Für einige ausgewählte Übungen sind weiter unten vorgezeichnete Graphen auf dem Silbertablett serviert.

Exercise 4: Repeller?

Betrachte die Startwerte $x = 2$ bzw. $x = 0.5$ und zeige allgemein, dass $1$ ein Repellor für $x^2$ ist.

Solution

Orbits: $\{2,4,16,256,\dots\}$ und $\{0.5,0.25.0.125,\dots\}$ . Nun betrachten wir einen Punkt in der Nähe von $1$ wobei $\varepsilon>0$ , $1+\varepsilon$ . $f(1+\varepsilon) = (1+\varepsilon)^2 = 1+2\varepsilon+\varepsilon^2$ . Dieser Wert wird pro Iteration zunehmen, also ist $1$ abstossend nach oben. Allerdings ist $f(1-\varepsilon) = (1-\varepsilon)^2 = 1-2\varepsilon+\varepsilon^2$ , das gegen $0$ tendiert.

Theorem 1: Attraktor-Bedingung

Gilt für einen Fixpunkt $x$ , dass $|f'(x)>1|$ , dann ist $x$ ein Repellor. Ist $|f'(x)|<1$ , so handelt es sich um einen Attraktor.

Proof

Übung, falls man zum Beispiel Lipschitz-Stetigkeit und den Mittelwertsatz googlen möchte.

Sei $f$ Lipschitz-stetig. Der Abstand zwischen $x_{n+1}$ und $x^*$ ist $|x_{n+1}-x^*| = |f(x_n)-f(x^*)|\leq L|x_n-x^*|$ . Nach Iteration hat man $|f(f(x_n))-x^*|\leq L|f(x_{n+1})-x^*|\leq L^2|x_n-x^*|$ . Also ist $|x_k-x^*|\leq L^k|x_0-x^*|$ . Ist $|L|<1$ dann gilt $L^k\to0$ für $k\to\infty$ . Ist $f$ nicht Lipschitz-stetig, so kann man den Mittelwertsatz anwenden, wenn $f$ differenzierbar und stetig ist. Es ist $x_{k+1}-x^* = f(x_k)-f(x^*) = f'(\zeta)\cdot(x_k-x^*)$ mit $\zeta\in(x_k,x^*)$ . Also betragsmässig $|f(x_k)-x^*| = |f'(\zeta)|\cdot|x_k-x^*|$ , was für $|f'(\zeta)|<1$ den Abstand pro Iterationsschritt verkürzt.

Exercise 5: Repeller, Attraktor, ...

Gib jeweils ein Beispiel einer Funktion mit

a) einem Attraktor bei $x = 3$ .

b) einem Repellor bei $x = -2$ .

c) zwei Fixpunkten, bei $x = 1$ bzw. $x = 4$ .

d) einem Fixpunkt der Periode $2$ in $x = 7$ , für den $f(7) = 19$ ist.

Solution

a) Ich nehme eine Funktion mit Ableitung an der Stelle $3$ betragsmässig kleiner $1$ . Zum Beispiel $f(x) = \frac{2}{3}x+1$ , denn $f'(x) = \frac{2}{3}$ . $f(3) = 3$ ist Fixpunkt und $|f'(3)| = \frac{2}{3}$ .

b) Wiederum bietet sich eine lineare Funktion mit Steigung grösser $1$ an: $g(x) = 2x+2$ erfüllt die Anforderungen.

c) Die beiden Werte sind Lösung der quadratischen Gleichung $0 = (x-1)(x-4) = x^2-5x+4$ die wir als Fixpunktbedingung umformulieren: $x^2-4x+4 = x$ . Also erfüllt $h(x) = (x-2)^2$ die Bedingung.

d) Aufgrund der vorhergehenden Ausführungen wissen wir, dass für jede lineare Funktion mit Steigung $-1$ jedes $x\in\mathbb{R}$ ein $2$ -Zyklus ist. Für $k(x) = -x+26$ ist auch $k(7) = 19$ erfüllt.

Exercise 6: Einzugsgebiet

Welche Aussagen kannst du über die Fixpunkte folgender Funktionen machen? Bestimme gegebenenfalls das "Einzugsgebiet", falls es sich um einen Attraktor handelt.

a) $\cos(x)$

b) $2\sin(x)$

c) $0.5x^2+0.5$

Solution

a) $\cos(x) = x$ ist analytisch nicht lösbar. Man kann beispielsweise gucken, wo die Graphen sich schneiden und Werte approximieren. Eine approximative Lösung mit einem Taylorpolynom wäre auch denkbar.

b) Dasselbe gilt wie in a) gilt hier auch.

\begin{align*} 0.5x^2+0.5 &\stackrel{!}{ = } x\\ x^2-2x+1 & = 0\\ (x-1)^2 & = 0\\ x & = 1 \end{align*}

Die Bedingung liefert $|x| = 1$ und damit ist $1$ sicher kein Attraktor.

Exercise 7: Fixpunkte?

Untersuche die Funktion

f(x) = -x^2+1

auf Fixpunkte.

Solution

Aus der Fixpunktbedingung $-x^2+1\stackrel{!}{ = }x$ folgt $0 = x^2+x-1$ deren Lösung die goldenen Schnitte $\varphi$ und $-\Phi$ sind. Wegen $f'(\varphi) = 2\varphi+1>1$ ist $\varphi$ instabil und aus $f'(-\Phi) = -2\Phi+1<-1$ erkennen wir, dass $-\Phi$ auch Repeller ist.

Die Fixpunkte der Periode $2$ geben etwas mehr zu tun.

f(f(x)) = -(-x^2+1)^2+1 = -x^4+2x^2\stackrel{!}{ = }x.

Darin stecken natürlich auch die Fixpunkte der Periode $1$ (gegeben durch $x^2+x-1 = 0$ ), die wir mit Hilfe einer Polynomdivision eliminieren, um die Polynomgleichung zu erhalten, welche die reinen Fixpunkte der Periode 2 liefert.

(-x^4+2x^2-x)\div(x^2+x-1) = x^2+x

und damit $x_3 = 0$ und $x_4 = 1$ . Es ist $(f(f(0)))' = -4\cdot0^3+4\cdot0 = 0$ und $(f(f(1)))' = 0$ , also sind beide Attraktoren.

Exercise 8: Standard-Parabel

Untersuche die Standard-Parabel

f(x) = x^2

auf Fixpunkte.

Solution

Aus der Fixpunktbedingung folgt unmittelbar $x^2-x\stackrel{!}{ = }0$ und damit $x_1 = 0, x_2 = 1$ . $0$ ist Attraktor, $1$ Repeller.

Für die Periode 2 Fixpunkte betrachten wir $x^4-x\stackrel{!}{ = }0$ , also $x^3 = 1$ und haben immer noch die beiden gleichen Fixpunkte.

Example 6

Wie sieht es nun für eine verschobene Parabel

f(x) = x^2-2

aus? Wir haben

x^2-x-2 = 0

mit den Lösungen $x_1 = -1$ und $x_2 = 2$ .

Für Fixpunkte der Periode zwei muss

x^4-4x^2-x+2 = 0

gelten. Um nun die echten $2$ -periodischen Fixpunkte zu erhalten, dividieren wir die Fixpunkte der Periode $1$ aus:

(x^4-4x^2-x+2)\div(x^2-x-2) = x^2+x-1

und setzen gleich $0$ . Die Lösung dieser schönen Gleichung kennen wir. Die Fixpunkte $2$ -ter Periode sind also

x = \frac{-1\pm\sqrt{5}}{2}.

(Parabel kommentiert)