Wann ist es vorteilhaft, Integrale numerisch zu iterieren?

Wenn es ein -dimensionales Integral der Form $(n+1)$ normalerweise würde man dies unter Verwendung einer mehrdimensionalen Integrationsbibliothek über die gesamte Domäne bewerten.

\int_{[0, 1]^{n + 1}} f (x, y) d^{n} x d y,

$\int_{[0,1]^{n+1}} f(x, y)\,\mathrm{d}^n x \,\mathrm{d}y,$

[0, 1]^{n + 1}

$[0,1]^{n+1}$

Aber gibt es einige Bedingungen, unter denen es sinnvoll sein könnte, das Integral über separat unter Verwendung einer eindimensionalen Quadratur auszuführen und dann die mehrdimensionale Integrationsbibliothek zu verwenden, um den Integranden über die anderen Koordinaten auszuwerten ? $y$ $n$

\int_{[0, 1]^{n}} g (x) d^{n} x, g (x) = \int_{0}^{1} f (x, y) d y .

$\int_{[0,1]^n}g(x)\,\mathrm{d}^nx, \qquad g(x) = \int_0^1 f(x,y)\,\mathrm{d}y.$

Dies kann beispielsweise sinnvoll sein, wenn als Funktion von besonders glatt ist, nicht jedoch . Aber wie glatt muss es in diesem Fall genau sein? Meine Vermutung war, dass es fast nie Sinn macht, weil viel zu viele der 1-D-Quadratur-Bewertungspunkte "verschwendet" würden, aber ich bin mir nicht sicher, ob dies immer zutrifft. Wird dies durch das Design der hochdimensionalen Integrationsmethoden garantiert? $f$ $y$ $x$

In meinem Fall ist Black-Box, aber stückweise glatt in , und hat eine unbekannte Menge Knicke und Sprünge in an unbekannten Orten, und ist ziemlich hoch ( ), so dass das Integral über hat mit etwas speziell für viele Dimensionen gemacht werden. Das Integral über kann mit etwas Regelmäßigem wie gemacht werden . In diesem Beispiel ist die Funktion in so flüssig, dass sie fast zu funktionieren scheint, aber die wiederholte Integration ist 30-mal langsamer, sodass ich mich frage, ob der Ansatz falsch ist. $f$ $y$ $x$ $n$ $n\geq 4$ $x$ $y$ quadgk $y$

Wenn Sie wissen, wo dies bereits in der Literatur diskutiert wird, wäre dies ebenfalls hilfreich.

\int_{[0, 1]^{n}} e^{- x_{1} x_{2} \dots x_{n}} d^{n} x = F (\begin{matrix} {1, \dots, 1}_{n} \\ {2, \dots, 2}_{n} \end{matrix} | - 1) .

$\int_{[0,1]^n} e^{-x_1 x_2\cdots x_n}\,\mathrm{d}^n x = \mathrm{F}\left(\begin{array}{}\{1,\ldots,1\}_n\\\{2,\ldots,2\}_n\end{array}\middle| -1\right).$

n

$n$

(n - 1)

$(n-1)$

x_{1}

$x_1$

g (x_{2 : n}) = - (e^{- a} - 1) / a

$g(x_{2:n}) = -(e^{-a}-1)/a$

a = x_{2} \dots x_{n}

$a=x_2\cdots x_n$

$(n=5)$ $N$ $0.00244N^{-1}$ $0.00167N^{-1}$ $4$ $g$ $1.5$

$1.5$ $1.5$ $g = (1-e^{-a})/a$ $1.5$

$x$ $y$

numerical-analysis reference-request quadrature integration Kirill
quelle

f

$f$

y

$y$

y

$y$

(n + 1)

$(n+1)$

y

$y$

1

$1$

n

$n$

(n + 1)

$(n+1)$

Ah, tut mir leid. Ich drehte es in meinem Kopf herum. Ich kann nicht sagen, dass ich hier eine gute Faustregel kenne, also muss jemand anderes diese nehmen.

Tyler Olsen

Antworten:

Klarstellung: Meine Antwort wurde speziell für adaptive Integrationsroutinen mit deterministischer Fehlerkontrolle wie dieser geschrieben . Es wird für spärliche Gitter- und Monte-Carlo-basierte Integrationsroutinen, deren Fehlerkontrolle nicht auf die unten beschriebene Weise durchgeführt wird, umstritten.

Ein erheblicher Kostenfaktor für automatische Tensorprodukt-basierte Black-Box-Integrationsroutinen ist die Fehlerkontrolle unter zwei Gesichtspunkten

Verschwendete Funktionsbewertungen. Alle adaptiven Integrationen funktionieren, indem der Integrand und der Fehler unter Verwendung einer Regel niedriger Ordnung oder einer gröberen Partitionierung geschätzt und mit Regeln höherer Ordnung oder feineren Partitionen wiederholt werden, bis die Fehleranforderungen erfüllt sind. Durch verschachtelte Integrationsregeln können einige der in früheren Schritten geleisteten Arbeiten recycelt werden, häufig jedoch nicht alle.
Um Funktionsbewertungen zu erhalten, werden in adaptiven Integrationscodes häufig stark verschachtelte Regeln wie Gauss-Kronrod oder Newton-Cotes verwendet. Verschachtelte Quadraturregeln sind suboptimale Quadraturregeln, da sie für eine bestimmte Funktionsklasse über eine feste Quadraturordnung erheblich ungenauer sind als optimale Regeln (z. B. Gauss-Legendre und Clenshaw Curtis). Mit anderen Worten, verschachtelte Regeln nutzen Funktionsbewertungen weniger effizient.

$y$ $y$ $f(x,y)$ $y$ $r$

| \sum_{k = 1}^{r} w_{k} f (x, y_{k}) - \int_{[0, 1]} f (x, y) d y | \leq ϵ for all x \in [0, 1]^{n},

$\left|\sum_{k=1}^r w_k f(x,y_k) - \int_{[0,1]}f(x,y)\,\mathrm{d}y\right| \le \epsilon\qquad \text{for all }x\in[0,1]^n,$

f (x, y)

$f(x,y)$

y

$y$

x

$x$

r

$r$

x

$x$

ϵ

$\epsilon$

$g(x)$ $n$ $g(x)$

$f(x,y)$

Um ein Anwendungsbeispiel zu nennen: Dieses genaue Problem trat für mich bei der Bewertung von Volumen-zu-Volumen-Singularintegralen in diesem Artikel auf , und meine Behandlung ähnelt der oben vorgeschlagenen. Als Faustregel ist es immer ratsam, so viele Dimensionen wie möglich mithilfe analytischer Argumente zu entfernen, bevor das Problem durch eine Black-Box-Integrationsroutine geleitet wird.

Richard Zhang
quelle

y

$y$

Mein Argument ist einfach, dass, wenn Sie eine adaptive Methode mit deterministischer Fehlerkontrolle annehmen, die Auswertung einiger Dimensionen in geschlossener Form (oder halb geschlossener Form) unvermeidliche Schritte eliminiert, die sonst numerisch ausgeführt würden. Ihr (ausgezeichnetes) Beispiel ist jedoch eines, bei dem eine deterministische adaptive Methode überhaupt nicht angewendet werden würde.

Richard Zhang

Angenommen, Sie haben eine deterministische Standardanpassungsmethode verwendet, z. B. ab-initio.mit.edu/wiki/index.php/Cubature . Dann wäre ich sehr, sehr überrascht, wenn Sie durch Ausschneiden nicht eine Beschleunigung des gesamten Faktors erhalten eine der Dimensionen semi-analytisch.

Richard Zhang

Wenn Sie Cubature genau so verwenden, wie Sie es vorschlagen (was ein durchaus vernünftiger Vorschlag ist), habe ich in erster Linie die "30-mal langsamere" Zahl in meiner Frage erhalten, also war ich überrascht (daher die Frage). Ich habe das Monte-Carlo-Beispiel nur als etwas leicht zu analysierendes gemeint, ich interessiere mich eigentlich mehr für deterministische Methoden.

Kirill

n + 1

$n+1$

(n + 1)

$(n+1)$