Iteration reellwertiger Funktionen

Wir betrachten eine reellwertige Funktion

f:\mathbb{R}\longrightarrow\mathbb{R},

beispielsweise eine Proportionalität

f(x) = \lambda x,

und wählen einen Startwert $x_0$ . Nun erzeugen wir rekursiv eine Folge mit

\begin{align*} f^1(x_0) &= f(x_0) &= x_1\\ f^2(x_0) &= f(x_1) &= x_2\\ f^3(x_0) &= f(x_2) &= x_3\\ &\vdots &\vdots \phantom{x_k} \\ f^k(x_0) &= f(x_{k-1}) &= x_k \end{align*}

Diesen Vorgang nennen wir Iteration von $f$ mit Startwert $x_0$ . Iterieren einer Funktion heisst also:

Zu einem gegebenen Startwert $x_0$ den Funktionswert $x_1=f(x_0)$ berechnen.
den Wert $x_1$ als neuen Startwert nehmen und bei 1. fortfahren.

Definition 1: Orbit

Die Menge

\{x_0,x_1,x_2,\dots\}

wird als Orbit oder Bahn von $x_0$ bezeichnet.

Example 1

Wir betrachten einige Beispiele.

f(x)=\frac{x}{2},\quad x_0=3\dots

Die Folge ist konvergent gegen $0$ . *

f(x)=3x,\quad x_0=1\dots

Die Folge divergiert. *

f(x)=x,\quad x_0\dots

Hier haben wir lauter Fixpunkte. *

f(x)=x+c,\quad x_0\dots

Wir haben $f^n(x)=x_0+n\cdot c$ , was im Allgemeinen divergiert. *

f(x)=x^2

Dieses Beispiel ist interessant, da das Verhalten wesentlich vom gewählten Startwert $x_0$ abhängt. - Ist $-1<x_0<1$ , dann erhalten wir bei Iteration eine monoton fallende Zahlenfolge mit

\lim_{n\to\infty}x_n=0.

Ferner fällt auf, dass ein negativer Startwert nach der ersten Iteration "ins Positive hüpft". - Gilt $|x_0|>1$ , so divergiert die entsprechende Folge.

Exercise 1: Iteriere x^2

Betrachte für

f(x)=x^2

die beiden Fälle $x_0=0$ und $x_0=1$ . In welchen Zusammenhang könnten die Begriffe Repeller und Attraktor hier gebracht werden?

Solution

Für $k\in\mathbb{N}$ ist $f^{k}(0)=0$ und $f^{k}(1)=1$ , die beiden Werte sind also Fixpunkte von $f$ .

Exercise 2: Fixpunkte

Finde Fixpunkte der Iteration

f(x)=x^2-2

und entscheide anschliessend, ob es sich um anziehende oder abstossende Fixpunkte handelt.

Solution

Mit der Fixpunktbedingung ergibt sich

\begin{align*} x^2-2 &= x\\ x^2-x-2 &= 0\\ x_{1,2} &= \frac{1\pm3}{2} \end{align*}

also sind die Fixpunkte $2$ und $-1$ . Ferner ist ein Fixpunkt $x_p$ anziehend, falls $|f'(x_p)|<1$ . Hier ist $f'(x)=2x$ und damit ist keiner der beiden anziehend.

Example 2

Möchte man die Fixpunkte der Iteration

f(x)=x^2

finden, so löst man einfach die entsprechende Bedingung,

f(x)=x,

nach $x$ . In der Tat hier also $x^2-x=0$ , woraus unmittelbar die Lösungen $x_1=0$ und $x_2=1$ abgelesen werden können.

Anziehend oder abstossend?

Exercise 3

Wie könnte man nun entscheiden, ob ein Fixpunkt anziehend oder abstossend ist?

Solution

Die Attraktorbedingung für einen Fixpunkt $x^*$ einer Funktion $f$ ist $|f'(x^*)|<1$ .

Proof

Beweis: 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.