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.

Satz 15V9 (Existenz von Nullstellen)

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

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

 
 

Beweis

Wir setzen \(\displaystyle a_0=a\) und \(\displaystyle 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 \(\displaystyle [a_n,b_n]\) das \(\displaystyle n\)-te Teilintervall. Es gelte \(\displaystyle f(a_n)< 0\) und \(\displaystyle f(b_n)>0\). Wir halbieren das Intervall und setzen

\(\displaystyle x_n=\dfrac {a_n+b_n} 2\)

Nun unterscheiden wir drei Fälle:

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

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

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

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

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

\(\displaystyle b_n=a_n+(b_n-a_n)\)

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

\(\displaystyle \lim b_n=\lim a_n+\lim (b_n-a_n)=\lim a_n=s\).

Also konvergieren die beiden Folgen gegen den gleichen Grenzwert \(\displaystyle s\).

Nun nutzen wir die Stetigkeit von \(\displaystyle f\). Nach Satz 5225E und Satz 5225F gilt:

\(\displaystyle \lim f(a_n)=f(s)\leq 0\) und \(\displaystyle \lim f(b_n)=f(s)\geq 0\),

also \(\displaystyle f(s)=0\).

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

Beispiel 164X

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

\(\displaystyle n\) \(\displaystyle a_n\) \(\displaystyle b_n\) \(\displaystyle f(a_n)\) \(\displaystyle f(b_n)\) \(\displaystyle x_n\)
0 0 2 -2 2 1
1 1 2 -1 2 1,5
2 1 1,5 -1 0,25 1,25
3 1,25 1,5 -0,4375 0,25 1,375
4 1,375 1,5 -0,109375 0,25 1,4375
5 1,375 1,4375 -0,109375 0,066406 1,4062
6 1,40625 1,4375 -0,02246 0,066406 1,4219

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.

Seit man begonnen hat, die einfachsten Behauptungen zu beweisen, erwiesen sich viele von ihnen als falsch.

Bertrand Russell

Copyright- und Lizenzinformationen: Diese Seite ist urheberlich geschützt und darf ohne Genehmigung des Autors nicht weiterverwendet werden.
Anbieterkеnnzeichnung: Wurzelzieher Mathеpеdιa  •  Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе
 
G: 28.08.2015 06:59:19 (531 ms; 194 M)

Stetigkeit