Bisektionsverfahren Rechner (Bolzano, Lineare Konvergenz)

Bisektionsverfahren-Rechner für Nullstellen: garantierte lineare Konvergenz 1 Stelle alle 3 Iterationen, basiert auf Bolzano-Theorem f(a)*f(b)<0, robust.

Berechnungsparameter
War dieser Rechner nützlich?

Bisektionsverfahren

Das Bisektionsverfahren (oder Dichotomie) ist der robusteste Algorithmus zum Finden von Nullstellen stetiger Gleichungen f(x) = 0. Basiert auf dem Bolzano-Theorem: wenn f stetig auf [a,b] und f(a) f(b) < 0, existiert mindestens eine Nullstelle in (a,b). Jede Iteration halbiert das Intervall und garantiert Konvergenz.

Geometrische Idee

Bei Intervall [a,b] mit f(a), f(b) entgegengesetzten Vorzeichen, Mittelpunkt c = (a+b)/2 berechnen und f(c) auswerten. Teilintervall [a,c] oder [c,b] wählen, das Vorzeichenwechsel beibehält. Wiederholen bis Intervall kleiner als Toleranz.

Bolzano-Theorem

Wenn f: [a,b] -> R stetig und f(a) f(b) < 0, dann existiert mindestens ein c in (a,b) mit f(c) = 0. Theorem (Bernhard Bolzano 1817) Grundlage des Verfahrens. Wesentliche Annahmen: Stetigkeit und Vorzeichenwechsel an Endpunkten.

Algorithmus

  1. Prüfen f(a) f(b) < 0.
  2. c = (a + b) / 2 berechnen.
  3. f(c) auswerten. Wenn |f(c)| < Tol oder |b-a| < Tol: STOPP, Nullstelle = c.
  4. Wenn f(a) f(c) < 0: neues Intervall [a, c]. Sonst: [c, b].
  5. Zurück zu Schritt 2.

Lineare Konvergenz

Jede Iteration halbiert das Intervall: |I_n| = (b-a) / 2^n. Für Präzision eps: n >= log_2((b-a)/eps). Beispiel: Intervall [1,2] (Breite 1), Präzision 1e-10: 33 Iterationen. Maschinenpräzision: 53 Iterationen.

Vergleich mit anderen Verfahren

  • Bisektion: Ordnung 1 (linear), IMMER garantiert wenn f Vorzeichen wechselt.
  • Newton: Ordnung 2 (quadratisch), schnell aber kann divergieren.
  • Sekante: Ordnung phi ~ 1.618, schnell aber nicht immer konvergent.
  • Regula falsi: hybrid, robust wie Bisektion aber schneller.
  • Brent: kombiniert Bisektion + inverse quadratische Interpolation, Standard in scipy.

Vor- und Nachteile

Vorteile: GARANTIERTE Konvergenz nach Bolzano, a priori Iterationsschätzung, unempfindlich gegen Ableitungen/Spitzen, einfache Implementierung. Nachteile: LANGSAME Konvergenz (1 Binärstelle pro Iter), benötigt Intervall mit Vorzeichenwechsel, findet EINE Nullstelle pro Intervall.

Hybridstrategie

Kombination von Bisektion mit superlinearen Verfahren (Sekante, Newton) ist beste Strategie. Algorithmen wie Brent (1973) oder Dekker (1969) verwenden Sicherheits-Bisektion wenn Interpolation versagt. Standard in scipy.optimize.brentq, MATLAB fzero, R uniroot.

Geschichte

Verfahren bekannt bei Antiken (Babylonier, Heron). Bolzano formalisierte es 1817 mit Zwischenwertsatz. Cauchy nahm es 1821 in "Cours d Analyse" als Standardalgorithmus auf. Seine Einfachheit und Robustheit machen es noch heute zu einem der meistverwendeten als Fallback.

Bisektion uber Nullstellen hinaus: Binarsuche und Optimierung

Die Idee, ein Intervall wiederholt zu halbieren, geht weit uber die Nullstellensuche hinaus. Die Binarsuche, einer der grundlegendsten Algorithmen der Informatik, ist konzeptionell identisch: um ein Element in einem sortierten Array zu finden, vergleicht man den mittleren Wert und verwirft bei jedem Schritt die Halfte der Kandidaten, genau wie die Bisektion die Halfte des Intervalls verwirft. Beide erreichen die Antwort in einer Schrittzahl proportional zum Logarithmus der Problemgrosse.

Dieselbe Strategie gilt fur jedes monotone Pradikat: die Technik der "Binarsuche uber die Antwort" lost Optimierungsprobleme, indem sie den Schwellenwert findet, ab dem eine Bedingung wahr wird. Fur unimodale Funktionen (mit einem einzigen Maximum oder Minimum) teilt die Variante namens Ternarsuche das Intervall in drei Teile und lokalisiert das Extremum im selben Geist. Die Bisektion ist somit der Prototyp einer ganzen Familie von Teile-und-herrsche-Algorithmen, die auf der Halbierung beruhen.

Robustheit und Grenzen: wann die Bisektion die richtige Wahl ist

Der grosse Vorzug der Bisektion ist ihre absolute Garantie: ist die Funktion stetig und wechselt an den Grenzen das Vorzeichen, konvergiert das Verfahren stets, ohne Ausnahme, und liefert eine sichere Fehlerschranke, genau (b-a)/2^n nach n Schritten. Diese Zuverlassigkeit macht sie in Kontexten wertvoll, in denen ein Versagen nicht zulassig ist, und als Sicherheitskomponente in Hybridverfahren, die sie mit Newton oder der Sekante kombinieren, um Garantie und Geschwindigkeit zu vereinen.

Ihre Grenzen sind ebenso klar. Die Bisektion kann keine Nullstellen gerader Vielfachheit finden, wo die Funktion die Achse ohne Vorzeichenwechsel beruhrt, keine komplexen Nullstellen und keine mehreren Nullstellen im selben Intervall (sie isoliert nur eine). Ihre lineare Konvergenz, die etwa eine Dezimalstelle alle 3-4 Iterationen gewinnt, ist langsam gegenuber superlinearen Verfahren. Sie ist das ideale Werkzeug, wenn Sicherheit wichtiger als Geschwindigkeit ist, oder als Sicherheitsnetz fur aggressivere Verfahren.

Aktualisiert im Juli 2026

Häufig gestellte Fragen

Was ist das Bisektionsverfahren?

Es ist ein iteratives Verfahren zur Bestimmung der Nullstellen von f(x)=0 in einem Intervall [a,b], in dem die Funktion das Vorzeichen wechselt. In jedem Schritt berechnet es den Mittelpunkt c=(a+b)/2 und wahlt die Halfte, in der der Vorzeichenwechsel bestehen bleibt, und halbiert das Intervall wiederholt bis zur gewunschten Genauigkeit.

Auf welchem Satz beruht es?

Auf dem Satz von Bolzano (oder dem Zwischenwertsatz): nimmt eine stetige Funktion an den Grenzen eines Intervalls Werte entgegengesetzten Vorzeichens an, so verschwindet sie mindestens einmal im Inneren. Dies garantiert die Existenz einer Nullstelle und die Konvergenz des Verfahrens.

Wie schnell ist die Konvergenz?

Die Bisektion konvergiert linear: jede Iteration halbiert das Intervall genau und gewinnt etwa 0,3 Dezimalstellen pro Schritt (ein Bit Genauigkeit). Es werden etwa log2((b-a)/epsilon) Iterationen benotigt: zum Beispiel 33 Iterationen fur 10 Dezimalstellen ausgehend von einem Einheitsintervall.

Was sind die Vorteile der Bisektion?

Die Konvergenz ist stets garantiert, wenn die Bolzano-Voraussetzungen gelten, ohne Divergenzrisiko. Sie benotigt keine Ableitung, ist einfach zu implementieren und liefert bei jedem Schritt eine sichere Fehlerschranke (b-a)/2^n, was schnellere Verfahren nicht bieten.

Was sind ihre Grenzen?

Sie findet keine Nullstellen gerader Vielfachheit (ohne Vorzeichenwechsel), keine komplexen Nullstellen, und gibt es im Intervall mehrere Nullstellen, isoliert sie nur eine. Zudem ist sie langsam: die lineare Konvergenz macht sie weit weniger effizient als superlineare Verfahren wie die Sekante oder Newton.

Wie viele Iterationen fur eine gegebene Genauigkeit?

Genau n >= log2((b-a)/epsilon), wobei epsilon die gewunschte Toleranz ist. Diese Formel folgt daraus, dass das Intervall nach n Halbierungen die Breite (b-a)/2^n hat. Es ist eines der wenigen Verfahren mit im Voraus vorhersagbarer Iterationszahl.

Welchen Bezug hat es zur Binarsuche?

Es ist dieselbe Idee: den Suchraum bei jedem Schritt zu halbieren. Die Binarsuche findet ein Element in einem sortierten Array durch Verwerfen der Halfte der Kandidaten; die Bisektion findet eine Nullstelle durch Verwerfen der Halfte des Intervalls. Beide haben logarithmische Kosten in der Problemgrosse.

Wann lohnt sich die Bisektion?

Wenn Sicherheit wichtiger als Geschwindigkeit ist: sie ist die ideale Wahl, wenn eine absolute Konvergenzgarantie und eine sichere Fehlerschranke benotigt werden. Sie dient auch als robuste Komponente in Hybridverfahren, wo die Bisektion die Konvergenz garantiert, wahrend Newton oder die Sekante die Geschwindigkeit liefern.

Kommentare (0)

Noch keine Kommentare. Sei der Erste!