Intervallschachtelung
Die Intervallschachtelung ist ein universell einsetzbares iteratives Lö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.
Table of contents |
2 Beispiel 3 Strategien 4 Beweis des Zwischenwertsatzes |
Bei der Suche nach den Nullstellen einer stetigen Funktion f kann man so vorgehen:
Es bietet sich an, den Beweis des Zwischenwertsatzes als Anwendungsbeispiel der Intervallschachtelung zu führen.
Behauptung:
Beweis:
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 [an, bn] haben folgende Eigenschaften:
Nullstellensuche bei einer stetigen Funktion
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 Nullstelle der Funktion
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].
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
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 Binärsystem die bevorzugte Wahl, da sie der dortigen Bruchdarstellung entspricht.
Beweis des Zwischenwertsatzes
Ist f: R ? R in einem abgeschlossenen Intervall [a0, b0] stetig und gilt
(das ist gleichbedeutend damit, dass einer der beiden Funktionswerte positiv und der andere negativ ist), dann existiert eine reelle Zahl x im offenen Intervall (a0, b0), so dass f(x) = 0, also eine Nullstelle von f.
Wir betrachten den Fall, dass f(a0) < 0 und f(b0) > 0. Den anderen Fall beweist man analog.
Da der Raum der reellen Zahlen vollständig ist, folgt daraus:
an ? an-1.
bn ? bn-1.
an < bn,
die beiden Folgen sind also beschränkt.
f(an) < 0, f(bn) > 0.
Die Intervall-Länge halbiert sich in jedem Schritt, so dass außerdem gilt:
Aufgrund der Konstruktion der Intervallgrenzen und der der Stetigkeit von f folgt schließlich:
Der gemeinsame Grenzwert x ist also eine Nullstelle von f.
Q.E.D