2.1 Bisektionsalgorithmus
Der Bisektionsalgorithmus ist eine einfache Methode, um die Wurzeln von eindimensionalen Funktionen zu finden. Das Ziel ist es, eine Wurzel \(x_0\in\) zu finden, so dass \(f(x_0)=0\). Der Algorithmus beginnt mit einem großen Intervall, von dem bekannt ist, dass es \(x_0\) enthält, und verkleinert dann sukzessive die Größe des Intervalls, bis es die Wurzel einklammert. Die theoretische Grundlage des Algorithmus ist der Zwischenwertsatz, der besagt, dass, wenn eine stetige Funktion \(f\) die Werte \(f(a)\) und \(f(b)\) an den Endpunkten des Intervalls \(\) annimmt, \(f\) dann alle Werte zwischen \(f(a)\) und \(f(b)\) irgendwo im Intervall annehmen muss. Wenn also \(f(a) < \gamma < f(b)\), dann gibt es ein \(c\in\), so dass \(f(c)=\gamma\).
Anhand dieser Informationen können wir den Bisektionsalgorithmus vorstellen. Zunächst müssen wir prüfen, ob \(\text{sign}(f(a)) \ne \text{sign}(f(b))\). Andernfalls enthält das Intervall nicht die Wurzel und muss eventuell erweitert werden. Dann können wir fortfahren:
-
Lassen Sie \(c = \frac{a + b}{2}\).
-
Wenn \(f(c) = 0\), stoppen Sie und geben Sie \(c\) zurück.
-
Wenn \(\text{sign}(f(a))\ne\text{sign}(f(c))\), dann setze \(b\leftarrow c\). Andernfalls, wenn \(\text{sign}(f(b))\ne\text{sign}(f(c))\), dann setze \(a\linker Pfeil c\).
-
Geh an den Anfang und wiederhole bis zur Konvergenz (siehe unten).
Nach \(n\) Iterationen ist die Größe des Intervalls, das die Wurzel umklammert, \(2^{-n}(b-a)\).
Der Bisektionsalgorithmus ist nützlich, konzeptionell einfach und leicht zu implementieren. Insbesondere braucht man keine besonderen Informationen über die Funktion \(f\), außer der Fähigkeit, sie an verschiedenen Punkten des Intervalls auszuwerten. Die Nachteile sind, dass er nur in einer Dimension nützlich ist und seine Konvergenz linear ist, was die langsamste Konvergenzrate für Algorithmen ist, die wir diskutieren werden (mehr dazu später).
Der Bisektionsalgorithmus kann in Situationen, in denen sich die Funktion \(f\) nicht gut verhält, auf Probleme stoßen. Die ideale Situation für den Bisektionsalgorithmus sieht etwa so aus.
Ideale Situation für den Bisektionsalgorithmus.
Hier haben \(f(a)\) und \(f(b)\) entgegengesetzte Vorzeichen und die Wurzel liegt eindeutig zwischen \(a\) und \(b\).
In dem folgenden Szenario wird der Algorithmus nicht starten, weil \(f(a)>0\) und \(f(b)>0\).
Die Ableitung von \(f\) an der Wurzel ist \(0\).
In diesem nächsten Szenario gibt es zwei Wurzeln zwischen \(a\) und \(b\), zusätzlich zu \(f(a)>0\) und \(f(b)>0\). Man müsste die Länge des Startintervalls reduzieren, um eine der beiden Wurzeln zu finden.
Zwei Wurzeln innerhalb des Intervalls.
In dem folgenden Szenario startet der Algorithmus, weil \(f(a)\) und \(f(b)\) entgegengesetzte Vorzeichen haben, aber es gibt keine Wurzel.
Das Intervall enthält eine Asymptote, aber keine Wurzel.
Die Konvergenz des Bisektionsalgorithmus kann entweder dadurch bestimmt werden, dass \(|b-a|<\varepsilon\) für ein kleines \(\varepsilon\) vorliegt oder dass \(|f(b)-f(a)|<\varepsilon\) vorliegt. Welches Kriterium Sie verwenden, hängt von der spezifischen Anwendung und den erforderlichen Toleranzen ab.
2.1.1 Beispiel: Quantile
Gegeben eine kumulative Verteilungsfunktion \(F(x)\) und eine Zahl \(p\in (0, 1)\), ist ein Quantil von \(F\) eine Zahl \(x\), so dass \(F(x) = p\). Der Bisektionsalgorithmus kann verwendet werden, um ein Quantil \(x\) für ein gegebenes \(p\) zu finden, indem die Funktion \(g(x) = F(x) – p\) definiert und der Wert von \(x\) ermittelt wird, der \(g(x) = 0\) ergibt.
Eine andere Möglichkeit, dies auszudrücken, ist, dass wir die CDF invertieren, um \(x = F^{-1}(p)\) zu berechnen. Der Bisektionsalgorithmus kann also verwendet werden, um Funktionen in diesen Situationen zu invertieren.