numerische Integration in viele Variablen

Sei und sei eine Funktion in diesen Variablen. $\vec{x} = (x_1, x_2, \dots, x_n) \in [0,1]^n$ $f(\vec{x}): [0,1]^n \to \mathbb{C}$

Gibt es ein rekursives Schema für dieses iterierte Integral?

\int_{[0, 1]^{n}} \prod d x_{i} f (\vec{x})

$\int_{[0,1]^n} \prod dx_i \;f(\vec{x})$

Wenn und ich in 100 Segmente zerlege, müssen wir Punkte addieren. Es muss einen intelligenteren Weg geben. $n = 10$ $[0,1]$ $10^{20}$

Tatsächlich ist die Funktion, die ich integrieren möchte, das Haar-Maß der Einheitsgruppe.

\int_{U (n)} f (EIN) d EIN = \frac{1}{n!} \int_{[0, 2 π]^{n}} \prod_{j < k} | e^{ich θ_{j}} - e^{ich θ_{k}} |^{2} \cdot f (θ_{1}, \dots, θ_{n}) \frac{d θ_{1}}{2 π} \dots \frac{d θ_{n}}{2 π}

$\int_{U(n)} f(A) \ dA = \frac{1}{n!} \int_{[0,2\pi]^n} \prod_{j<k} \big|e^{i \theta_j} - e^{i \theta_k}\big|^2 \cdot f(\theta_1, \ldots, \theta_n) \ \frac{d \theta_1}{2\pi} \ \cdots \ \frac{d \theta_n}{2\pi}$

numerical-analysis fourier-analysis John Mangual
quelle

Wenn Ihre Dimension nicht zu groß ist, können Sie auch spärliche Quadraturmethoden für Ihr Integral in Betracht ziehen.

Paul

@Paul kannst du dieses Thema in einer Antwort näher erläutern? Ich werde wahrscheinlich abstimmen

John Mangual

Antworten:

Bei Integrationen mit vielen Variablen ist die Monte-Carlo-Methode normalerweise eine gute Wahl. Sein Fehler nimmt ab, wenn wobei N die Anzahl der ausgewählten gleichverteilten Punkte ist. Dies ist natürlich nicht gut für Räume mit geringen Abmessungen (1D und 2D), in denen Methoden hoher Ordnung existieren. Die meisten dieser deterministischen Methoden benötigen jedoch eine große Anzahl von Punkten in höheren Dimensionen. Zum Beispiel ist ein 1D-Schema 1. Ordnung $O (\sqrt{N})$ in 2D und $O(\sqrt{N})$ in 3D. Die Stärke der Monte-Carlo-Methode besteht darin, dass die Fehlerkonvergenz unabhängig von der Raumdimension ist. Egal ob Ihr Leerzeichen 1D oder 100D ist, es ist $O(N^{\frac{1}{4}})$ . $O (\sqrt{N})$

Da dies jedoch wahrscheinlich ist, müssen Sie es mehrmals mit einer festgelegten Anzahl von Punkten integrieren, um eine Standardabweichung und eine Schätzung Ihres Fehlers zu ermitteln.

Godric Seher
quelle

Für die Integration ist die Verwendung von Quasi-Monte-Carlo, beispielsweise unter Verwendung von Sobel-Sequenzen, etwas besser.

Lutz Lehmann

Ah ja, ich habe gleich verteilte Punkte angegeben (über Pseudozufall), aber nicht explizit zwischen den beiden unterschieden.

Godric Seer

@GodricSeer Sieht so aus, als würden Sobol-Sequenzen auch in großen Dimensionen ein schönes gleichmäßiges Netz bilden. Es scheint, dass er die gleiche Frage anspricht: zu haben

sehr schnell. Gray CodeundDiskrepanzenscheinen Probleme zu sein.

\frac{1}{n} \sum f (x_{ich}) \approx \int_{[0, 1]^{n}} f d x

$\frac{1}{n} \sum f(x_i) \approx \int_{[0,1]^n} f \ dx$

John Mangual

Ja, die Sobol-Sequenz würde eine gute Punkteverteilung ergeben. Quasi-Monte-Carlo ist wahrscheinlich eine der besseren Methoden für Ihr Problem.

Godric Seer

Eine spärliche Gitterquadratur ist ein alternativer Ansatz zur Integration in höhere Dimensionen.

Die Quadratur beruht auf der Auswertung einer gewichteten Summe von Funktionswerten an bestimmten "optimalen" Punkten. Herkömmliche Quadratur verwendet eine Tensorproduktgitterkonstruktion in höheren Dimensionen, was bedeutet, dass Sie die Funktion mit zunehmender Dimension an einer exponentiell wachsenden Anzahl von Punkten bewerten müssen.

Der Trick, die Gitterquadratur zu sparsamen besteht darin, dass Sie mit einer kleinen Teilmenge des Tensorproduktgitters die gleiche Ordnungsgenauigkeit (im asymptotischen Sinne) können. Die wenigen Punkte, die Sie auswählen, sind diejenigen, die Monome bis zu einem gewünschten Gesamtgrad genau integrieren . Die Recheneinsparungen (im Vergleich zum Tensorproduktgitter) steigen mit zunehmender Dimension erheblich.

Es gibt jedoch Nachteile bei dieser Methode, die Sie beachten sollten.

Diese Methode funktioniert nicht gut, wenn Ihre Funktion nicht glatt ist (oder durch Polynomfunktionen nicht gut approximiert wird).
Während die Genauigkeitsreihenfolge der spärlichen Gitterquadratur einem Tensorproduktgitter äquivalent sein kann, kann die relative Genauigkeit viel schlechter sein. Dies liegt daran, dass die Konstante vor der Genauigkeitsreihenfolge des dünnen Gitters sehr groß sein kann.
Sparsame Gitter eignen sich gut für relativ kleine Dimensionen. Aber es gibt eine Dimension, nach der Sie wahrscheinlich besser dran sind, wenn Sie eine andere Methode verwenden (wie Monte Carlo oder seine Varianten).

Für weitere Informationen zu dünnen Gittern empfehle ich Burkardts dünne Gitter in hohen Dimensionen . Wenn Sie an Code zum Generieren von spärlichen Gittern interessiert sind, sollten Sie diese Matlab-Dateien berücksichtigen .

Paul
quelle