4.4. Fixpunktiterationen ohne Ableitungen

Im Folgenden diskutieren wir alternative Fixpunktiterationsverfahren, die keine Ableitungen verwenden. Gründe für den Einsatz solcher Verfahren können sein, dass entweder \(F\) nicht differenzierbar ist, oder häufiger noch, weil die Ableitung von \(F\) nicht einfach berechnet werden kann, z.B. weil die Funktion \(F\) selbst nur durch ein numerisches Verfahren ausgewertet werden kann. Das klassische Beispiel von Fixpunktiterationen ohne Ableitungen sind Intervallschachtelungsverfahren im Eindimensionalen, im einfachsten Fall mittels Bisektion.

Beispiel 4.3 (Bisektionsverfahren)

Sei \(f: \R \rightarrow \R\) stetig und \(a < b\) so, dass \(F(a)F(b) < 0\). Dann wissen wir aus dem Zwischenwertsatz, dass eine Nullstelle der Funktion im Intervall \((a,b)\) liegt. Wir berechnen also \(F(\frac{a+b}2)\) und vergleichen das Vorzeichen mit dem von \(F(a)\) und \(F(b)\). Ist das Vorzeichen gleich dem von \(F(a)\), so liegt die Nullstelle im Intervall \((\frac{a+b}2,b)\), andernfalls im Intervall \((a,\frac{a+b}2).\) Nun können wir iterativ die Intervalle weiter verfeinern.

Mathematisch sauberer definieren wir eine Iterierte \(x_k \in \R^2\) mit \(x_0 = (a,b)\) und

\[x_{k+1} = \left\{ \begin{array}{ll} \left(x_k^1,\frac{x_k^1+x_k^2}2 \right) & \text{falls } f(x_k^1) \cdot f(\frac{x_k^1+x_k^2}2) \, < \, 0, \\ \left(\frac{x_k^1+x_k^2}2,x_k^2 \right) & \text{falls } f(x_k^2) \cdot f(\frac{x_k^1+x_k^2}2) \, < \, 0, \\ \left[ \frac{x_k^1+x_k^2}2,\frac{x_k^1+x_k^2}2 \right] & \text{falls } f(\frac{x_k^1+x_k^2}2) \, = \, 0. \end{array} \right.\]

In diesem Fall haben wir offensichtlich eine Fixpunktiteration und daher können wir das Verfahren bezüglich Kontraktivität untersuchen. Man kann zeigen, dass die Kontraktionskonstante \(q=\frac{1}2\) ist. Wir können die Konvergenz des Bisektionsverfahrens oben aber auch direkt analysieren. Es gilt offensichtlich:

\[\Vert x_k - \overline{x} \Vert_1 \ = \ \vert x_k^1 - x_k^2 \vert \ \leq \ \frac{1}2 \vert x_{k-1}^1 - x_{k-1}^2 \vert \ \leq \ \ldots \ \leq \ \frac{1}{2^k} \vert x_{0}^1 - x_{0}^2 \vert \ = \ \frac{\vert a - b \vert}{2^k}.\]

Als zweites Beispiel diskutieren wir ein klassisches Verfahren zur Approximation des Newton-Verfahrens ohne Ableitungen zu verwenden. Die Idee hierbei ist es die Tangente im Newton-Verfahren durch die Sekante zwischen den letzten beiden Iterierten zu ersetzen. Daraus lässt sich also das folgende Sekantenverfahren herleiten.

Beispiel 4.4 (Sekantenverfahren)

Sei \(F: \R \rightarrow \R\) eine Funktion deren Nullstelle wir bestimmen wollen. Es seien bereits mindestens zwei Iterierte \(x_k\) und \(x_{k-1}\) gegeben. Falls \(F(x_k) \neq F(x_{k-1})\) gilt, berechnen wir

\[x_{k+1} \ = \ x_k - \frac{x_k - x_{k-1}}{F(x_k) - F(x_{k-1})}F(x_k).\]

Durch Taylor-Entwicklung erhalten wir, dass das Sekantenverfahren eine superlineare Konvergenz aufweist, wenn \(F\) hinreichend glatt ist und \(F'(\overline{x}) \neq 0\) gilt (in diesem Fall ist in einer Umgebung auch \(F(x) \neq F(y)\) für \(x \neq y\)).

Bemerkung 4.6

Das Sekantenverfahren lässt sich nicht direkt auf den mehrdimensionalen Fall erweitern. Eine einfachere Variante ist eine Differenzenapproximation der Ableitung mit fixer (kleiner) Schrittweite \(\delta\), d.h. also wir berechnen statt dessen im Eindimensionalen:

\[x_{k+1} \ = \ x_k - \frac{\delta}{F(x_k+\delta) - F(x_{k})}F(x_k) .\]

Für eine mehrdimensionale Funktion \(F: \R^n \rightarrow \R^n\) können wir analog die Jacobi Matrix mittels

\[(F'(x))_{ij} \ \approx \ \frac{F_i(x+\delta e_j) - F_i(x) }\delta, \quad \forall \ 1 \leq i,j \leq n\]

approximieren, wobei \(e_j\) den \(j\)-ten Einheitsvektor im \(\R^n\) bezeichnet.