Intervallschachtelung

Bei der Bestimmung der Lösung einer Gleichung mittels Intervallschachtelung wird das Intervall so verkleinert, dass die Nullstelle der entsprechenden Funktion in dem verkleinerten Intervall liegt.
Das Verfahren der schrittweisen Annäherung an die Lösung einer Gleichung gehört zu den Iterationsverfahren.
Von einem Iterationsverfahren spricht man, wenn man aus einer Näherungslösung durch Anwendung eines Algorithmus zu einer besseren Näherungslösung und letztlich die Lösung prinzipiell beliebig gut an die exakte Lösung heranführen kann. Man sagt dann, dass die Iteration konvergiert.

Grundgedanke der Näherungsverfahren zum Bestimmen der Lösungen von Gleichungen ist, die Gleichung in eine Funktion umzuwandeln, sodass die Variable der Gleichung als Veränderliche der Funktion erscheint. Es werden dann die Nullstellen dieser Funktion gesucht. Statt der Gleichung p(x) = 0 wird die Funktion f(x) = p(x) betrachtet.
Dabei muss die Funktion folgende Bedingungen erfüllen:

1. Der Graph der Funktion kann über dem Intervall in einem Zug gezeichnet werden (stetig).
2. Die Funktionswerte am Anfang und am Ende des Intervalls haben unterschiedliche Vorzeichen.

Bei der Intervallschachtelung wird das Intervall so verkleinert, dass die Nullstelle danach in dem verkleinerten Intervall liegt. Dieses Vorgehen wird wiederholt, bis das Intervall so klein ist, dass ein Wert aus dem Intervall als hinreichend genaue Näherung für die Nullstelle betrachtet werden kann.
Das Verkleinern das Intervalls erfolgt am bequemsten und schnellsten durch Halbieren. Diese spezielle Vorgehensweise wird Intervallhalbierungsmethode (Bisektionsmethode, Bild 2) genannt.

Das Intervall $\left[{\text{x}}_{\text{1}}\text{;}{\text{x}}_{\text{2}}\right]$ wird halbiert.
Die neuen Intervalle $\left[{\text{x}}_{\text{1}}\text{;}{\text{ x}}_{\text{3}}\right]\text{und}\left[{\text{x}}_{\text{3}}\text{;}{\text{ x}}_{\text{2}}\right]$ werden betrachtet.
Wegen des Vorzeichenwechsels im Intervall $\left[{\text{x}}_{\text{1}}{\text{; x}}_{\text{3}}\right]$ wird dieses Intervall für die Fortsetzung ausgewählt.
Für die Beendigung dieses Verfahrens muss eine Abbruchbedingung (eine Genauigkeitsforderung) angegeben werden.

Das algorithmische Vorgehen zeigt das folgende Struktogramm:

Struktogramm der Intervallhalbierungsmethode