Logo

Mathepedia

Unterstützen Sie die Mathepedia!

Jetzt

Mathepedia auf Facebook

Wurzelzieher Blog

Stetigkeit


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 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.

Beweis

Wir setzen a0 = a und b0 = 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 [an , bn ] das n-te Teilintervall. Es gelte f(an ) < 0 und f(bn ) > 0. Wir halbieren das Intervall und setzen
wFormel
Nun unterscheiden wir drei Fälle:
Fall 1: f(xn ) = 0. Wir tun nichts weiter, denn die Behauptung wurde gezeigt.
Fall 2: f(xn ) < 0. Wir setzen als neues Intervall [an + 1 , bn + 1 ] = [xn , bn ].
Fall 3: f(xn ) > 0. Wir setzen als neues Intervall [an + 1 , bn + 1 ] = [an , xn ].
Für die Fälle 2 und 3 gilt jetzt wieder f(an + 1 ) < 0 und f(bn + 1 ) > 0 und der Prozess der Teilung kann neu gestartet werden.
Wir zeigen jetzt, dass die Folgen (an ) und (bn ) gegen den gleichen Grenzwert konvergieren. Die Folge (an ) ist nach oben beschränkt (b ist eine obere Schranke) und monoton wachsend. Nach Satz 5225A konvergiert (an ) gegen ihr Supremum s. Es gilt
bn = an + (bn - an )
Die Differenz (bn - an ) ist eine Nullfolge (die Intervalle werden immer kleiner!). Damit ist
lim bn = lim an + lim(bn - an ) = lim an = s.
Also konvergieren die beiden Folgen gegen den gleichen Grenzwert s.
Nun nutzen wir die Stetigkeit von f. Nach Satz 5225E und Satz 5225F gilt:
wFormel und wFormel,
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. wFormel

Beispiel 164X

Um z.B. wFormel zu berechnen, geht man von der Funktion f(x) = x2 - 2 aus, deren positive Lösung die gesuchte Wurzel ist. Zum Start des Verfahrens nehmen wir a0 = 0 und b0 = 2. Die Tabelle zeigt die einzelnen Rechenschritte.
n an bn f(an ) f(bn ) xn
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.

Wer die erhabene Weisheit der Mathematik tadelt, nährt sich von Verwirrung.

Leonardo da Vinci

 

 

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: 23.01.2014 11:54:41 (559 ms; 319 M)
C: 30.10.2014 16:52:39 (31 ms; 228 M)