Como estimar a precisão de uma integral?

11

Uma situação extremamente comum em computação gráfica é que a cor de algum pixel é igual à integral de alguma função com valor real. Freqüentemente, a função é muito complicada para ser resolvida analiticamente, então ficamos com a aproximação numérica. Mas a função também costuma ser muito cara de calcular, por isso estamos muito limitados em quantas amostras podemos calcular. (Por exemplo, você não pode simplesmente decidir coletar um milhão de amostras e deixar assim.)

Em geral, o que você deseja fazer é avaliar a função em pontos escolhidos aleatoriamente até que a integral estimada se torne "precisa o suficiente". O que me leva à minha pergunta real: como você estima a "precisão" da integral?


Mais especificamente, temos , que é implementado por algum algoritmo complicado e lento do computador. Queremos estimarf:RR

k=abf(x) dx

Podemos calcular para qualquer x que desejamos, mas é caro. Portanto, queremos escolher vários valores x aleatoriamente e parar quando a estimativa de k se tornar aceitável e precisa. Para fazer isso, é claro, precisamos saber quão precisa é a estimativa atual.f(x)xxk

Não tenho certeza de que ferramentas estatísticas seriam apropriadas para esse tipo de problema. Mas parece-me que, se não sabemos absolutamente nada sobre , então o problema é insolúvel. Por exemplo, se você calcular f ( x ) mil vezes e sempre for zero, sua integral estimada será zero. Mas, sabendo nada sobre f , ainda é possível que f ( x ) = 1 , 000 , 000 em toda parte exceto os pontos que aconteceram a amostra, assim que sua estimativa é horrivelmente errado!ff(x)ff(x)=1,000,000

Talvez, então, minha pergunta devesse ter começado com "o que precisamos saber sobre para tornar possível estimar a precisão de nossa integralf ?" Por exemplo, muitas vezes sabemos que é impossível que seja negativo, o que parece ser um fato altamente relevante ...f


Edit: OK, então isso parece ter gerado muitas respostas, o que é bom. Em vez de responder a cada um deles individualmente, tentarei preencher alguns antecedentes adicionais aqui.

Quando digo que não sabemos "nada" sobre , quero dizer que podemos calcular f , mas não sabemos mais nada sobre isso. Eu esperaria (e os comentários parecem concordar) que ter mais conhecimento nos permite usar algoritmos melhores. Parece que conhecer limites em f e / ou a primeira derivada de f seria útil.ffff

Na maioria dos problemas em que estou pensando, muda dependendo da geometria da cena e da localização dentro da cena em consideração. Não é um pedaço de álgebra legal e arrumado que você possa resolver analiticamente. Normalmente, f representa a intensidade da luz. Obviamente, a intensidade da luz nunca pode ser negativa, mas não há limite para o tamanho dos seus valores positivos. E, finalmente, as arestas dos objetos geralmente resultam em descontinuidades acentuadas em f , e geralmente você não pode prever onde elas estão.fff

Em suma, é muito complicado, então minha primeira ligação foi perguntar o que podemos fazer com isso, sem mais informações. Parece que, sem pelo menos alguns limites superiores e inferiores, a resposta é "não muito" ... Então, parece que eu preciso começar a fazer algumas suposições para avançar aqui.f

Além disso, dado o número de vezes que "Monte Carlo" surgiu, acho que esse é o termo técnico para esse tipo de integração?

MathematicsOrchid
fonte
ff
2
1/NN1/N(lnN)n/Nn
11
f
11
ff
11
f

Respostas:

2

222222

Michael R. Chernick
fonte
3
0Mf
11
@ Macro Sem saber nada sobre f, não vejo como se poderia dizer algo sobre a precisão estatística de uma estimativa da integral com base na avaliação em um conjunto finito fixo de pontos. Minhas suposições são bastante mínimas. Se f estiver delimitado no intervalo [a, b], deve haver algum M grande o suficiente para que possa ser usado como limite superior em f.
Michael R. Chernick
M
2
É uma suposição. Usei o termo mimimal para dizer que estou fazendo o mínimo de suposições possível para chegar a uma resposta definitiva.
Michael R. Chernick
f
8

f

Uma leitura complementar a isso seria, obviamente, a monografia de Niederreiter (1992) .

StasK
fonte
3
(+1) Josef Dick também tem alguns resultados relacionados bastante recentes interessantes.
cardeal