Verwendung des Bisektionsverfahren

 Die Hauptsätze dieses Kapitels lassen sich alternativ durch Bisektion (Intervallhalbierung) beweisen. Für den Nullstellensatz erhalten wir im Allgemeinen nicht mehr die kleinste Nullstelle, dafür aber numerische Approximationen.

 Die Methode besteht darin, ein gegebenes kompaktes Intervall in zwei gleichlange kompakte Intervalle aufzuteilen, einen „guten“ Teil auszuwählen und das Verfahren zu wiederholen. Nach dem Prinzip der Intervallschachtelung existiert ein eindeutiger Schnittpunkt der konstruierten Intervalle, der durch die „gute“ Auswahl der Teilintervalle die gewünschte Eigenschaft besitzt.

Allgemeines Bisektionsverfahren

Für ein kompaktes reelles Intervall [ a, b ] seien

L(a, b)  =  [ a, (a + b)/2 ],(linke Intervallhälfte)

R(a, b)  =  [ (a + b)/2, b ].(rechte Intervallhälfte)

Weiter sei ℰ([ a, b ]) eine Eigenschaft, und es sei I0 = [ a0, b0 ] ein Startintervall. Wir definieren rekursiv solange möglich Intervalle In = [ an, bn ] durch:

In + 1  =  [ an + 1, bn + 1 ]  =  L(an, bn),  falls  ℰ(L(an, bn)),

In + 1  =  [ an + 1, bn + 1 ]  =  R(an, bn),  falls ansonsten  ℰ(R(an, bn)).

Gilt ℰ für beide Hälften von In = [ an, bn ] nicht, so ist In + 1 nicht definiert ud die Rekursion bricht an der Stelle n ab. Andernfalls heißt (In)n  ∈  ℕ die (linkslastige) Bisektionsfolge von [ a0, b0 ] für die Erhaltungseigenschaft ℰ, und das eindeutige p mit ⋂n In = { p } der durch das Verfahren berechnete Punkt.

 Es gilt bn − an = (b0 − a0)/2n für alle definierten In. Bricht das Verfahren nicht ab, so gilt supn an = p = infn bn für den berechneten Punkt p.

 Ein wichtiges Beispiel hatten wir schon kennengelernt. Wir formulieren neu:

Beweis des Satzes von Bolzano-Weierstraß

Sei (xn)n  ∈  ℕ eine Folge in [ a0, b0 ]. Sei (In)n  ∈  ℕ die Bisektionsfolge des Startintervalls I0 = [ a0, b0 ] für

ℰ(a, b)  =  „es gibt unendlich viele n mit xn  ∈  [ a, b ]“.

Das Verfahren bricht nicht ab und der berechnete Punkt p ist ein Häufungspunkt der Folge.

Analog wird ein Häufungspunkt einer unendlichen Menge M ⊆ [ a0, b0 ] gefunden. Hier verwenden wir die Erhaltungseigenschaft

ℰ(a, b)  =  „M ∩ [ a, b ] ist unendlich“.

 Der Nullstellensatz (und damit der Zwischenwertsatz) lässt sich ebenfalls recht einfach durch das Bisektionsverfahren beweisen:

Beweis des Nullstellensatzes

Sei f: [ a0, b0 ] → ℝ stetig mit f (a) < 0 und f (b) > 0. Wir führen das Bisektionsverfahren durch mit I0 = [ a0, b0 ] und der Erhaltungseigenschaft

ℰ(a, b)  =  „f (an) < 0 und f (bn) > 0“.

Ist f (cn) = 0 mit cn = (an + bn)/2, so bricht das Verfahren bei n ab, und eine Nullstelle von f ist gefunden. Ist f (cn) ≠ 0, so hat f für (an, cn, bn) die Vorzeichen (−, +, +) oder (−, −, +), sodass L(an, bn) bzw. R(an, bn) als nächstes Intervall verwendet wird. Bricht das Verfahren nicht ab, so gilt für den berechneten Punkt p mit { p } = ⋂n In aufgrund der Stetigkeit von f bei p:

0  ≤  limn(f (an))  =  f (p)  ≤  limnf (bn)  ≤  0.

Damit gilt f (p) = 0.

 Wir geben in knapper Form Bisektionsbeweise für die beiden anderen Hauptsätze. Der interessierte Leser möge die Details ergänzen.

Beweis des Extremwertsatzes von Weierstraß

Sei f : [ a0, b0 ] → ℝ stetig. Sei s = sup(f [ I0 ]) ≤ ∞. (Es wird sich zeigen, dass s < ∞.) Wir bisektieren I0 = [ a0, b0 ] mit

ℰ(a, b)  =  „sup { f (x) | x  ∈  [ a, b ] }  =  s“.

Das Verfahren bricht nicht ab. Für den berechneten Punkt p gilt f (p) = s (aufgrund der Stetigkeit von f in p), sodass

f (p)  =  max(f [ I0 ])  <  ∞.

 Im Gegensatz zum Nullstellensatz ergibt sich aus dem Beweis kein Approximationsverfahren zur Berechnung von Extremwerten.

Beweis des Satzes von Heine über gleichmäßige Stetigkeit

Wir führen den Beweis indirekt. Sei f : [ a0, b0 ] → ℝ nicht gleichmäßig stetig. Wir zeigen, dass f an einer gewissen Stelle p nicht stetig ist. Sei hierzu ε > 0 derart, dass die gleichmäßige Stetigkeit von f für ε verletzt ist. Wir bisektieren nun wir das Startintervall I0 = [ a0, b0 ] mit

ℰ(a, b)  =  „∀δ > 0 ∃x  ∈  [ a, b ] ∃x′  ∈  I0 (|x − x′| < δ ∧ |f (x) − f (x′)| ≥ ε“).

Das Verfahren bricht nicht ab (da wir in ℰ(a, b) nur verlangen, dass x in [ a, b ] liegt; der „Partner“ x′ kann außerhalb liegen). Für den berechneten Punkt p gilt

(+)  f ist unstetig an der Stelle p.

 Die Funktion f : [ −1/2, 1/2 ] → ℝ mit f (x) = −1 für x ≤ 0 und f (x) = 1 für x > 0 illustriert die Eigenschaft ℰ(a, b). Das Verfahren findet die Sprungstelle 0 mit den Intervallen In = [ − 1/2n, 0 ]. Von Zeugenpaaren (x, x′) für die Verletzung der gleichmäßigen Stetigkeit für ε = 1 liegt immer nur ein Punkt in In.

 Wir beenden diesen Abschnitt mit einem numerischen Experiment:

Beispiel: Nummerische Berechnung der Nullstelle durch Bisektion

Wir berechnen 2, indem wir das Bisektionsverfahren auf die Funktion f : [ 0, 2 ] → ℝ mit f (x) = x2 − 2 anwenden. Es gilt f (0) < 0 und f (2) > 0. Eine Computerberechnung liefert die folgenden Bisektionsintervalle:

I0 =  [ 0, 2 ] 
I1 =  [ 1, 2 ]rechts
I2 =  [ 1, 3/2 ]links
I3 =  [ 5/4, 3/2 ]rechts
I4 =  [ 11/8, 3/2 ]rechts
I5 =  [ 11/8, 23/16 ]links
I6 =  [ 45/32, 23/16 ]rechts
I7 =  [ 45/32, 91/64 ]links
I8 =  [ 181/128, 91/64 ]rechts
I9 =  [ 181/128, 363/256 ]links
I10 =  [ 181/128, 725/512 ]links

Auf sechs Nachkommastellen gerundet gilt

181/128  =  1,414063;  2  =  1,414214;  725/512  =  1,416016.

Für I50 = [ a50, b50 ] gilt

a50  =  796131459065721562949953421312  =  1,4142135623730940

b50  =  398065729532861281474976710656  =  1,4142135623730958

Das Verfahren kann das Heron-Verfahren nicht ersetzen (vgl. 2.1), hat aber den Vorteil der universellen Einsetzbarkeit: Es liefert beliebig genaue Approximationen an eine Nullstelle einer beliebigen stetigen Funktion f : [ a0, b0 ] → ℝ mit verschiedenen Vorzeichen bei a0 und b0.