Methodenauswahl für numerische Quadratur

12

Für die numerische Quadratur gibt es mehrere Methodenfamilien. Wenn ich eine bestimmte Klasse von Integranden habe, wie wähle ich die ideale Methode aus?

Was sind die relevanten Fragen, die sowohl zum Integranden (z. B. ist er glatt? Hat er Singularitäten?) Als auch zum Rechenproblem (z. B. Fehlertoleranz, Rechenbudget) gestellt werden müssen?

Wie können Antworten auf diese Fragen die verschiedenen Methodenfamilien ausschließen oder fördern? Der Einfachheit halber betrachten wir nur einzelne oder niedrig dimensionale Integrale.

In dem Wikipedia-Artikel zu QUADPACK heißt es beispielsweise, dass die relativ allgemeine QAGSRoutine " globale adaptive Quadratur basierend auf der 21-Punkte-Gauß-Kronrod-Quadratur in jedem Teilintervall mit Beschleunigung durch den Epsilon-Algorithmus von Peter Wynn " verwendet.

Wie wurde diese Entscheidung getroffen? Wie kann man ähnliche Entscheidungen treffen, wenn mehr bekannt ist?

MRocklin
quelle
1
Möglicherweise sind spezifischere Informationen erforderlich, um dies richtig zu beantworten. Es gibt kein Einheitskriterium, die Gaußsche Quadratur eignet sich häufig für sehr glatte Probleme, während andere Quadraturen bei milden Singularitäten verwendet werden können. Wenn Sie jedoch in regelmäßigen Abständen auftreten, kann es sein, dass ein einfaches Trapez es schneidet.
Reid.Atcheson
2
@ Reid.Atcheson, ich glaube, du beantwortest die Frage gerade. Ich frage nicht, was die beste Methode ist, ich frage, welche Art von Fragen würden Sie stellen und was würden Ihnen diese Antworten sagen? Wie geht man generell mit solchen Problemen um?
MRocklin

Antworten:

11

Zunächst müssen Sie sich die Frage stellen, ob Sie eine Allround-Quadraturroutine benötigen, die einen Integranden als Black Box verwenden soll. Wenn ja, können Sie sich für eine adaptive Quadratur entscheiden, bei der Sie hoffen, dass die Adaptivität "schwierige" Stellen im Integranden erfasst. Und das ist einer der Gründe, warum Piessens et al. wählte für eine Gauß-Kronrod-Regel (diese Art von Regel ermöglicht es Ihnen, eine Approximation des Integrals und eine Schätzung des Approximationsfehlers unter Verwendung derselben Funktionsbewertungen zu berechnen) von bescheidener Ordnung, angewendet in einem adaptiven Schema (mit Unterteilung des Intervalls mit der höchster Fehler), bis die erforderlichen Toleranzen erreicht sind. Der Wynn-Epsilon-Algorithmus ermöglicht die Bereitstellung einer Konvergenzbeschleunigung und hilft normalerweise in Fällen, in denen Endpunkt-Singularitäten vorliegen.

Wenn Sie jedoch die "Form" oder "Art" Ihres Integranden kennen, können Sie Ihre Methode an Ihre Bedürfnisse anpassen, sodass der Rechenaufwand für die von Ihnen benötigte Genauigkeit begrenzt ist. Also, was müssen Sie sich anschauen:

Integrand:

  • Glätte: Kann sie durch ein Polynom aus einer orthogonalen Polynomfamilie angenähert werden (in diesem Fall ist die Gaußsche Quadratur gut geeignet)?
  • Singularitäten: Kann das Integral in Integrale mit nur Endpunkt-Singularitäten aufgeteilt werden (wenn dies der Fall ist, ist die IMT-Regel oder die doppelt exponentielle Quadratur für jedes Unterintervall gut)
  • Rechenaufwand für die Auswertung?
  • Kann der Integrand berechnet werden? Oder sind nur begrenzte punktuelle Daten verfügbar?
  • Hochoszillatorischer Integrand: Suchen Sie nach Methoden vom Levin-Typ.

|x-c|-αcα

Integrationsintervall: endlich, halb unendlich oder unendlich. Können sie bei semi-unendlichen oder unendlichen Intervallen durch eine variable Transformation auf ein endliches Intervall reduziert werden? Wenn nicht, können Laguerre- oder Hermite-Polynome im Gaußschen Quadratur-Ansatz verwendet werden.

Ich habe keine Referenz für ein echtes Flussdiagramm für Quadratur im Allgemeinen, aber das QUADPACK-Buch (nicht die Netlib-Hilfeseiten, sondern das echte Buch) enthält ein Flussdiagramm, mit dem Sie die entsprechende Routine basierend auf dem zu bewertenden Integral auswählen können. Das Buch beschreibt auch die Auswahl in Algorithmen von Piessens et al. für die verschiedenen Routinen.

Bei niedrigdimensionalen Integralen wird typischerweise eine verschachtelte eindimensionale Quadratur verwendet. Im Sonderfall der zweidimensionalen Integrale (Kubatur) existieren Integrationsregeln für verschiedene Fälle von Integrationsdomänen. R. Cools hat eine Vielzahl von Regeln in seiner Encyclopedia of Cubature Formulas gesammelt und ist der Hauptautor des Cubpack- Pakets. Für hochdimensionale Integrale greift man typischerweise auf Monte-Carlo-Methoden zurück. Man benötigt jedoch typischerweise eine sehr große Anzahl von Integrandenauswertungen, um eine angemessene Genauigkeit zu erhalten. Bei niedrigdimensionalen Integralen übertreffen Approximationsmethoden wie Quadratur / Kubatur / verschachtelte Quadratur häufig diese stochastischen Methoden.

Allgemeine interessante Referenzen:

  1. Quadpack, Piessens, Robert; de Doncker-Kapenga, Elise; Überhuber, Christoph W .; Kahaner, David (1983). QUADPACK: Ein Unterprogrammpaket für die automatische Integration. Springer-Verlag. ISBN 978-3-540-12553-2
  2. Methoden der numerischen Integration: Zweite Auflage, Ph. Davis und Ph. Rabinowitz, 2007, Dover Books on Mathematics, ISBN 978-0486453392
GertVdE
quelle
1
Nette antwort Warum hätte sich QUADPACK insbesondere für die 21-Punkte-Gauß-Kronrod-Methode entschieden? Warum die magische Zahl?
MRocklin
@MRocklin: Ich denke, es war ein guter Kompromiss zwischen Genauigkeit und Effizienz: Sie möchten Ihre Quadraturregel nicht übersteuern (teuer), aber Sie möchten auch nicht, dass sie zu schwach ist (zu viele Unterteilungen im adaptiven Teil) ). Um vollständig zu sein: In der QAG-Routine muss der Benutzer die Quadraturregel angeben; In der QAGS (mit Extrapolation) ist die Vorgabe die 21-Punkte-Regel, die jedoch mit der erweiterten Aufrufroutine QAGSE außer Kraft gesetzt werden kann.
GertVdE
1
@GertVdE Sehr nette Antwort in der Tat. Können Sie die Verwendung von Clenshaw-Curtis zur Erfassung von Singularitäten in der Mitte des Intervalls erläutern oder Referenzen bereitstellen? Ich habe noch nie gehört, dass es auf diese Weise verwendet wird, und konnte bei einem schnellen Googeln keine Details finden. Vielen Dank!
OscarB
3
@OscarB: sorry für die lange verzögerung, war ohne netzzugang (ah das gute leben). Siehe das Quadpack-Buch §2.2.3.3 und weiter; Branders, Piessens, "Eine Erweiterung der Clenshaw-Curtis-Quadratur", 1975, J.Comp.Appl.Math., 1, 55-65; Piessens, Branders, "Die Bewertung und Anwendung einiger veränderter Momente", 1973, BIT, 13, 443-450; Piessens, Branders, "Berechnung oszillierender Integrale", 1975, J.Comp.Appl.Math., 1, 153-164. Wenn Sie zwischen 1972 und 1980 nach "Robert Piessens" suchen, werden Sie viele interessante Artikel finden.
GertVdE