Intervallhalbierung

Intervallhalbierung, auch Bisectionsmethode genannt, ist ein einfaches numerisches Verfahren zum Bestimmen einer Nullstelle einer stetigen Funktion f auf dem Intervall [a,b], für das f(a) und f(b) unterschiedliche Vorzeichen haben. Nach dem Zwischenwertsatz existiert in diesem Intervall mindestens eine Nullstelle.

Voraussetzungen und Zielsetzung: Die Funktion muss auf [a,b] stetig sein, und f(a)·f(b) ≤ 0. Falls mehrere Nullstellen vorhanden sind, garantiert die Methode lediglich die Existenz einer Nullstelle in dem internen Intervall, das während des Verfahrens entsteht, und konvergiert gegen eine dieser Nullstellen.

Vorgehen: Man setzt c = (a+b)/2 und berechnet f(c). Falls f(a)·f(c) ≤ 0, wird das Intervall [a,b] durch Ersetzen von b durch c auf [a,c] verkürzt; andernfalls wird das Intervall auf [c,b] verkürzt. Dieser Bracketing-Schritt wiederholt sich iterativ, wodurch das Intervall, das eine Nullstelle einschließt, immer kleiner wird.

Konvergenz und Abbruch: Der Prozess liefert eine Folge geschlossener Intervalle, deren Länge sichhalbiert. Die Konvergenz ist linear. Abbruchkriterien sind typischerweise |b−a| < tol oder |f(c)| < tol bzw. eine maximale Anzahl von Iterationen. Die Methode liefert auch eine geeignete Näherung c als Mittelwert des letzten Intervalls.

Eigenschaften und Komplexität: Die Intervallhalbierung ist robust, benötigt keine Ableitungen und funktioniert unter nur milden Voraussetzungen. Sie ist jedoch vergleichsweise langsam, da die Fehlerreduktion proportional zur Zahl der Iterationen bleibt. Die Anzahl der benötigten Funktionsauswertungen liegt ungefähr bei log2((b−a)/tol).

Anwendungen: Sie dient als zuverlässige Grundmethode in der Numerik und als Baustein in komplexeren Algorithmen wie Brent-Methoden, die Bracketing mit Interpolation kombinieren.