Bisektionsverfahren (Intervallhalbierung)
Manche Gleichungen kann man nicht nach $x$ auflösen. Eine Nullstelle lässt sich trotzdem beliebig genau finden – mit einem Verfahren, das nur eine einzige Frage stellt: Wo wechselt das Vorzeichen? Bei jeder Antwort wird das Suchgebiet halb so groß. Das ist das Bisektionsverfahren, auf Deutsch auch Intervallhalbierung genannt.
Die Grundidee: ein Vorzeichenwechsel
Stell Dir den Graphen einer Funktion vor, der ohne Sprung gezeichnet werden kann. Liegt er bei $x = a$ unterhalb der x-Achse und bei $x = b$ oberhalb, dann muss er dazwischen die Achse mindestens einmal kreuzen. Mathematisch: Ist $f$ auf $[a;\,b]$ stetig und haben $f(a)$ und $f(b)$ verschiedene Vorzeichen, dann gibt es zwischen $a$ und $b$ eine Nullstelle. Das ist der Zwischenwertsatz.
Achtung: nur ohne Sprünge
Bei $f(x) = \frac{1}{x}$ ist $f(-1) = -1$ und $f(1) = 1$ – trotzdem gibt es keine Nullstelle. Der Graph springt an der Polstelle $x = 0$ von $-\infty$ nach $+\infty$. Der Zwischenwertsatz gilt nur für stetige Funktionen.
Der Ablauf in vier Schritten
- Startintervall wählen: Suche $a$ und $b$ mit verschiedenen Vorzeichen von $f(a)$ und $f(b)$ – zum Beispiel mit einer kleinen Wertetabelle.
- Mitte berechnen: $m = \frac{a + b}{2}$ und den Funktionswert $f(m)$.
- Hälfte wählen: Hat $f(m)$ dasselbe Vorzeichen wie $f(a)$, liegt die Nullstelle rechts von $m$ – dann wird $m$ die neue linke Grenze. Sonst liegt sie links – dann wird $m$ die neue rechte Grenze.
- Wiederholen, bis das Intervall klein genug ist. Die Mitte des letzten Intervalls ist die Näherung.
Ist $f(m)$ zufällig genau 0, hast Du die Nullstelle exakt getroffen und bist fertig.
Schritt für Schritt: Intervall halbieren
| k | ak | bk | Mitte mk | f(mk) | weiter mit |
|---|
Beispiel: $\sqrt{3}$ ohne Wurzeltaste
$\sqrt{3}$ ist die positive Nullstelle von $f(x) = x^2 - 3$. Wegen $f(1) = -2 < 0$ und $f(2) = 1 > 0$ startest Du mit $[1;\,2]$. Weil $f(a)$ negativ ist, gilt in jedem Schritt: $f(m)$ negativ → rechte Hälfte, $f(m)$ positiv → linke Hälfte.
| k | $a_k$ | $b_k$ | Mitte $m_k$ | $f(m_k)$ | weiter mit |
|---|---|---|---|---|---|
| 0 | 1 | 2 | 1,5 | −0,75 | rechte Hälfte |
| 1 | 1,5 | 2 | 1,75 | 0,0625 | linke Hälfte |
| 2 | 1,5 | 1,75 | 1,625 | −0,359375 | rechte Hälfte |
| 3 | 1,625 | 1,75 | 1,6875 | −0,152344 | rechte Hälfte |
| 4 | 1,6875 | 1,75 | 1,71875 | −0,045898 | rechte Hälfte |
| 5 | 1,71875 | 1,75 | 1,734375 | 0,008057 | linke Hälfte |
| 6 | 1,71875 | 1,734375 | 1,7265625 | −0,018982 | rechte Hälfte |
| 7 | 1,7265625 | 1,734375 | 1,73046875 | −0,005478 | rechte Hälfte |
Nach acht Halbierungen ist das Intervall nur noch $\frac{1}{256} \approx 0{,}0039$ lang, und beide Grenzen beginnen mit $1{,}73$. Tatsächlich ist $\sqrt{3} = 1{,}7320508\ldots$
Wie genau ist das Ergebnis?
Jede Halbierung teilt die Länge des Intervalls durch 2. Nach $n$ Schritten ist das Intervall noch
Daraus erhältst Du die nötige Anzahl der Schritte für eine gewünschte Genauigkeit $\varepsilon$: Aus $\frac{b - a}{2^n} \le \varepsilon$ folgt $2^n \ge \frac{b - a}{\varepsilon}$, also
Beispiel
Startintervall $[1;\,2]$, das Intervall soll höchstens $0{,}001$ lang werden: $2^n \ge 1000$. Da $2^9 = 512$ noch zu klein und $2^{10} = 1024$ groß genug ist, brauchst Du 10 Halbierungen.
Als Faustregel gilt: Für jede weitere richtige Dezimalstelle sind etwa 3,3 zusätzliche Schritte nötig, denn $2^{3{,}3} \approx 10$. Das Verfahren ist also zuverlässig, aber nicht schnell.
Stärken und Grenzen
| Stärken | Grenzen |
|---|---|
| braucht keine Ableitung, nur Funktionswerte | langsam – viel langsamer als das Newton-Verfahren |
| funktioniert bei stetigen Funktionen immer, sobald ein Vorzeichenwechsel da ist | findet Nullstellen ohne Vorzeichenwechsel nicht, zum Beispiel doppelte Nullstellen wie bei $(x - 2)^2$ |
| der Fehler ist vorher bekannt (Fehlerschranke) | liegen mehrere Nullstellen im Intervall, findet es nur eine davon |
In der Praxis kombiniert man deshalb gern: Erst grenzt die Intervallhalbierung die Nullstelle sicher ein, dann liefert ein schnelles Verfahren wie das Newton-Verfahren die restlichen Stellen.
Rechner: Intervallhalbierung und Schrittzahl
Online üben
Rechne mit Dezimalzahlen und gib mehrere Werte mit Semikolon getrennt ein, zum Beispiel 1,5; 1,75; 1,625.
Stufe 3: Schrittzahl und Fehler
-
Aufgabe 1
\(\text{Länge } 3,\) Ziel: höchstens \(0{,}02\) lang. Halbierungen?\(\frac{3}{2^{8}} \le 0{,}02 < \frac{3}{2^{7}}\ \Rightarrow\ n = 8\)
-
Aufgabe 2
\(\text{Länge } 3:\) Länge nach \(3\) Halbierungen?\(\frac{3}{2^{3}} = 0{,}375\)
-
Aufgabe 3
\(\text{Länge } 4,\) \(3\) Halbierungen: Fehler der Mitte höchstens?\(\frac{4}{2^{4}} = 0{,}25\)
-
Aufgabe 4
\(\text{Länge } 4:\) Länge nach \(7\) Halbierungen?\(\frac{4}{2^{7}} = 0{,}03125\)
-
Aufgabe 5
\(\text{Länge } 2,\) Ziel: höchstens \(0{,}0001\) lang. Halbierungen?\(\frac{2}{2^{15}} \le 0{,}0001 < \frac{2}{2^{14}}\ \Rightarrow\ n = 15\)
Tippe Deine Lösung ein und klicke auf „Prüfen“ (oder drücke Enter). Brüche als 3/4, Dezimalzahlen mit Komma, mehrere Lösungen mit ; trennen, Potenzen als x^2, Wurzeln als sqrt(5). Punkte: 10 für richtig beim ersten Versuch, 6 nach einem Fehlversuch, 5 mit Tipp, 0 wenn Du Dir vorher die Lösung anschaust. Deine Punkte und Abzeichen siehst Du unter Mein Training.
Arbeitsblatt: Intervallhalbierung (Bisektion)
Eine volle DIN-A4-Seite Aufgaben mit Lösungsblatt zum Ausdrucken – bei jedem Klick neue Aufgaben. Klasse 10–12.
Wie man Nullstellen exakt berechnet, zeigt die Seite Nullstellen berechnen. Schnellere Näherungsverfahren findest Du beim Newton-Verfahren, der Regula falsi und dem Sekantenverfahren, eine ganz andere Idee bei der Fixpunktiteration.
Weiterlesen: Bisektion, Zwischenwertsatz bei Wikipedia