Robert Sedgewick: Algorithmen

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


39. Integration



Adaptive Quadratur

Ein größerer Mangel der bisher betrachteten Methoden besteht darin, daß die entstehenden Fehler nicht nur von der verwendeten Länge der Teilintervalle abhängen, sondern auch vom Wert der Ableitungen höherer Ordnung der zu integrierenden Funktion. Das hat zur Folge, daß diese Verfahren für gewisse Funktionen (solche mit großen Ableitungen höherer Ordnung) ganz und gar nicht geeignet sind. Doch wenige Funktionen haben überall große Ableitungen höherer Ordnung. Es ist sinnvoll, kleine Intervalle zu benutzen, wenn die Ableitungen groß sind, und große Intervalle, wenn die Ableitungen klein sind. Ein Verfahren, welches dies auf eine systematische Weise realisiert, wird ein Verfahren der adaptiven Quadratur genannt.

Der allgemeine Ansatz bei einer adaptiven Quadratur besteht darin, für jedes Teilintervall zwei verschiedene Quadraturmethoden anzuwenden, die Ergebnisse zu vergleichen und das Intervall weiter zu unterteilen, wenn die Differenz zu groß ist. Natürlich ist dabei eine gewisse Sorgfalt erforderlich, da bei Verwendung von zwei gleichermaßen ungeeigneten Methoden diese recht gut übereinstimmende, doch schlechte Ergebnisse liefern könnten. Dies kann vermieden werden, indem man sicherstellt, daß die eine Methode das Ergebnis stets unterschätzt, die andere hingegen es stets überschätzt. Eine andere Möglichkeit ist, dafür Sorge zu tragen, daß die eine Methode genauer ist als die andere. Ein Verfahren dieses letzteren Typs wird nachfolgend beschrieben.

Die rekursive Unterteilung des Intervalls ist mit einem beträchtlichen zusätzlichen Aufwand verbunden, so daß es sich lohnt, wie in der folgenden Implementation, ein gutes Verfahren für die Schätzung der Integrale zu benutzen:

    function adapt(a,b: real): real;
      begin
      if abs(intsimp(a,b,10)-intsimp(a,b,5))<tolerance
        then adapt:=intsimp(a,b,10)
        else adapt:=adapt(a,(a+b)/2) + adapt((a+b)/2,b);
      end;

Beide Näherungen für das Integral werden von der Simpson-Methode abgeleitet, wobei für die eine jedoch doppelt so viele Teilintervalle wie für die andere benutzt werden. Im wesentlichen bedeutet das, daß die Genauigkeit der Simpson-Methode für das betreffende Intervall geprüft wird und, wenn sie nicht ausreichend ist, weiter unterteilt wird.

Im Unterschied zu unseren anderen Methoden, bei denen wir entscheiden, wieviel Aufwand wir treiben wollen, und dann die Ergebnisse unabhängig von ihrer Genauigkeit akzeptieren, treiben wir bei einer adaptiven Quadratur so viel Aufwand, wie erforderlich ist, um die im voraus festgelegte Genauigkeit zu erreichen. Das bedeutet, daß die Variable tolerance sorgfältig gewählt werden muß, damit im Programm nicht unendlich oft die Schleife durchlaufen wird, um eine unerreichbar hohe Genauigkeit zu erzielen. Die Anzahl der erforderlichen Schritte hängt sehr stark von der Art der zu integrierenden Funktion ab. Eine Funktion, die heftige Schwankungen aufweist, erfordert eine große Anzahl von Schritten, doch eine solche Funktion würde auch bei den Methoden mit »festen Intervallängen« zu einem sehr ungenauen Ergebnis führen. Abbildung 39.5 zeigt die Punkte, die berechnet werden, wenn eine adaptive Quadratur (beruhend auf der Trapezregel) auf die Funktion in den Abbildungen 39.1 - 39.4 angewandt wird. Wir bemerken, daß die Intervalle dort größer sind, wo die Funktion gerade und glatt verläuft, und kleiner, wo die Funktion stärker gekrümmt ist.

Abbildung 39.5
Abbildung 39.5 Adaptive Quadratur.

Eine glatte Funktion wie die in unserem Beispiel kann mit einer vertretbaren Anzahl von Schritten verarbeitet werden. In der nachfolgenden Tabelle sind für verschiedene Werte von tolerance der berechnete Wert des Integrals und die Anzahl der für das obige Programm zur Berechnung von Integral 1->2 dx/x benötigten rekursiven Aufrufe angegeben:

0,00001000000 0,6931473746651 1
0,00000010000 0,6931471829695 5
0,00000000100 0,6931471806413 13
0,00000000001 0,6931471805623 33

Das obige Programm kann auf verschiedene Arten verbessert werden. Erstens ist es sicher nicht notwendig, intsimp (a, b, 10) zweimal aufzurufen. Tatsächlich können die Funktionswerte dieses Aufrufs von intsimp (a, b, 5) mit genutzt werden. Zweitens kann die Schranke für die Toleranz besser zur Genauigkeit des Ergebnisses in Beziehung gesetzt werden, wenn tolerance über das Verhältnis der Länge des aktuellen Intervalls zur Länge des Gesamtintervalls ausgedrückt wird. Weiterhin kann offensichtlich ein besseres Programm entwickelt werden, indem eine bessere Quadraturformel als die Simpson-Regel benutzt wird (wobei es jedoch ein grundlegendes Gesetz der Rekursion ist, daß eine andere adaptive Routine keine gute Idee wäre). Ein kompliziertes Programm der adaptiven Quadratur kann für Probleme, die auf andere Weise nicht bearbeitet werden können, sehr genaue Ergebnisse liefern. Dabei ist jedoch den Typen der verarbeiteten Funktionen größte Aufmerksamkeit zu widmen.

Das Schema »Teile und Herrsche« für die Entwicklung von Algorithmen ist somit auch für numerische Programme von Nutzen. Tatsächlich haben adaptive Verfahren dieser Art eine große Bedeutung als Lösungsmethoden für schwierigere numerische Probleme, wie die Integration in höheren Dimensionen und die numerische Lösung von Differentialgleichungen.


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