Bisektion

Die Bisektion, auch fortgesetzte Bisektion oder Intervallhalbierungsverfahren genannt, ist ein Verfahren der Mathematik und der Informatik. Bisektion erzeugt endlich viele Glieder einer Intervallschachtelung, also eine Folge von Intervallen, die genau eine reelle Zahl definiert. Je ein Intervall entsteht aus dem vorhergehenden durch Teilung in zwei Hälften; hierfür stehen die lateinischen Bestandteile bi („zwei“) und sectio („Schnitt“) des Wortes „Bisektion“.

Grundsätzlich finden Bisektionsverfahren immer dann Anwendung, wenn ein Problem gelöst werden kann, indem es in zwei etwa gleich große Teilprobleme zerlegt wird, die dann einzeln für sich behandelt werden können.

Beispiel

Ein einfaches Beispiel stellt folgende Aufgabe dar: Gesucht ist eine Zahl zwischen 1 und 1000, die ein Spieler erraten soll. Er erhält als Hinweis immer nur „größer“ oder „kleiner“ oder „Treffer“.

Angenommen die Zahl sei 512. Verwendet der Spieler zum Raten das Bisektionsverfahren der binären Suche, ergibt sich folgender Dialog:

1. 500 – größer
2. 750 – kleiner
3. 625 – kleiner
4. 562 – kleiner
5. 531 – kleiner
6. 515 – kleiner
7. 507 – größer
8. 511 – größer
9. 513 – kleiner
10. 512 – Treffer

Hätte der Spieler stattdessen linear gesucht und bei 1 begonnen, so hätte der Dialog folgenden Verlauf genommen:

1. 1 – größer

2. 2 – größer

…

511. 511 – größer

512. 512 – Treffer

Statt zehn Fragen hätte er also 512 Fragen gebraucht; die Bisektion ist hier also deutlich effizienter.

Laufzeit und Konvergenz

Diskreter Fall

Im diskreten Fall, also wenn das zugrundeliegende Problem nur eine endliche Anzahl von zu testenden Lösungen besitzt, kann ein solches Problem immer als eine Suche aufgefasst werden: Aus einer endlichen Menge $M$ soll ein Element $x$ mit der Eigenschaft $p(x)=0$ gefunden werden. $p$ soll hierbei eine Funktion

$p\colon M\to \mathbb {R}$

sein, wobei Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle p(y)=0} genau dann gelten soll, wenn die gesuchte Eigenschaft erfüllt ist, also $y=x$. Um dieses Problem mittels Bisektion zu lösen, soll weiterhin gelten:

• Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle p(y)<0} falls $y<x$
• $p(y)>0$ falls Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y>x}

Die Funktion $p$ gibt also nicht nur den Treffer an (bei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p(x)=0} ), sondern weist im anderen Fall auch die Richtung, in der weitergesucht werden muss. Dabei wird natürlich stillschweigend vorausgesetzt, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} durch eine Relation < geordnet wird.

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} wird in zwei möglichst gleich große Hälften geteilt, indem zunächst $p$ für ein Element möglichst nah der Mitte von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} ausgewertet wird. Der Fall, dass sich Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle M} aufgrund einer ungeraden Anzahl von Elementen lediglich in zwei nur ungefähr gleich große Teile teilen lässt, kann unterschlagen werden, er wirkt sich bei großen Elementzahlen so gut wie nicht aus. Nach jedem Schritt kann also eine Hälfte der zuletzt untersuchten Menge verworfen werden, die Menge halbiert sich mit jeder Auswertung von $p$. Das Verfahren endet spätestens, wenn die Menge nur noch ein Element enthält, dieses muss das gesuchte sein, sofern es überhaupt in der Ausgangsmenge enthalten war. Um also eine Menge der Größe $m$ durch fortgesetztes Halbieren auf 1 zu reduzieren, sind Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Schritte notwendig, mit:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m < 2^n \Rightarrow \log_2 m < n}

Das Verfahren hat also eine Laufzeit von OFehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle (\log(m))} .

Kontinuierlicher Fall

Datei:Bisektion Ani.gif

Ablauf der Bisektion (Animation)

Im kontinuierlichen Fall ist als Lösung meist ein Intervall gesucht, das ein Teilintervall eines anderen gegebenen endlichen Intervalls ist. Eine wichtige Anwendung ist die Suche nach einem kleinen Intervall, das eine Nullstelle einer gegebenen Funktion enthält:

Gesucht ist die Nullstelle einer stetigen streng monoton steigenden Funktion $f$ im Intervall $[a,b]$. Diese soll mit einer Genauigkeit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varepsilon} angegeben werden; es wird also ein Teilintervall von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle [a,b]} gesucht, das die Nullstelle enthält und höchstens die Länge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varepsilon} hat. Da es unendlich viele derartige Intervalle gibt, können diese nicht einfach alle durchprobiert werden. Es gilt jedoch:

• Eine stetige streng monoton steigende Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f} hat in einem Intervall Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle [l,r]} genau dann eine Nullstelle, wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(l)<0} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(r)>0} ist.

Dies führt zu folgendem Algorithmus:

1. Setze Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle l=a} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r=b} .
2. Teste, ob Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle [l,r]} eine Nullstelle enthält. Wenn nicht: Abbruch.
3. Teste, ob Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r-l < \varepsilon} ist. Wenn ja, ist das Lösungsintervall gefunden.
4. Sonst teile $[l,r]$ in der Mitte und setze das Verfahren mit beiden Teilintervallen rekursiv bei 2. fort.

Ähnlich wie im diskreten Fall endet der Algorithmus spätestens, wenn das Intervall die Länge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \varepsilon} unterschreitet. Also:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \frac{b-a}{2^n} < \varepsilon \Rightarrow \log_2 \frac{b-a}{\varepsilon} < n}

Es ergibt sich somit eine logarithmische Laufzeit in Abhängigkeit vom Verhältnis der Intervalllänge zur gewünschten Genauigkeit.

Die Monotonie der Funktion ist nicht zwingend erforderlich. Eine stetige Funktion hat im Intervall $[l,r]$ nach dem Zwischenwertsatz schon dann mindestens eine Nullstelle, wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(l) f(r)<0} . Der Algorithmus ist dem obigen sehr ähnlich und sieht dann so aus:

1. Setze Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle l=a} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r=b} .
2. Teste, ob Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f(l) f(r)<0} . Wenn nicht: Abbruch.
3. Setze Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle c=\frac{l+r}{2}} .
4. Wenn $f(l)f(c)<0$ setze Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r=c} sonst setze Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle l=c}
5. Teste, ob Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r-l < \varepsilon} ist. Wenn ja, ist das Lösungsintervall gefunden.

Vor- und Nachteile des Verfahrens

Die Bisektion eignet sich für folgende Fälle:

• Ein Vorzeichenwechsel liegt im gegebenen Intervall vor und die Funktion ist stetig
• Die Startwerte der klassischen Verfahren (Newton-Verfahren, Regula falsi) liegen nicht hinreichend nah genug an der Nullstelle, so dass dort keine lokale Konvergenz eintritt
• Mehrfache Nullstellen mindern die Konvergenzgeschwindigkeit der klassischen Verfahren

Nachteile der Bisektion:

• Bei einfachen Fällen (streng monotone Funktion) ist sie langsamer als ein quadratisch konvergentes Verfahren
• Ohne Vorzeichenwechsel im gegebenen Intervall sind Zusatzprüfungen notwendig, um ein lokales Minimum von einer Nullstelle zu unterscheiden

Bisektion und Binärbäume

Es besteht ein enger Zusammenhang zwischen Bisektion und Binärbäumen. Während einer Bisektion wird in jedem Schritt eine Entscheidung getroffen, ob mit der linken oder der rechten Teilmenge fortgesetzt werden soll, und beim Durchlaufen eines Binärbaums von der Wurzel aus muss in jedem Knoten entschieden werden, ob der linken oder der rechten Kante gefolgt werden soll. Zu einer gegebenen Mengengröße und einem Bisektionsverfahren gibt es also genau einen zugeordneten Binärbaum, der alle potentiellen Verläufe der Bisektion beschreibt. Der Baum hat dabei genau so viele Blätter, wie das gegebene Problem mögliche Ergebnisse liefern kann. Da sich mit jeder Entscheidung in einem Knoten die Anzahl der noch möglichen Ergebnisse etwa halbiert, hat er ungefähr

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \log_2 m}

Ebenen. Dies entspricht der Laufzeit der Bisektion, da die Anzahl der Ebenen die Weglänge von oben nach unten festlegt, die wiederum gleich der Laufzeit ist. Der sich durch diese Zuordnung ergebende Baum entspricht einem balancierten binären Suchbaum.

Bisektion und binäre Zahlen

Bisektion lässt sich beispielsweise auch verwenden, um die binäre Darstellung einer Zahl zu ermitteln. Eine Zahl zwischen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m-1} kann durch eine Folge von „größer-oder-gleich“- und „kleiner“-Entscheidungen gekennzeichnet werden. Wird Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} als eine Potenz von 2 gewählt, so kann immer auf das Element „rechts der Mitte“ getippt werden, da die Menge eine gerade Größe hat. Für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m=8} ergibt sich zum Beispiel die Menge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left\{ 0,\ldots,7 \right\}} – die Suche nach der 2 liefe nun wie folgt ab:

• 4 – kleiner
• 2 – größer oder gleich (auf einen „Treffer“ wird verzichtet)
• 3 – kleiner

Damit ist die 2 genau beschrieben. Setzen wir nun für „kleiner“ die 0 und für „größer oder gleich“ die 1, so ergibt sich 010. Dies ist gerade die binäre Darstellung der 2.

Weblinks

• Bisektion – Ein größeres Beispiel
• Bisektion – Programmierbeispiel (englisch)