integrasi numerik dalam banyak variabel

12

Biarkan dan f ( x ) : [ 0 , 1 ] nC menjadi fungsi dalam variabel-variabel ini.x=(x1,x2,,xn)[0,1]nf(x):[0,1]nC

Apakah ada skema rekursif untuk integral iterasi ini?

[0,1]ndxif(x)

Jika dan saya membagi [ 0 , 1 ] menjadi 100 segmen, kami memiliki 10 20 poin untuk dijumlahkan. Pasti ada cara yang lebih pintar.n=10[0,1]1020


Sebenarnya, fungsi yang ingin saya integrasikan adalah ukuran Haar dari grup Unitary.

U(n)f(A) dA=1n![0,2π]nj<k|eiθjeiθk|2f(θ1,,θn) dθ12π  dθn2π
John Mangual
sumber
2
Jika dimensi Anda tidak terlalu besar, Anda juga dapat mempertimbangkan metode kuadratur jarang untuk integral Anda.
Paul
@ Paul, bisakah Anda menjelaskan topik ini lebih dalam jawaban? Saya mungkin akan memilih
john mangual

Jawaban:

15

O(N)O(N)O(N14)O(N)

Karena ini probabilistik, Anda perlu mengintegrasikannya beberapa kali menggunakan sejumlah poin untuk menemukan standar deviasi dan perkiraan kesalahan Anda.

Pelihat Godric
sumber
1
Untuk integrasi, penggunaan quasi-Monte-Carlo, misalnya menggunakan urutan Sobel, sedikit lebih baik.
Lutz Lehmann
Ah, ya, saya menyatakan poin equi-didistribusikan (lebih dari pseudo-acak) tetapi tidak secara eksplisit membedakan keduanya.
Godric Seer
1
1nf(xi)[0,1]nf dx
Ya, urutan Sobol akan membangun distribusi poin yang baik. quasi-Monte-Carlo kemungkinan merupakan salah satu metode yang lebih baik untuk masalah Anda.
Godric Seer
8

Kuadratur grid jarang adalah pendekatan alternatif untuk berintegrasi dalam dimensi yang lebih tinggi.

Quadrature bergantung pada evaluasi jumlah nilai fungsi tertimbang pada titik "optimal" tertentu. Kuadratur tradisional menggunakan konstruksi kisi-kisi produk tensor dalam dimensi yang lebih tinggi, yang berarti Anda harus mengevaluasi fungsi pada jumlah titik yang bertambah secara eksponensial seiring dengan meningkatnya dimensi.

Trik untuk kuadratur grid jarang adalah Anda dapat memperoleh akurasi urutan yang sama (dalam arti asimptotik) menggunakan subset kecil dari kisi produk tensor. Poin jarang yang Anda pilih akhirnya adalah mereka yang secara akurat mengintegrasikan monomial hingga tingkat total yang diinginkan . Penghematan komputasi (dibandingkan dengan grid produk tensor) meningkat secara signifikan seiring dengan meningkatnya dimensi.

Namun, ada kekurangan untuk metode ini yang harus Anda waspadai.

  1. Metode ini tidak berfungsi dengan baik jika fungsi Anda tidak lancar (atau sebaliknya tidak didekati dengan baik oleh fungsi polinomial).
  2. Sementara urutan akurasi kuadratur grid jarang mungkin setara dengan grid produk tensor, akurasi relatif mungkin jauh lebih buruk. Ini karena konstan di depan urutan akurasi grid jarang bisa sangat besar.
  3. Grid jarang bekerja dengan baik untuk dimensi yang relatif kecil. Tapi ada dimensi setelah itu Anda mungkin akan lebih baik menggunakan metode lain (seperti monte carlo atau variannya).

Untuk informasi lebih lanjut tentang grid jarang, saya merekomendasikan Grid Sparse Burkardt dalam Dimensi Tinggi . Jika Anda tertarik pada kode untuk menghasilkan grid yang jarang, Anda mungkin ingin mempertimbangkan file matlab ini .

Paul
sumber