Intervallschachtelung

Die Intervallschachtelung ist ein universell einsetzbares iteratives Lösungsverfahren der Mathematik. Idee des Verfahrens ist, dass sich eine Lösung 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. Bei der Nullstellensuche von stetigen Funktionen ist das sicher der Fall, wenn der Funktionswert der einen Intervallgrenze das entgegengesetzte Vorzeichen des Funktionswertes der anderen Intervallgrenze hat. Das Verfahren schreitet voran, indem das jeweils gefundene Intervall in zwei Teile geteilt wird und durch berechnen der Probe dasjenige Teilintervall bestimmt wird, das die gesuchte Lösung enthält.

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 durch Polynomdivision und anschließende Quadratische Ergänzung ermitteln.

Wenn die Intervallschachtelung nicht bei einem glatten Dezimalbruch endet, ist sie bei Erreichen der gewünschten Genauigkeit abzubrechen.

Strategien

Die fortgesetzte Halbierung der Intervalle führt sehr schnell im Dezimalsystem zu Brüchen mit sehr vielen Nachkommastellen und ist somit in der Regel ungeeignet. Dagegen ist sie im Binärsystem die bevorzugte Wahl, da sie der dortigen Bruchdarstellung entspricht.
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 dennoch relativ langsam.
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).