Adaptive Quadratur

Die adaptive Quadratur unterteilt das Integrationsintervall automatisch dort, wo der Integrand schwierig ist, und verwendet lokale Fehlerschätzungen, um eine angeforderte Genauigkeit mit möglichst wenigen Funktionsauswertungen zu erreichen.

Definition

Adaptive Quadratur ist jede numerische Integrationsstrategie, die Schätzungen des lokalen Approximationsfehlers verwendet, um zu entscheiden, wo und wie fein der Integrationsbereich unterteilt werden soll, damit eine vorgegebene Gesamtfehlertoleranz effizient erreicht wird.

Scope

Dieses Thema behandelt die lokale Fehlerschätzung durch den Vergleich von Regeln unterschiedlicher Ordnung oder Verfeinerungsgrade, die rekursive Intervallhalbierung (adaptive Simpson- und adaptive Gauss-Kronrod-Quadratur), globale Fehlerbudgets und Abbruchkriterien, den Umgang mit Singularitäten und scharfen Merkmalen sowie das Design von automatischen Produktionsintegratoren, wie sie in der QUADPACK-Bibliothek zu finden sind.

Core questions

• Wie wird der lokale Fehler einer Quadratur-Schätzung berechnet, ohne das exakte Integral zu kennen?
• Wie konzentriert die rekursive Unterteilung den Aufwand dort, wo der Integrand am stärksten variiert?
• Welche Abbruchkriterien erreichen zuverlässig die angeforderte Toleranz und vermeiden gleichzeitig unnötige Arbeit?
• Wie werden integrierbare Singularitäten und Diskontinuitäten robust erkannt und behandelt?

Key theories

Lokale Fehlerschätzung und Unterteilung

Der Vergleich einer groben und einer feineren (oder höherwertigen) Schätzung auf einem Teilintervall liefert eine Schätzung des lokalen Fehlers; überschreitet dieser den dem Teilintervall zugewiesenen Anteil der Toleranz, wird das Teilintervall geteilt und das Verfahren rekursiert, andernfalls wird sein Beitrag akzeptiert.

Global adaptive Strategien

Anstatt Teilintervalle unabhängig voneinander zu behandeln, führen global adaptive Integratoren eine Warteschlange von Teilintervallen, die nach dem geschätzten Fehler geordnet sind, und verfeinern immer das schlechteste, was lokalisierte Singularitäten effizient handhabt und den QUADPACK-Routinen zugrunde liegt.

Mechanisms

Auf jedem Teilintervall wertet der Integrator ein eingebettetes Regelpaar aus – zum Beispiel ein Gauss-Kronrod-Paar oder zwei Simpson-Schätzungen bei unterschiedlichen Verfeinerungen –, dessen Differenz den lokalen Fehler schätzt. Eine lokal adaptive Methode rekursiert, indem sie jedes Teilintervall halbiert, dessen geschätzter Fehler zu groß ist. Eine global adaptive Methode verwaltet eine Prioritätswarteschlange von Teilintervallen, die nach dem geschätzten Fehler geordnet sind, und unterteilt den aktuell schlechtesten Verursacher wiederholt, bis die summierte Fehlerschätzung die Toleranz erfüllt. Extrapolation und spezialisierte Gewichtshandhabung werden hinzugefügt, um Endpunktsingularitäten und oszillierende Integranden zu bewältigen.

Clinical relevance

Adaptive Quadratur ist das, worauf allgemeine Integrationsroutinen in wissenschaftlicher Software angewiesen sind, um ein Ergebnis mit einer vom Benutzer angegebenen Genauigkeit zu liefern, ohne dass der Benutzer den Integranden analysieren muss; sie ist unerlässlich für Integranden mit Spitzen, Grenzschichtverhalten oder integrierbaren Singularitäten, die eine feste Regel überwinden würden, und sie liegt den automatischen Integratoren in weit verbreiteten numerischen und statistischen Paketen zugrunde.

History

Die automatische, fehlerkontrollierte Integration reifte in den 1970er und frühen 1980er Jahren und gipfelte im QUADPACK-Paket (1983), dessen adaptive Gauss-Kronrod-Routinen mit Extrapolation zum De-facto-Standard wurden und später in vielen numerischen und statistischen Softwaresystemen übernommen, portiert oder neu implementiert wurden.

Key figures

• Robert Piessens
• Philip J. Davis
• Philip Rabinowitz

Seminal works

• davis1984
• piessens1983

Frequently asked questions

Wie kennt ein adaptiver Integrator den Fehler, wenn er die Antwort nicht kennt?

Er schätzt den lokalen Fehler, indem er zwei Approximationen unterschiedlicher Genauigkeit auf demselben Teilintervall vergleicht – zum Beispiel eine höher- und eine niederwertige Regel. Ihre Differenz approximiert den Fehler und leitet an, wo verfeinert werden soll, auch wenn das wahre Integral unbekannt ist.

Wann stößt die adaptive Quadratur an ihre Grenzen?

Sie kann durch Integranden in die Irre geführt werden, die an den Abtastpunkten glatt sind, aber versteckte Merkmale dazwischen aufweisen, durch stark oszillierende Integranden oder durch nicht integrierbare Singularitäten. Dann sind spezialisierte Regeln, Transformationen oder Methoden zur oszillierenden Integration erforderlich.