Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenSonntag, 23. November 2014 

Intervallschachtelung


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.
Die Intervallschachtelung ist ein universell einsetzbares iteratives Lösungsverfahren der Mathematik . Idee des Verfahrens ist dass sich Lösung einer Gleichung oft nicht unmittelbar berechnen dass sich aber sehr wohl ein Intervall finden lässt das die Lösung enthält man die richtige Grundmenge zugrunde legt. Durch Verkleinerung dieses Intervalls findet man beliebig genaue der Lösung.

Inhaltsverzeichnis

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 z.B. die Funktion an einigen ganzzahligen Stellen
  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 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 [ c b ] eine Nullstelle (es können jedoch auch Intervalle Nullstellen enthalten das Verfahren kann aber eine finden). Im Fall dass f ( c ) = 0 ist endet natürlich das mit der gefundenen Nullstelle c .
  5. Man fährt fort das gefundene Intervall zu verkleinern bis man eine Nullstelle direkt oder bis die Intervall-Länge klein genug ist man die Randpunkte als geeignete Näherungen betrachten wenn also die Intervallschachtelung nicht bei einem Dezimalbruch endet bricht man sie bei Erreichen gewünschten Genauigkeit ab.

Bricht man die Intervallschachtelung nicht ab verkleinert die Intervalle immer weiter dann erhält beim Grenzübergang genau eine Zahl die in allen 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² - 9256x - 0 2646 .

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

Wird nun f(0 5) = 0 5³+0 5²-0 9256·0 5-0 2646=-0 4799 < 0 so ergibt sich das Intervall [0 5;1] hier der Vorzeichenwechsel stattfindet.
Aus f(0 8) = 0 8³+0 49·0 9256·0 8-0 2646 = -0 17948 < ergibt sich das Intervall [0 8;1]
aus f(0 9) = 0 9³+0 49·0 9256·0 9-0 2646 = +0 02826 > ergibt sodann sich das Intervall [0 8;0
Da die Nullstelle zwischen 0 8 0 9 liegt wird nach dem gleichen die zweite Nachkommastelle ermittelt. So wird die x =0 88 gefunden. Die beiden anderen lassen 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 Nachkommastellen und ist somit in der Regel Dagegen ist sie im Binärsystem die bevorzugte Wahl da sie der Bruchdarstellung entspricht.
  2. Die annähernde Halbierung wie sie oben vorgestellt wurde hat Vorteil dass erst eine Zehnerstelle ermittelt wird die nächste bearbeitet wird. Sie ist jedoch langsamer als die exakte Halbierung der Intervalle.
  3. Die gewichtete Teilung ist wesentlich schneller. Hier wird nicht die binäre Entscheidung "größer oder kleiner als getroffen sondern die Beträge werden mit berücksichtigt. Im obigen Beispiel das: Da f(0 9) = 0 02826 näher an der Null ist als f(0 = -0 17948 wird als nächste Intevallteilung x =0 85 sondern x =0 88 oder 0 89 gewählt. Auf Idee beruht das oft verwendete Sekanten-Verfahren ( Regula Falsi ).

Beweis des Zwischenwertsatzes

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

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

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

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

Wir führen die Intervallschachtelung mit fortgesetzter unendlich oft durch es sei denn wir vorher schon auf eine Nullstelle womit der 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
    a n a n-1 .
  • Die oberen Intervallgrenzen b n bilden eine monoton fallende Folge reeller
    b n b n-1 .
  • Jede untere Intervallgrenze ist kleiner als entsprechende obere Intervallgrenze:
    a n < b n
    die beiden Folgen sind also beschränkt.
  • Die Voraussetzung für den jeweils nächsten 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 so dass außerdem gilt:

  • b n - a n konvergiert gegen 0 die beiden Grenzwerte also gleich: a = b =: x .

Aufgrund der Konstruktion der Intervallgrenzen und 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.



Bücher zum Thema Intervallschachtelung

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Intervallschachtelung.html">Intervallschachtelung </a>