Jak oszacować dokładność całki?

11

Niezwykle częstą sytuacją w grafice komputerowej jest to, że kolor niektórych pikseli jest równy całce funkcji o wartościach rzeczywistych. Często funkcja jest zbyt skomplikowana, aby ją rozwiązać analitycznie, więc pozostaje nam przybliżenie numeryczne. Ale funkcja ta jest również często bardzo droga do obliczenia, dlatego jesteśmy bardzo ograniczeni liczbą próbek, które możemy obliczyć. (Na przykład nie możesz po prostu wziąć miliona próbek i zostawić to w tym miejscu).

Ogólnie rzecz biorąc, to, co chcesz zrobić, to ocenić funkcję w losowo wybranych punktach, aż oszacowana całka stanie się „wystarczająco dokładna”. Co prowadzi mnie do mojego aktualnego pytania: Jak oceniasz „dokładność” całki?


Mówiąc dokładniej, mamy f:RR , który jest implementowany przez jakiś skomplikowany, wolny algorytm komputerowy. Chcemy oszacować

k=abf(x) dx

Możemy obliczyć dla dowolnego x, którego chcemy, ale jest to kosztowne. Chcemy więc losowo wybrać kilka wartości x i zatrzymać, gdy oszacowanie dla k stanie się akceptowalnie dokładne. Aby to zrobić, musimy oczywiście wiedzieć, jak dokładne są aktualne szacunki.f(x)xxk

Nie jestem nawet pewien, jakie narzędzia statystyczne byłyby odpowiednie dla tego rodzaju problemu. Wydaje mi się jednak, że jeśli nie wiemy absolutnie nic o , problem jest nierozwiązywalny. Na przykład, jeśli obliczymy f ( x ) tysiąc razy i zawsze jest to zero, oszacowana całka wyniesie zero. Ale, nie wiedząc nic o f , to wciąż możliwe, że f ( x ) = 1 , 000 , 000 wszędzie z wyjątkiem punktów zdarzyło się próbki, więc oszacowanie jest bardzo źle!ff(x)ff(x)=1,000,000

Być może zatem moje pytanie powinno zacząć się od „co musimy wiedzieć o aby umożliwić oszacowanie dokładności naszej całkif ?” Na przykład często wiemy, że nigdy nie jest ujemny, co wydaje się być bardzo istotnym faktem ...f


Edycja: OK, więc wydaje się, że wygenerowało wiele odpowiedzi, co jest dobre. Zamiast odpowiadać każdemu z nich osobno, postaram się tutaj uzupełnić o dodatkowe informacje.

Kiedy mówię, że wiemy „nic” o , mam na myśli, że możemy obliczyć f , ale nie wiemy nic więcej na ten temat. Spodziewałbym się (a komentarze wydają się zgadzać), że posiadanie większej wiedzy pozwala nam korzystać z lepszych algorytmów. Wydaje się, że przydatna byłaby znajomość granic f i / lub pierwszej pochodnej f .ffff

W większości problemów, o których myślę, zmienia się w zależności od geometrii sceny i lokalizacji w rozważanej scenie. To nie jest ładny, schludny kawałek algebry, który można analitycznie rozwiązać. Zazwyczaj f oznacza natężenie światła. Oczywiście natężenie światła nigdy nie może być ujemne, ale nie ma ograniczenia co do wielkości jego dodatnich wartości. I wreszcie, krawędzie obiektów zwykle powodują ostre nieciągłości w f , i zwykle nie można przewidzieć, gdzie one są.fff

Krótko mówiąc, jest przeklęty, więc moim pierwszym portem było zapytanie, co możemy z tym zrobić, bez dalszych informacji. Wygląda na to, że bez przynajmniej niektórych górnych i dolnych granic odpowiedź brzmi „nie do cholery” ... Wygląda więc na to, że muszę zacząć myśleć o pewnych założeniach, aby poczynić tutaj postępy.f

Biorąc pod uwagę, ile razy pojawił się „Monte Carlo”, zgaduję, że to techniczny termin na tego rodzaju integrację?

MathematicalOrchid
źródło
Kiedy mówisz „jeśli absolutnie nic nie wiemy o ”, co dokładnie masz na myśli? Możemy obliczyć f , prawda? ff
Makro
2
Zazwyczaj, gdy integrujesz za pomocą znanej funkcji, możesz zrobić znacznie lepiej niż integracja Monte Carlo. Monte Carlo zbiega się do wartości rzeczywistej w stosunku , gdzieNjest liczbą punktów oceny. Inne algorytmy, np. Oparte na kwadraturze, będą zbiegać się z prędkością1/Nlub nawet szybciej (np. Dla funkcji okresowej w regionie integracji), zakładając pewien poziom gładkości funkcji. Jeszcze inne, oparte na sekwencjach quasi-losowych (np. Sekwencje Sobola), będą zbieżne w pośrednich szybkościach, np.(1nN)n/Ndlaintegracjin-wymiarowej. 1/NN1/N(lnN)n/Nn
jbowman
1
To ma jasne, ale nieoczekiwane odpowiedzi. Odpowiedź na drugie pytanie brzmi „nic”: jedynym wymogiem jest, aby był mierzalny, co jest dorozumiane w pytaniu o jego całkę. Ale wtedy jedyne, co możesz zrobić, to losowe próbkowanie. Przy dodatkowych założeniach można znacznie lepiej oszacować całkę i ocenić dokładność. Lepszym pytaniem jest więc „jakie ulepszenia w zakresie szacowania dokładności można osiągnąć przy pomocy jakich założeń”. Ale to jest zbyt szerokie. Dlatego powiedz nam, z jakim rodzajem funkcji masz obecnie do czynienia. f
whuber
1
@Macro Ta procedura jest mało opłacalna, ponieważ to najgorsze, co możesz zrobić. Jak zauważa jbowman, bardzo łagodne założenia dotyczące mogą prowadzić do znacznie lepszych szacunków. BTW, nie ma sensu ustalać, że f jest „skończone”. Jeśli jest to dobrze zdefiniowana funkcja, wszystkie jej wartości są liczbami rzeczywistymi i tym bardziej skończonymi. Jeśli miałeś na myśli „ograniczoną”, nie ma to dla ciebie żadnego dobra, chyba że wcześniej znasz granice. ff
whuber
1
@Macro „Większość” funkcji nie jest nigdzie ciągła! W rzeczywistości nie rozumiem, w jaki sposób CLT mógłby mieć zastosowanie w ogóle. może być odwrotnym CDF dosłownie dowolnego rozkładu, na przykład w tym przypadku twoje losowania Monte-Carlo próbkują z tego rozkładu - do którego CLT nie musi mieć zastosowania, nawet jeśli sama całka (tj. średnia) istnieje. Myślę, że OP byłoby bardziej owocne, gdyby zawęził to pytanie, a respondenci zastosowali się do sugestii jbowmana. f
whuber

Odpowiedzi:

2

Dla uproszczenia załóżmy, że f (x)> = 0 dla wszystkich x w [a, b] i wiemy, że M (f) x (M) dla wszystkich x w [a, b]. Całka I f nad [a, b] może być zamknięta w prostokącie o szerokości ba i wysokości M. Całka f jest proporcją prostokąta objętą funkcją f pomnożoną przez M (ba). Teraz, jeśli wybierzesz losowo punkty w prostokącie i policzysz ten punkt jako sukces, jeśli spadnie on pod krzywą, a jako porażkę, w przeciwnym razie skonfigurujesz próbę Bernoulliego. Część próbna punktów w środku jest proporcją dwumianową, a zatem ma średnią p i wariancję p (1-p) / n, gdzie n jest liczbą uzyskanych punktów. Stąd można skonstruować przedział ufności dla p, a ponieważ I = p M (ba) przedział ufności dla I także, ponieważ dla oszacowania I ^ = p ^ M (ba), Var (I ^) = M (ba) 222p (1-p) / n. Aby więc użyć statystyk do ustalenia najmniejszego n, dla którego całka jest wystarczająco dokładna, można określić górną granicę S wariancji I ^. Uwaga p (1-p) / n <= 1 / (4n) dla każdego 0 <= p <= 1. Więc ustaw S = M 2 (ba) 2 / (4n) lub n = najmniejsza liczba całkowita> M 2 (ba) 2 / (4S).2222

Michael R. Chernick
źródło
3
To będzie działać zgodnie z założeniami ty określonymi w zdaniu pierwszym, ale na podstawie opisu problemu wydaje się mało prawdopodobne, że można, a priori , związany wartości funkcji między i M . Okazało się, że wszystko, co masz, to umiejętność obliczenia f i nic więcej. 0Mf
Makro
1
@Macro Nie wiedząc nic o f, nie widzę, jak można by cokolwiek powiedzieć o statystycznej dokładności oszacowania całki opartej na ocenie jej w ustalonym skończonym zbiorze punktów. Moje założenia są raczej minimalne. Jeśli f jest ograniczone w przedziale [a, b], powinno być trochę M wystarczająco duże, aby można go było użyć jako górnej granicy na f.
Michael R. Chernick
Z pewnością zgadzam się z twoim pierwszym zdaniem, które zaczyna odnosić się do drugiego pytania PO. Ale metoda, którą opisałeś, wymaga, abyś z góry znał , co nie jest szczególnie minimalnym założeniem. M
Makro
2
To założenie. Użyłem terminu mimimal, aby powiedzieć, że poczyniłem jak najmniej założeń, aby uzyskać ostateczną odpowiedź.
Michael R. Chernick
Co za genialny pomysł ... Masz rację, to nie działa bez ograniczeń , ale wygląda na to, że nie możesz wiele zrobić bez tych informacji. f
MathematicalOrchid
8

Jest to nietrywialne pytanie, które obejmuje zagadnienia takie jak całkowitej zmienności z f i jego rozsądnych rozszerzeń wielowymiarowych. Statystyk Stanford, Art Owen, pracował nad tym przy użyciu losowych technik quasi-Monte Carlo . Zwykły Monte Carlo pozwala na bezpośrednie oszacowanie dokładności całki, ale każda indywidualna ocena nie jest tak dokładna. Quasi-Monte Carlo daje dokładniejsze oszacowania, ale jest to technika w pełni deterministyczna i jako taka nie pozwala oszacować wariancji wyniku. Pokazał, jak połączyć te dwa podejścia, a jego praca jest bardzo przejrzysta, więc nie będę próbował jej tutaj odtworzyć.

Uzupełnieniem tego będzie oczywiście monografia Niederreiter (1992) .

StasK
źródło
3
(+1) Josef Dick ma również kilka interesujących dość niedawnych powiązanych wyników.
kardynał