Bagaimana cara memperkirakan keakuratan suatu integral?

11

Situasi yang sangat umum dalam grafik komputer adalah bahwa warna beberapa piksel sama dengan integral dari beberapa fungsi bernilai nyata. Seringkali fungsi ini terlalu rumit untuk diselesaikan secara analitis, jadi kita dibiarkan dengan pendekatan numerik. Tetapi fungsi ini juga sering kali sangat mahal untuk dihitung, jadi kami sangat terkendala dalam berapa banyak sampel yang dapat kami hitung. (Misalnya, Anda tidak bisa hanya memutuskan untuk mengambil satu juta sampel dan membiarkannya begitu saja.)

Secara umum, yang ingin Anda lakukan adalah mengevaluasi fungsi pada titik yang dipilih secara acak hingga integral yang diperkirakan menjadi "cukup akurat". Yang membawa saya ke pertanyaan saya yang sebenarnya: Bagaimana Anda memperkirakan "keakuratan" integral?


Lebih khusus, kami memiliki , yang diimplementasikan oleh beberapa algoritma komputer yang rumit dan lambat. Kami ingin memperkirakanf:RR

k=abf(x) dx

Kita dapat menghitung untuk setiap kita inginkan, tetapi harganya mahal. Jadi kami ingin memilih beberapa nilai secara acak, dan berhenti ketika perkiraan untuk menjadi akurat. Untuk melakukan ini, tentu saja, kita perlu tahu seberapa akurat perkiraan saat ini sebenarnya.f(x)xxk

Saya bahkan tidak yakin alat statistik apa yang cocok untuk masalah seperti ini. Tetapi nampak bagi saya bahwa jika kita sama sekali tidak tahu tentang , maka masalahnya tidak dapat diselesaikan. Misalnya, jika Anda menghitung seribu kali dan selalu nol, taksiran integral Anda akan menjadi nol. Tapi, tidak tahu apa-apa tentang , masih mungkin bahwa mana-mana kecuali poin yang Anda ambil sampel, jadi perkiraan Anda sangat salah!ff(x)ff(x)=1,000,000

Mungkin, kemudian, pertanyaan saya seharusnya dimulai dengan "apa yang perlu kita ketahui tentang agar memungkinkan untuk memperkirakan keakuratan integral kitaf ?" Sebagai contoh, sering kita tahu bahwa tidak mungkin bagi untuk menjadi negatif, yang kelihatannya merupakan fakta yang sangat relevan ...f


Sunting: Oke, jadi ini sepertinya telah menghasilkan banyak respons, yang bagus. Daripada membalas masing-masing secara individual, saya akan mencoba untuk mengisi beberapa latar belakang tambahan di sini.

Ketika saya mengatakan kita tidak tahu apa-apa tentang , maksud saya kita bisa menghitung , tetapi kita tidak tahu apa-apa lagi tentang itu. Saya berharap (dan komentar tampaknya setuju) bahwa memiliki lebih banyak pengetahuan memungkinkan kami untuk menggunakan algoritma yang lebih baik. Tampaknya mengetahui batas-batas pada dan / atau turunan pertama dari akan berguna.ffff

Dalam sebagian besar masalah yang saya sedang berpikir tentang, perubahan tergantung pada geometri adegan dan lokasi dalam adegan di bawah pertimbangan. Ini bukan aljabar yang bagus dan rapi yang secara analitis dapat Anda pecahkan. Biasanya mewakili intensitas cahaya. Jelas intensitas cahaya tidak mungkin negatif, tetapi tidak ada batasan seberapa besar nilai positifnya. Dan akhirnya, tepi objek biasanya menghasilkan diskontinuitas yang tajam pada , dan biasanya Anda tidak dapat memprediksi di mana ini.fff

Singkatnya, terkutuk fiddly, jadi port of call pertama saya adalah untuk bertanya apa yang bisa kita lakukan dengan itu tanpa informasi lebih lanjut. Tampaknya tanpa setidaknya batas atas dan bawah, jawabannya adalah "tidak banyak" ... Jadi sepertinya saya harus mulai membuat beberapa asumsi untuk membuat kemajuan di sini.f

Juga, mengingat berapa kali "Monte Carlo" muncul, saya menduga itu istilah teknis untuk integrasi semacam ini?

Matematika Matematika
sumber
Ketika Anda mengatakan "jika kita sama sekali tidak tahu tentang ", apa maksud Anda sebenarnya? Kita bisa menghitung , kan? fff
Makro
2
Biasanya, ketika Anda mengintegrasikan lebih dari fungsi yang diketahui, Anda dapat melakukan jauh lebih baik daripada integrasi Monte Carlo. Monte Carlo menyatu ke nilai sebenarnya pada tingkat , di mana adalah jumlah poin evaluasi. Algoritme lain, misalnya berbasis quadrature, akan bertemu pada kecepatan atau bahkan lebih cepat (misalnya, untuk fungsi yang periodik di wilayah integrasi), dengan asumsi tingkat kelancaran fungsi. Yang lain lagi, berdasarkan urutan kuasi-acak (misalnya, urutan Sobol '), akan bertemu pada tingkat menengah, misalnya, untuk integrasi dimensi. N1/N(lnN)n/Nn1/NN1/N(lnN)n/Nn
jbowman
1
Ini memiliki jawaban yang jelas tetapi tidak menguntungkan. Jawaban untuk pertanyaan kedua adalah "tidak ada": satu-satunya persyaratan adalah bahwa dapat diukur, yang tersirat dalam meminta integralnya. Tapi kemudian satu-satunya hal yang dapat Anda lakukan adalah pengambilan sampel secara acak. Dengan asumsi tambahan, seseorang dapat melakukan jauh lebih baik dalam memperkirakan integral dan menilai akurasi. Jadi pertanyaan yang lebih baik adalah "perbaikan dalam estimasi akurasi yang dapat dicapai dengan asumsi mana." Tapi ini terlalu luas. Karena itu, beri tahu kami fungsi apa yang sedang Anda tangani. f
whuber
1
@ Macro Prosedur itu tidak menguntungkan karena itu yang terburuk yang bisa Anda lakukan. Seperti yang ditunjukkan jbowman, asumsi yang sangat ringan tentang dapat menghasilkan estimasi yang jauh lebih baik. BTW, tidak ada artinya untuk menetapkan bahwa adalah "terbatas." Jika itu adalah fungsi yang terdefinisi dengan baik, semua nilainya adalah bilangan real dan terbatas fortiori . Jika Anda berarti "terikat," itu tidak ada gunanya kecuali Anda tahu batas sebelumnya. fff
whuber
1
@Macro "Sebagian" fungsi tidak berkelanjutan di mana saja! Bahkan, saya tidak melihat bagaimana CLT bisa berlaku secara umum. bisa menjadi CDF terbalik dari setiap distribusi, misalnya, dalam hal ini penarikan Monte-Carlo Anda diambil dari distribusi tersebut - yang CLT tidak perlu terapkan bahkan jika integral itu sendiri (yaitu, rata-rata) ada. Saya pikir akan jauh lebih bermanfaat bagi OP untuk mempersempit pertanyaan dan responden untuk mengikuti saran jbowman. f
Whuber

Jawaban:

2

Untuk kesederhanaan, anggap f (x)> = 0 untuk semua x dalam [a, b] dan kita tahu M sedemikian sehingga f (x) <M untuk semua x dalam [a, b]. Integral I dari f atas [a, b] dapat ditutup dalam persegi panjang dengan lebar ba dan tinggi M. Integrasi dari f adalah proporsi persegi panjang yang jatuh di bawah fungsi f dikalikan dengan M (ba). Sekarang jika Anda memilih poin dalam kotak secara acak dan menghitung poin sebagai keberhasilan jika jatuh di bawah kurva dan sebagai kegagalan jika tidak, Anda telah menyiapkan uji coba Bernoulli. Fraksi sampel dari titik-titik di dalam adalah proporsi binomial dan karenanya memiliki p rata-rata dan varians p (1-p) / n di mana n adalah jumlah poin yang diambil. Oleh karena itu Anda dapat membangun interval kepercayaan untuk p dan karena I = p M (ba) interval kepercayaan untuk saya juga karena untuk estimasi I ^ = p ^ M (ba), Var (I ^) = M (ba)2 2 2 2 222p (1-p) / n. Jadi, untuk menggunakan statistik untuk menentukan n terkecil yang integralnya cukup akurat, Anda dapat menentukan batas atas S pada varian I ^. Catat p (1-p) / n <= 1 / (4n) untuk setiap 0 <= p <= 1. Jadi atur S = M (ba) / (4n) atau n = integer terkecil> M (ba) / (4S).2222

Michael R. Chernick
sumber
3
Ini akan bekerja di bawah asumsi Anda diletakkan dalam kalimat pertama, tetapi berdasarkan uraian masalah tampaknya tidak mungkin bahwa Anda bisa, a priori , terikat nilai-nilai fungsi antara dan . Tampaknya semua yang Anda berikan adalah kemampuan untuk menghitung dan tidak ada yang lain. M f0Mf
Makro
1
@ Macro Tanpa mengetahui apa pun tentang f Saya tidak melihat bagaimana orang dapat mengatakan apa pun tentang keakuratan statistik estimasi integral berdasarkan evaluasi pada set poin yang terbatas. Asumsi saya agak minim. Jika f dibatasi pada interval [a, b] harus ada beberapa M yang cukup besar sehingga dapat digunakan sebagai batas atas pada f.
Michael R. Chernick
Saya tentu setuju dengan kalimat pertama Anda, yang mulai menjawab pertanyaan kedua OP. Tetapi, metode yang telah Anda jelaskan mengharuskan Anda, seorang apriori , tahu , yang bukan asumsi yang minimal. M
Makro
2
Itu adalah asumsi. Saya menggunakan istilah mimimal untuk mengatakan bahwa saya membuat asumsi sesedikit mungkin untuk mencapai jawaban yang pasti.
Michael R. Chernick
Ide yang cerdik ... Anda benar, itu tidak berfungsi tanpa batas pada , tetapi sepertinya Anda tidak dapat melakukan banyak hal tanpa informasi itu. f
MathematicalOrchid
8

Ini adalah pertanyaan non-sepele yang melibatkan isu-isu seperti variasi total dari dan ekstensi multivariat yang wajar. Ahli statistik Stanford, Art Owen telah mengerjakan ini menggunakan teknik quasi-Monte Carlo secara acak . Monte Carlo reguler memungkinkan estimasi langsung keakuratan integral, tetapi setiap evaluasi individu tidak seakurat itu. Quasi-Monte Carlo menghasilkan estimasi yang lebih akurat, tetapi ini adalah teknik yang sepenuhnya deterministik, dan karenanya tidak memungkinkan untuk memperkirakan varians hasil Anda. Dia menunjukkan bagaimana menggabungkan kedua pendekatan, dan makalahnya sangat jelas, jadi saya tidak akan mencoba mereproduksi di sini.f

Bacaan tambahan untuk ini tentu saja akan menjadi Niederreiter (1992) monograf.

Tugas
sumber
3
(+1) Josef Dick juga memiliki beberapa hasil terkait yang cukup menarik.
kardinal