Robert Sedgewick: Algorithmen

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


39. Integration



Einfache Quadraturverfahren

Das vielleicht offensichtlichste Verfahren zur Approximation eines Integrals ist die Rechteckmethode. Die Berechnung eines Integrals entspricht der Ermittlung der Fläche unter einer Kurve, und wir können die Fläche unter einer Kurve schätzen, indem wir die Flächen kleiner Rechtecke addieren, die die Fläche unter der Kurve annähernd ausfüllen, wie es in Abbildung 39.1 schematisch dargestellt ist.

Abbildung 39.1
Abbildung 39.1 Rechteckregel.

Um dies exakt zu formulieren, nehmen wir an, daß wir Integral a->b f(x) dx berechnen wollen, und daß das Intervall [a, b], über dem das Integral berechnet werden soll, in N Teile zerlegt wird, die durch die Punkte x1, x2,..., xN+1 begrenzt werden. Dann liegen N Rechtecke vor, wobei die Breite des i-ten Rechtecks (1 <= i <= N) durch xi+1 - xi gegeben ist. Als Höhe des i-ten Rechtecks könnten wir f(xi) oder f(xi+1) benutzen, doch es ist zu erwarten, daß man ein genaueres Ergebnis erhält, wenn, wie in der obigen Skizze, der Wert von f im Mittelpunkt des Intervalls (f((xi+xi+1)/2)) verwendet wird. Dies führt zu der Quadraturformel

Formel

die eine Abschätzung für den Wert des Integrals von f(x) über dem Intervall von a = x1 bis b = xN+1 darstellt. In dem üblicherweise vorliegenden Fall, daß alle Intervalle die gleiche Länge haben, etwa xi+1 - xi = w, gilt xi+1 + xi = 2a + (2i-1)w, so daß die Näherung r für das Integral leicht berechnet werden kann:

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

Natürlich wird das Ergebnis genauer, wenn man N vergrößert. Abbildung 39.2 zeigt das Ergebnis der Verwendung einer kleineren Intervallänge für die in Abbildung 39.1 dargestellte Funktion.

Abbildung 39.2
Abbildung 39.2 Rechteckregel bei einer kleinen Intervallänge.

Nachfolgend geben wir ein eher quantitatives Beispiel an, das die mit Hilfe dieser Funktion für das Integral Integral 1->2 dx/x (das den bekannten Wert ln 2 = 0,6931471805599... besitzt) berechneten Näherungen zeigt, wenn die Funktion mit dem Aufruf intrect (1.0, 2.0, N) für N = 10, 100, 1000 aufgerufen wird:

10 0.6928353604100
100 0.6931440556283
1000 0.6931471493100

Für N = 1000 ist unser Ergebnis auf ungefähr sieben Dezimalstellen genau. Bei Verwendung anspruchsvollerer Quadraturmethoden kann mit wesentlich weniger Aufwand eine höhere Genauigkeit erzielt werden.

Es zeigt sich, daß sich aus der Betrachtung von Fehlerabschätzungen für spezielle Methoden oft Ideen für genauere Verfahren ergeben können. Wir betrachten den analytischen Ausdruck für den bei der Rechteckmethode entstehenden Fehler, indem wir f(x) im Mittelpunkt jedes Intervalls in eine Taylor-Reihe entwickeln, integrieren und dann die Summe über alle Intervalle bilden. Wir wollen nicht auf die Einzelheiten dieser Rechnung eingehen, sondern nur angeben, daß

 Integral a->b f(x) dx = r + w3e3 + w5e5 + ...

gilt, wobei w die Intervallänge ist ((b - a)/N) und e3 vom Wert der dritten Ableitung von f in den Mittelpunkten der Intervalle abhängt usw. (Dies ist normalerweise eine gute Näherung, da die meisten »vernünftigen« Funktionen kleine Ableitungen höherer Ordnung haben, obwohl das nicht immer zutrifft.) Wenn wir zum Beispiel die Punkte so wählen, daß w = 0,01 gilt (was im obigen Beispiel der Wahl von N = 100 entsprechen würde), so sagt diese Formel aus, daß das bei Anwendung der obigen Prozedur berechnete Integral auf ungefähr sechs Dezimalstellen genau sein dürfte.

Abbildung 39.3
Abbildung 39.3 Trapezregel.

Ein anderer Weg, das Integral zu approximieren, besteht in der Zerlegung der Fläche unter der Kurve in Trapeze, wie dies in Abbildung 39.3 schematisch dargestellt ist. Wir erinnern daran, daß die Fläche eines Trapezes gleich der Hälfte des Produkts der Höhe und der Summe der Längen der beiden parallelen Seiten ist. Die Trapezmethode führt zu der Quadraturformel

Formel

Die folgende Prozedur ist eine Implementation der Trapezmethode für den für gewöhnlich vorliegenden Fall, daß alle Intervalle die gleiche Länge haben:

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

Der Fehler dieses Verfahrens kann in ähnlicher Weise hergeleitet werden wie für die Rechteckmethode. Es zeigt sich, daß

 Integral a->b f(x) dx = t - 2w3e3 - 4w5e5 + ...

gilt. Folglich ist die Rechteckmethode doppelt so genau wie die Trapezmethode. Dies bestätigt sich auch an unserem Beispiel; mit der Trapezmethode erhalten wir die folgenden Näherungen für Integral 1->2 dx/x:

10 0.6937714031754
100 0.6931534304818
1000 0.6931472430599

Es mag zunächst überraschend sein, daß die Rechteckmethode genauer als die Trapezmethode ist. Man muß jedoch berücksichtigen, daß die Rechtecke die Tendenz aufweisen, teils unterhalb und teils oberhalb der Kurve zu liegen (so daß ein Ausgleich des Fehlers innerhalb eines Intervalls möglich ist), während bei den Trapezen die Tendenz besteht, daß ihre obere Seite entweder vollständig unter oder vollständig über der Kurve liegt. Abbildung 39.4 zeigt die Trapezmethode mit einer kleineren Intervallänge; dem Anschein nach erfolgt eine exakte Anpassung an die Kurve, doch Abbildung 39.2 ergibt in Wirklichkeit eine bessere Schätzung für die Fläche unter der Kurve.

Abbildung 39.4
Abbildung 39.4 Trapezregel bei einer kleinen Intervallänge.

Ein weiteres durchaus sinnvolles Verfahren ist die Quadratur mit Hilfe von Splines: Unter Benutzung der im vorangegangenen Kapitel betrachteten Verfahren wird eine Interpolation mit Hilfe von Splines durchgeführt, und danach wird das Integral durch schrittweise Anwendung der oben beschriebenen einfachen Methode der symbolischen Integration von Polynomen berechnet. Wie wir weiter unten sehen werden, steht diese Methode in Wirklichkeit in enger Beziehung zur Rechteckregel und zur Trapezregel.


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