Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


39. Integration



Zusammengesetzte Verfahren

Die Betrachtung der oben für den Fehler der Rechteckmethode und der Trapezmethode angegebenen Formeln führt zu einem einfachen Verfahren, das sich als wesentlich genauer erweist und als Simpson-Methode bezeichnet wird. Die Grundidee besteht darin, durch eine Kombination der beiden Methoden das erste Glied im Ausdruck für den Fehler zu beseitigen. Wenn man die Formel für die Rechteckmethode mit zwei multipliziert, die Formel für die Trapezmethode hinzuaddiert und anschließend durch drei dividiert, ergibt sich die Gleichung

 Integral a->b f(x) dx = (2r + t - 2w5e5 + ...)/3.

Das Glied mit w3 ist verschwunden, so daß diese Formel besagt, daß wir ein bis auf einen Fehler von der Ordnung w5 genaues Verfahren erhalten können, indem wir die Quadraturformeln in der gleichen Weise kombinieren:

Formel

Wenn für die Simpson-Regel eine Intervallänge von 0,01 benutzt wird, kann das Integral bis auf etwa zehn Dezimalstellen genau berechnet werden. Auch dies wird in unserem Beispiel sichtbar. Die Implementation der Simpson-Methode ist nur wenig komplizierter als die anderen (wir betrachten wieder den Fall, daß die Intervalle die gleiche Länge haben):

    function intsimp(a,b: real; N: integer): real;
      var i: integer; w,s: real;
      begin
      s:=0; w:=(b-a)/N;
      for i:=1 to N do
        s:=s+w*(f(a+(i-1)*w)+4*f(a-w/2+i*w)+f(a+i*w))/6;
      intsimp:=s;
      end;

Dieses Programm erfordert drei Berechnungen von Funktionswerten (anstelle von zwei) in der inneren Schleife, doch es liefert bedeutend genauere Ergebnisse als die vorangegangenen beiden Methoden:

10 0.6931473746651
100 0.6931471805795
1000 0.6931471805599

Es sind kompliziertere Quadraturmethoden entwickelt worden, deren erhöhte Genauigkeit durch Kombination einfacherer Methoden mit ähnlichen Fehlern erzielt wird. Die bekannteste von ihnen ist die Romberg-Integration, die zwei verschiedene Mengen von Teilintervallen für ihre beiden »Methoden« benutzt.

Es erweist sich, daß die Simpson-Methode exakt Interpolation der Daten mit Hilfe einer stückweise quadratischen Funktion und anschließenden Integration entspricht. Es ist interessant festzustellen, daß alle vier von uns betrachteten Methoden als Methoden der stückweisen Interpolation aufgefaßt werden können: Die Rechteckregel entspricht der Interpolation mittels einer Konstanten (Polynom vom Grad null), die Trapezregel der Interpolation mittels einer Geraden (Polynom vom Grad eins), die Simpson-Regel der Interpolation durch ein quadratisches Polynom und die Quadratur mit Hilfe von Splines der Interpolation durch ein kubisches Polynom.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]