Bisektionsverfahren

Im Beweis des folgenden Satzes, wir das so genannte Bisektionsverfahren benutzt. Dieses Verfahren ermöglicht es, Nullstellen numerisch zu berechnen, indem das Intervall, in dem sie auftreten können, immer weiter eingegrenzt wird, bis es kleiner als die geforderte Rechengenauigkeit ist.

Sei $f$ auf dem abgeschlossenen Intervall $[a,b]$ stetig, $f(a)<0$ und $f(b)>0$ dann hat $f$ in $]a,b[$ eine Nullstelle.

Analog gilt: Ist $f(a)>0$ und $f(b)<0$ dann hat $f$ in $]a,b[$ eine Nullstelle.

Wir setzen $a_0=a$ und $b_0=b$ und wenden folgendes Verfahren ein, um die Nullstelle einzugrenzen. Das Intervall wir halbiert und je nach Lage des Funktionswertes wird ein neues Teilintervall definiert, dass die Nullstelle garantiert enthält.

Sei $[a_n,b_n]$ das $n$-te Teilintervall. Es gelte $f(a_n)< 0$ und $f(b_n)>0$. Wir halbieren das Intervall und setzen

Nun unterscheiden wir drei Fälle:

Fall 1: $f(x_n)= 0$. Wir tun nichts weiter, denn die Behauptung wurde gezeigt.

Fall 2: $f(x_n)<0$. Wir setzen als neues Intervall $[a_{n+1},b_{n+1}]=[x_n,b_n]$.

Fall 3: $f(x_n)> 0$. Wir setzen als neues Intervall $[a_{n+1},b_{n+1}]=[a_n,x_n]$.

Für die Fälle 2 und 3 gilt jetzt wieder $f(a_{n+1})<0$ und $f(b_{n+1})>0$ und der Prozess der Teilung kann neu gestartet werden.

Wir zeigen jetzt, dass die Folgen $(a_n)$ und $(b_n)$ gegen den gleichen Grenzwert konvergieren. Die Folge $(a_n)$ ist nach oben beschränkt ($b$ ist eine obere Schranke) und monoton wachsend. Nach Satz 5225A konvergiert $(a_n)$ gegen ihr Supremum $s$. Es gilt

Die Differenz $(b_n-a_n)$ ist eine Nullfolge (die Intervalle werden immer kleiner!). Damit ist

Also konvergieren die beiden Folgen gegen den gleichen Grenzwert $s$.

Nun nutzen wir die Stetigkeit von $f$. Nach Satz 5225E und Satz 5225F gilt:

also $f(s)=0$.

Zum Beweis des zweiten Teils des Satzes geht man zu $-f(x)$ über und greift auf das schon Bewiesene zurück. $\qed$

Um z.B. $\sqrt 2$ zu berechnen, geht man von der Funktion $f(x)=x^2-2$ aus, deren positive Lösung die gesuchte Wurzel ist. Zum Start des Verfahrens nehmen wir $a_0=0$ und $b_0=2$. Die Tabelle zeigt die einzelnen Rechenschritte.

Man sieht wie sich die Werte langsam dem wahren Wert annähert. Dabei liegt die Betonung auf "langsam". Es gibt bessere Verfahren, wie das Newton-Verfahren, dass bei wesentlich weniger Iterationen bessere Ergebnisse liefert.