całkowanie numeryczne w wielu zmiennych

12

Niech a być funkcją w tych zmiennych.f(x ):[0,1]nCx=(x1,x2,,xn)[0,1]nf(x):[0,1]nC

Czy istnieje schemat rekurencyjny dla tej iterowanej całki?

[0,1]ndxif(x)

Jeśli a ja podzielę na 100 segmentów, mamy punktów do zsumowania. Musi być mądrzejszy sposób.[ 0 , 1 ] 10 20n=10[0,1]1020


W rzeczywistości funkcją, którą chcę zintegrować, jest miara Haara grupy Unitary.

U(n)f(A) dA=1n![0,2π]nj<k|eiθjeiθk|2f(θ1,,θn) dθ12π  dθn2π
John Mangual
źródło
2
Jeśli twój wymiar nie jest zbyt duży, możesz również rozważyć rzadkie metody kwadraturowe dla całki.
Paweł
@Paul, czy możesz wyjaśnić ten temat bardziej w odpowiedzi? Prawdopodobnie będę głosować
John Mangual

Odpowiedzi:

15

W przypadku integracji z wieloma zmiennymi metoda Monte Carlo zwykle jest przyzwoitym dopasowaniem. Jego błąd maleje wraz z gdzie N jest liczbą wybranych równo rozmieszczonych punktów. Oczywiście nie jest to dobre w przypadku przestrzeni niskiego wymiaru (1D i 2D), w których istnieją metody wyższego rzędu. Jednak większość z tych metod deterministycznych zajmuje dużą liczbę punktów w wyższych wymiarach. Na przykład schemat 1D 1. rzędu to w 2D i w 3D. Siłą metody Monte Carlo jest to, że zbieżność błędów jest niezależna od wymiaru przestrzeni. Bez względu na to, czy masz przestrzeń 1D czy 100D, jest to . O(O(N)O(N 1O(N)O(O(N14)O(N)

Ponieważ jest to probabilistyczne, musisz go zintegrować wiele razy, używając ustalonej liczby punktów, aby znaleźć odchylenie standardowe i oszacować swój błąd.

Godric Seer
źródło
1
W przypadku integracji użycie quasi-Monte-Carlo, na przykład przy użyciu sekwencji Sobela, jest nieco lepsze.
Lutz Lehmann
Ach, tak, podałem punkty równomiernie rozłożone (ponad pseudolosowe), ale nie wyraźnie rozróżniałem te dwa.
Godric Seer,
1
@GodricSeer Wygląda na to, że sekwencje Sobola zbudują ładną, równomiernie rozmieszczoną siatkę, nawet w dużych wymiarach. Wygląda na to, że odpowiada on na to samo pytanie: bardzo szybko uzyskać . Problemy stanowią szary kod i rozbieżności .
1nf(xi)[0,1]nf dx
John Mangual
Tak, sekwencja Sobola zbudowałaby dobry rozkład punktów. quasi-Monte-Carlo jest prawdopodobnie jedną z lepszych metod dla twojego problemu.
Godric Seer,
8

Rzadka kwadratura siatki to alternatywne podejście do integracji w wyższych wymiarach.

Kwadratura polega na ocenie ważonej sumy wartości funkcji w określonych „optymalnych” punktach. Tradycyjna kwadratura wykorzystuje konstrukcję siatki produktu tensorowego w wyższych wymiarach, co oznacza, że ​​musisz oceniać funkcję w wykładniczo rosnącej liczbie punktów wraz ze wzrostem wymiaru.

Sztuczka polegająca na rozrzedzeniu kwadratury siatki polega na tym, że można uzyskać tę samą dokładność zamówienia (w sensie asymptotycznym) przy użyciu małego podzbioru siatki produktu tensorowego. Wybrane przez ciebie rzadkie punkty to te, które dokładnie integrują monomialy do pożądanego całkowitego stopnia . Oszczędności obliczeniowe (w porównaniu do siatki produktów tensorowych) znacznie rosną wraz ze wzrostem wymiaru.

Istnieją jednak wady tej metody, o których powinieneś wiedzieć.

  1. Ta metoda nie działa dobrze, jeśli funkcja nie jest płynna (lub w inny sposób nie jest dobrze przybliżona przez funkcje wielomianowe).
  2. Podczas gdy rząd dokładności kwadratury siatki rzadkiej może być równoważny siatce produktu tensorowego, dokładność względna może być znacznie gorsza. Wynika to z faktu, że stała przed rzędem dokładności rzadkiej siatki może być bardzo duża.
  3. Rzadkie siatki działają dobrze dla stosunkowo małych wymiarów. Ale pojawia się wymiar, po którym prawdopodobnie lepiej byłoby użyć innej metody (takiej jak Monte Carlo lub jej warianty).

Aby uzyskać więcej informacji na temat rzadkich siatek, polecam rzadkie siatki Burkardta w dużych wymiarach . Jeśli interesuje Cię kod do generowania rzadkich siatek, możesz rozważyć te pliki Matlab .

Paweł
źródło