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

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 : \mathbb{R} \rightarrow \mathbb{R}$ , który jest implementowany przez jakiś skomplikowany, wolny algorytm komputerowy. Chcemy oszacować

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)$$x$$x$$k$

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!$f$$f(x)$$f$$f(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łki$f$ ?” 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 .$f$$f$$f$$f$

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ą.$f$$f$$f$

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ę?

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)$^2$$^2$p (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).$^2$$^2$$^2$$^2$

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) .