¿Cómo estimar la precisión de una integral?

Question

Una situación muy común en los gráficos por ordenador es que el color de un píxel sea igual a la integral de una función de valor real. A menudo, la función es demasiado complicada para resolverla analíticamente, por lo que se recurre a la aproximación numérica. Pero la función también suele ser muy cara de calcular, por lo que estamos muy limitados en cuanto al número de muestras que podemos calcular. (Por ejemplo, no se puede decidir tomar un millón de muestras y dejarlo así).

En general, lo que se quiere hacer es evaluar la función en puntos elegidos al azar hasta que la integral estimada sea lo suficientemente precisa. Lo que me lleva a mi pregunta: ¿Cómo se estima la "precisión" de la integral?

---

Más concretamente, tenemos $f : \mathbb{R} \rightarrow \mathbb{R}$ que se implementa mediante un complicado y lento algoritmo informático. Queremos estimar

$$k = \int_a^b f(x) \ dx$$

Podemos calcular $f(x)$ para cualquier $x$ que deseamos, pero es caro. Así que queremos elegir varios $x$ -al azar, y se detiene cuando la estimación de $k$ se convierte en aceptablemente precisa. Para ello, por supuesto, necesitamos saber cuál es la precisión real de la estimación actual.

Ni siquiera estoy seguro de qué herramientas estadísticas serían adecuadas para este tipo de problema. Pero me parece que si sabemos absolutamente nada acerca de $f$ entonces el problema no tiene solución. Por ejemplo, si se calcula $f(x)$ mil veces y siempre es cero, tu integral estimada sería cero. Pero, sin saber nada de $f$ todavía es posible que $f(x) = 1,000,000$ en todas partes excepto en los puntos que has muestreado, ¡así que tu estimación es terriblemente errónea!

Quizás, entonces, mi pregunta debería haber empezado por "¿qué necesitamos saber sobre $f$ para hacerlo posible para estimar la precisión de nuestra integral ?" Por ejemplo, a menudo sabemos que es imposible que $f$ ser negativo alguna vez, lo que parece ser un hecho muy relevante...

---

Edita: Vale, parece que esto ha generado muchas respuestas, lo cual es bueno. En lugar de responder a cada una de ellas por separado, voy a intentar aportar aquí algunos datos adicionales.

Cuando digo que no sabemos "nada" sobre $f$ Quiero decir que podemos calcular $f$ pero no sabemos nada más al respecto. Yo esperaría (y los comentarios parecen estar de acuerdo) que tener más conocimientos nos permite utilizar mejores algoritmos. Parece que conocer los límites de $f$ y/o la primera derivada de $f$ sería útil.

En la mayoría de los problemas en los que estoy pensando, $f$ cambia en función de la geometría de la escena y de la ubicación dentro de la escena considerada. No se trata de una bonita y ordenada pieza de álgebra que se pueda resolver analíticamente. Por lo general, $f$ representa la intensidad luminosa. Obviamente, la intensidad luminosa nunca puede ser negativa, pero sus valores positivos no tienen límite. Y por último, los bordes de los objetos suelen dar lugar a discontinuidades bruscas en $f$ y normalmente no se puede predecir dónde están.

Resumiendo, $f$ es condenadamente incómoda, así que lo primero que hice fue preguntar qué podíamos hacer con ella, a falta de más información. Parece que sin unos límites superior e inferior, la respuesta es "no mucho"... Así que parece que tengo que empezar a hacer algunas suposiciones para avanzar.

Además, dado el número de veces que se ha hablado de "Montecarlo", supongo que ése es el término técnico para este tipo de integración.

Answer 1

Por simplicidad supongamos f(x)>=0 para todo x en [a,b] y conocemos M tal que f(x) < M para todo x en [a,b]. La integral I de f sobre [a,b] puede encerrarse en el rectángulo de anchura b-a y altura M. La integral de f es la proporción del rectángulo que cae bajo la función f multiplicada por M(b-a). Ahora bien, si elegimos puntos del rectángulo al azar y contamos el punto como un éxito si cae bajo la curva y como un fracaso en caso contrario, habremos establecido un ensayo de Bernoulli . La fracción muestral de puntos en el interior es una proporción binomial y, por tanto, tiene media p y varianza p(1-p)/n, donde n es el número de puntos tomados. Por lo tanto, puede construir un intervalo de confianza para p y, puesto que I =p M(b-a), un intervalo de confianza para I también, ya que para la estimación I^ =p^ M (b-a), Var(I^)= M $^2$ (b-a) $^2$ p(1-p)/n. Así que para utilizar la estadística para determinar el n más pequeño para el que la integral es lo suficientemente precisa se podría especificar un límite superior S en la varianza de I^. Nótese que p(1-p)/n <=1/(4n) para cada 0<=p<=1. Así que fija S=M $^2$ (b-a) $^2$ /(4n) o n = número entero más pequeño> M $^2$ (b-a) $^2$ /(4S).

Answer 2

Se trata de una cuestión no trivial que implica aspectos como variación total de $f$ y sus extensiones multivariantes razonables. El estadístico de Stanford Art Owen ha trabajado en esto utilizando técnicas aleatorias cuasi-Monte Carlo . El Monte Carlo regular permite estimar directamente la precisión de la integral, pero cada evaluación individual no es tan precisa. Cuasi-Monte Carlo produce estimaciones más precisas, pero es una técnica totalmente determinista, y como tal no permite estimar la varianza de su resultado. Mostró cómo combinar los dos enfoques, y su artículo es muy lúcido, así que no intentaré reproducirlo aquí.

Una lectura complementaria sería, por supuesto Niederreiter (1992) monografía.