Die Intervallschachtelung ist ein iteratives Gleichungslösungsverfahren der Mathematik. Idee des Verfahrens ist, dass sich eine Lösung einer Gleichung oft nicht unmittelbar berechnen lässt, dass sich aber sehr wohl ein Intervall finden lässt, das die Lösung enthält, wenn man die richtige Grundmenge zugrunde legt. Durch schrittweise Verkleinerung dieses Intervalls findet man beliebig genaue Näherungen der Lösung.

Nullstellensuche bei einer stetigen Funktion

Bei der Suche nach den Nullstellen einer stetigen Funktion f kann man so vorgehen:

1. Man ermittelt ein Intervall [a, b] mit der Eigenschaft, dass der Funktionswert f(a) der einen Intervallgrenze das entgegengesetzte Vorzeichen des Funktionswertes f(b) der anderen Intervallgrenze hat. (Dazu rechnet man z.B. die Funktion an einigen ganzzahligen Stellen aus.)
2. Das Intervall [a, b] wird an einem Punkt c zwischen a und b in zwei Teilintervalle [a,c] und [c,b] geteilt (zur Wahl von c siehe unten die Strategien).
3. Man berechnet den Funktionswert f(c).
4. Man wählt ein Teilintervall, das mit Sicherheit eine Nullstelle enthält: Das Intervall [a, c] enthält eine Nullstelle von f, wenn f(a) und f(c) verschiedene Vorzeichen haben, ansonsten enthält das Intervall [c, b] eine Nullstelle (es können jedoch auch beide Intervalle Nullstellen enthalten, das Verfahren kann aber nur eine finden). Im Fall, dass f(c) = 0 ist, endet natürlich das Verfahren mit der gefundenen Nullstelle c.
5. Man fährt fort, das gefundene Intervall solange zu verkleinern, bis man eine Nullstelle direkt findet, oder bis die Intervall-Länge klein genug ist, damit man die Randpunkte als geeignete Näherungen betrachten kann; wenn also die Intervallschachtelung nicht bei einem glatten Dezimalbruch endet, bricht man sie bei Erreichen der gewünschten Genauigkeit ab.

Bricht man die Intervallschachtelung nicht ab, sondern verkleinert die Intervalle immer weiter, dann erhält man beim Grenzübergang genau eine Zahl, die in allen Intervallen liegt. Dass diese eine Nullstelle von f ist, ist die Aussage des Zwischenwertsatzes, der weiter unten in diesem Artikel bewiesen wird.

Beispiel

Gesucht sei eine Lösung der Gleichung

x³ + 0,49x² - 0,9256x - 0,2646 = 0

oder anders ausgedrückt: Gesucht ist eine Nullstelle der Funktion

f(x) = x³ + 0,49x² - 0,9256x - 0,2646.

Da die Funktion stetig ist und weil f(0) = -0,2646 < 0 und f(1) = 1+0,49-0,9256-0,2636 > 0, liegt eine Nullstelle mit Sicherheit zwischen x=0 und x=1, also im Intervall [0;1].

Wird nun f(0,5) = 0,5³+0,49·0,5²-0,9256·0,5-0,2646=-0,4799 < 0 berechnet, so ergibt sich das Intervall [0,5;1], da hier der Vorzeichenwechsel stattfindet.

Aus f(0,8) = 0,8³+0,49·0,8²-0,9256·0,8-0,2646 = -0,17948 < 0 ergibt sich das Intervall [0,8;1],

aus f(0,9) = 0,9³+0,49·0,9²-0,9256·0,9-0,2646 = +0,02826 > 0 ergibt sodann sich das Intervall [0,8;0,9].

Da die Nullstelle zwischen 0,8 und 0,9 liegt, wird nach dem gleichen Verfahren die zweite Nachkommastelle ermittelt. So wird die Nullstelle x=0,88 gefunden. Die beiden anderen lassen sich nun durch Polynomdivision und anschließende Quadratische Ergänzung ermitteln.

Strategien

1. Die fortgesetzte Halbierung der Intervalle durch die Wahl
   c := (a+b)/2
   führt im Dezimalsystem sehr schnell zu Brüchen mit sehr vielen Nachkommastellen und ist somit in der Regel ungeeignet. Dagegen ist sie im Dualsystem die bevorzugte Wahl, da sie der dortigen Bruchdarstellung entspricht.
2. Die annähernde Halbierung, wie sie oben vorgestellt wurde, hat den Vorteil, dass erst eine Zehnerstelle ermittelt wird, bevor die nächste bearbeitet wird. Sie ist jedoch etwas langsamer als die exakte Halbierung der Intervalle.
3. Die gewichtete Teilung ist wesentlich schneller. Hier wird nicht nur die binäre Entscheidung "größer oder kleiner als Null" getroffen, sondern die Beträge werden mit berücksichtigt. Im obigen Beispiel hieße das: Da f(0,9) = 0,02826 wesentlich näher an der Null ist als f(0,8) = -0,17948, wird als nächste Intevallteilung nicht x=0,85, sondern x=0,88 oder 0,89 gewählt. Auf dieser Idee beruht das oft verwendete Sekanten-Verfahren (Regula Falsi).

Vorteile und Nachteile

Der große Vorteil des Verfahrens sind die geringen Anforderungen an die Funktion: sie muss nur stetig sein. Ferner konvergiert es immer. Allerdings funktioniert es nicht mehr bei mehrdimensionalen Funktionen. Außerdem ist die Konvergenzgeschwindigkeit nur linear. Deswegen ist das Newton-Verfahren meist die bessere Wahl. Jenes konvergiert quadratisch dafür allerdings nicht immer.

Beweis des Zwischenwertsatzes

Es bietet sich an, den Beweis des Zwischenwertsatzes als Anwendungsbeispiel der Intervallschachtelung zu führen.

Behauptung:
Ist f: R ? R in einem abgeschlossenen Intervall [a₀, b₀] stetig und gilt

f(a₀) · f(b₀) < 0

(das ist gleichbedeutend damit, dass einer der beiden Funktionswerte positiv und der andere negativ ist), dann existiert eine reelle Zahl x im offenen Intervall (a₀, b₀), so dass f(x) = 0, also eine Nullstelle von f.

Beweis:
Wir betrachten den Fall, dass f(a₀) < 0 und f(b₀) > 0. Den anderen Fall beweist man analog.

Wir führen die Intervallschachtelung mit fortgesetzter Halbierung unendlich oft durch, es sei denn, wir stoßen vorher schon auf eine Nullstelle, womit der Beweis ebenfalls erbracht wäre.

Die dadurch erhaltenen Intervalle [a_n, b_n] haben folgende Eigenschaften:

• Die unteren Intervallgrenzen a_n bilden eine monoton wachsende Folge reeller Zahlen:
  a_n ? a_n-1.
• Die oberen Intervallgrenzen b_n bilden eine monoton fallende Folge reeller Zahlen:
  b_n ? b_n-1.
• Jede untere Intervallgrenze ist kleiner als die entsprechende obere Intervallgrenze:
  a_n < b_n,
  die beiden Folgen sind also beschränkt.
• Die Voraussetzung für den jeweils nächsten Schachtelungsschritt ist erfüllt:
  f(a_n) < 0, f(b_n) > 0.

Da der Raum der reellen Zahlen vollständig ist, folgt daraus:

• Beide Folgen (a_n) und (b_n) konvergieren gegen eine reelle Zahl a bzw. b.

Die Intervall-Länge halbiert sich in jedem Schritt, so dass außerdem gilt:

• b_n - a_n konvergiert gegen 0, die beiden Grenzwerte sind also gleich: a = b =: x.

Aufgrund der Konstruktion der Intervallgrenzen und der der Stetigkeit von f folgt schließlich:

• f(a) ? 0, f(b) ? 0, und damit f(x) = 0.

Der gemeinsame Grenzwert x ist also eine Nullstelle von f.
Q.E.D.