Bisektionsverfahren

Studium

m = \frac{a + b}{2}, \qquad [a, b] \to \begin{cases} [a, m], & f(a) \cdot f(m) \leq 0 \\ [m, b], & \text{sonst} \end{cases}

Voraussetzung: $f$ $stetig auf$ $[a, b],$ $f(a) \cdot f(b) < 0$

$a, b$: linke und rechte Grenze des aktuellen Intervalls
$m$: Mittelpunkt des Intervalls, neue Näherung
$f$: stetige Funktion, deren Nullstelle gesucht ist

Das Bisektionsverfahren halbiert ein Intervall mit Vorzeichenwechsel so lange, bis die Nullstelle genau genug eingeschlossen ist.

Erklärung

Das Bisektionsverfahren (Intervallhalbierung) sucht eine Nullstelle einer stetigen Funktion in einem Intervall $[a, b]$ , an dessen Enden $f$ verschiedene Vorzeichen hat. Nach dem Zwischenwertsatz liegt dann mindestens eine Nullstelle im Intervall.

In jedem Schritt berechnet man den Mittelpunkt $m$ und prüft das Vorzeichen von $f(m)$ . Man behält die Hälfte, in der der Vorzeichenwechsel liegt. Ist $f(m) = 0$ , hat man die Nullstelle gefunden.

Das Verfahren ist robust: Es konvergiert immer, wenn die Voraussetzungen erfüllt sind, und braucht keine Ableitung. Dafür ist es langsam. Nach $n$ Schritten ist das Intervall $\frac{b - a}{2^n}$ lang, pro Schritt gewinnt man also nur ein Bit an Genauigkeit (lineare Konvergenz mit Faktor $\frac{1}{2}$ ). Liegen mehrere Nullstellen im Intervall, findet man eine davon. Nullstellen ohne Vorzeichenwechsel, z.B. bei $x^2$ , findet das Verfahren nicht.

Beispiele

Nullstelle von $f(x) = x^2 - 2$ auf $[1, 2]$ : Es ist $f(1) = -1 < 0$ und $f(2) = 2 > 0$ .

\begin{aligned} m &= 1{,}5: & f(m) &= 0{,}25 > 0 & &\Rightarrow [1;\ 1{,}5] \\ m &= 1{,}25: & f(m) &= -0{,}4375 < 0 & &\Rightarrow [1{,}25;\ 1{,}5] \\ m &= 1{,}375: & f(m) &= -0{,}109375 < 0 & &\Rightarrow [1{,}375;\ 1{,}5] \\ m &= 1{,}4375: & f(m) &\approx 0{,}0664 > 0 & &\Rightarrow [1{,}375;\ 1{,}4375] \end{aligned}

Nach vier Schritten ist das Intervall $\frac{1}{2^4} = 0{,}0625$ lang. Der Mittelpunkt $1{,}40625$ weicht höchstens $0{,}03125$ von $\sqrt{2}$ ab.

Wie viele Schritte braucht man, um ein Intervall der Länge $1$ auf höchstens $10^{-6}$ zu verkleinern? Aus $2^n \geq 10^6$ folgt $n \geq \log_2 10^6 \approx 19{,}93$ , also $n = 20$ . Denn $2^{19} = 524288 < 10^6$ , aber $2^{20} = 1048576 \geq 10^6$ .

Typische Fehler

Die falsche Hälfte behalten. Entscheidend ist, wo das Vorzeichen wechselt, nicht, welcher Funktionswert kleiner ist.
Das Verfahren auf ein Intervall ohne Vorzeichenwechsel anwenden. Aus $f(a) \cdot f(b) > 0$ folgt nicht, dass keine Nullstelle existiert, aber das Verfahren garantiert dann nichts.
Stetigkeit vergessen: $f(x) = \frac{1}{x}$ wechselt auf $[-1, 1]$ das Vorzeichen, hat aber keine Nullstelle.

Bisektionsverfahren