stringtranslate.com

Integración de Montecarlo

Una ilustración de la integración de Montecarlo. En este ejemplo, el dominio D es el círculo interior y el dominio E es el cuadrado. Debido a que el área del cuadrado (4) se puede calcular fácilmente, el área del círculo (π*1,0 2 ) se puede estimar mediante la relación (0,8) de los puntos dentro del círculo (40) con respecto al número total de puntos (50). , produciendo una aproximación para el área del círculo de 4*0,8 = 3,2 ≈ π.

En matemáticas , la integración de Monte Carlo es una técnica de integración numérica utilizando números aleatorios . Es un método particular de Monte Carlo que calcula numéricamente una integral definida . Mientras que otros algoritmos suelen evaluar el integrando en una cuadrícula regular, [1] Monte Carlo elige aleatoriamente puntos en los que se evalúa el integrando. [2] Este método es particularmente útil para integrales de dimensiones superiores. [3]

Existen diferentes métodos para realizar una integración de Monte Carlo, como el muestreo uniforme , el muestreo estratificado , el muestreo de importancia , el Monte Carlo secuencial (también conocido como filtro de partículas) y los métodos de partículas de campo medio .

Descripción general

En la integración numérica, métodos como la regla trapezoidal utilizan un enfoque determinista . La integración de Monte Carlo, por otra parte, emplea un enfoque no determinista : cada realización proporciona un resultado diferente. En Montecarlo, el resultado final es una aproximación del valor correcto con las respectivas barras de error, y es probable que el valor correcto esté dentro de esas barras de error.

El problema que aborda la integración de Monte Carlo es el cálculo de una integral definida multidimensional donde Ω, un subconjunto de , tiene volumen

El enfoque ingenuo de Monte Carlo consiste en muestrear puntos uniformemente en Ω: [4] dadas N muestras uniformes,

puedo ser aproximado por

Esto se debe a que la ley de los grandes números asegura que

Dada la estimación de I a partir de Q N , las barras de error de Q N pueden estimarse mediante la varianza muestral utilizando la estimación insesgada de la varianza .

lo que lleva a

Mientras la secuencia esté acotada, esta varianza disminuye asintóticamente a cero como 1/ N . La estimación del error de Q N es entonces que disminuye a medida que . Este es el error estándar de la media multiplicada por . Este resultado no depende del número de dimensiones de la integral, que es la ventaja prometida de la integración de Monte Carlo frente a la mayoría de los métodos deterministas que dependen exponencialmente de la dimensión. [5] Es importante señalar que, a diferencia de los métodos deterministas, la estimación del error no es un límite de error estricto; Es posible que el muestreo aleatorio no descubra todas las características importantes del integrando que pueden dar lugar a una subestimación del error.

Si bien el ingenuo Monte Carlo funciona con ejemplos simples, una mejora con respecto a los algoritmos deterministas solo se puede lograr con algoritmos que utilicen distribuciones de muestreo específicas del problema. Con una distribución muestral adecuada es posible explotar el hecho de que casi todos los integrandos de dimensiones superiores están muy localizados y sólo un subespacio pequeño contribuye notablemente a la integral. [6] Gran parte de la literatura de Monte Carlo está dedicada a desarrollar estrategias para mejorar las estimaciones de error. En particular, el muestreo estratificado (que divide la región en subdominios) y el muestreo de importancia (muestreo a partir de distribuciones no uniformes) son dos ejemplos de tales técnicas.

Ejemplo

Error relativo en función del número de muestras, mostrando la escala.

Un ejemplo paradigmático de integración de Monte Carlo es la estimación de π. Considere la función y el conjunto Ω = [−1,1] × [−1,1] con V = 4. Observe que

Por tanto, una forma sencilla de calcular el valor de π con integración de Monte Carlo es elegir N números aleatorios en Ω y calcular

En la figura de la derecha, el error relativo se mide en función de N , confirmando el .

ejemplo C

Tenga en cuenta que se debe utilizar un verdadero generador de números aleatorios.

int i , lanza = 99999 , insideCircle = 0 ; doble randX , randY , pi ;          srand ( hora ( NULL ));for ( i = 0 ; i < throws ; ++ i ) { randX = rand () / ( doble ) RAND_MAX ; randY = rand () / ( doble ) RAND_MAX ; if ( randX * randX + randY * randY < 1 ) ++ insideCircle ; }                               pi = 4.0 * círculo interior / tiros ;      

Ejemplo de Python

Hecho en Python .

de  numpy  importación  aleatoriathrows  =  2000 inside_circle  =  0 i  =  0 radio  =  1 mientras  i  <  throws :  # Elija X e Y aleatorios centrados alrededor de 0,0  x  =  aleatorio . uniforme ( -radio , radio ) y = aleatorio .uniforme ( -radio , radio ) # Si el punto está dentro del círculo, aumenta la variable si x ** 2 + y ** 2 <= radio ** 2 : círculo_interior += 1 i += 1                  # Calcular el área e imprimir; debería estar más cerca de Pi con un número creciente de lanzamientos área  =  ((( 2  *  radio )  **  2 )  *  inside_circle )  /  throws print ( área )

Ejemplo de Wolfram Mathematica

El siguiente código describe un proceso de integración de la función utilizando el método Monte-Carlo en Mathematica :

func [ x_ ] := 1 / ( 1 + Sinh [ 2 * x ] * ( Iniciar sesión [ x ]) ^ 2 );    (*Muestra de distribución normal truncada para acelerar la convergencia*) Distrib [ x_ , promedio_ , var_ ] := PDF [ NormalDistribution [ promedio , var ], 1.1 * x - 0.1 ]; norte = 10 ; RV = VariaciónAleatoria [ Distribución Truncada [{ 0,8 , 3 }, Distribución Normal [ 1 , 0,399 ]], n ]; Int = 1 / n Total [ func [ RV ] / Distrib [ RV , 1 , 0.399 ]] * Integrar [ Distrib [ x , 1 , 0.399 ], { x , 0.8 , 3 }]                          NIntegrate [ func [ x ], { x , 0.8 , 3 }] (*Comparar con la respuesta real*)    

Muestreo estratificado recursivo

Una ilustración del muestreo estratificado recursivo. En este ejemplo, la función: de la ilustración anterior se integró dentro de un cuadrado unitario utilizando el algoritmo sugerido. Los puntos muestreados fueron registrados y trazados. El algoritmo de muestreo claramente estratificado concentra los puntos en las regiones donde la variación de la función es mayor.

El muestreo estratificado recursivo es una generalización de cuadraturas adaptativas unidimensionales a integrales multidimensionales. En cada paso de recursión, la integral y el error se estiman utilizando un algoritmo de Monte Carlo simple. Si la estimación del error es mayor que la precisión requerida, el volumen de integración se divide en subvolúmenes y el procedimiento se aplica recursivamente a los subvolúmenes.

La estrategia ordinaria de "dividir entre dos" no funciona para múltiples dimensiones, ya que el número de subvolúmenes crece demasiado rápido como para realizar un seguimiento. En lugar de ello, se estima en qué dimensión una subdivisión debería generar mayores dividendos y sólo se subdivide el volumen a lo largo de esta dimensión.

El algoritmo de muestreo estratificado concentra los puntos de muestreo en las regiones donde la varianza de la función es mayor, reduciendo así la gran varianza y haciendo que el muestreo sea más efectivo, como se muestra en la ilustración.

La popular rutina MISER implementa un algoritmo similar.

MISER Montecarlo

El algoritmo MISER se basa en un muestreo estratificado recursivo . Esta técnica tiene como objetivo reducir el error de integración general concentrando los puntos de integración en las regiones de mayor varianza. [7]

La idea del muestreo estratificado comienza con la observación de que para dos regiones disjuntas a y b con estimaciones de Monte Carlo de la integral y y varianzas y , la varianza Var( f ) de la estimación combinada está dada por,

Se puede demostrar que esta varianza se minimiza distribuyendo los puntos de manera que,

Por lo tanto, la estimación del error más pequeña se obtiene asignando puntos muestrales en proporción a la desviación estándar de la función en cada subregión.

El algoritmo MISER procede dividiendo la región de integración a lo largo de un eje de coordenadas para dar dos subregiones en cada paso. La dirección se elige examinando todas las d posibles bisecciones y seleccionando la que minimice la varianza combinada de las dos subregiones. La varianza en las subregiones se estima mediante muestreo con una fracción del número total de puntos disponibles para el paso actual. Luego se repite el mismo procedimiento de forma recursiva para cada uno de los dos semiespacios de la mejor bisección. Los puntos de muestra restantes se asignan a las subregiones utilizando la fórmula para Na y N b . Esta asignación recursiva de puntos de integración continúa hasta una profundidad especificada por el usuario donde cada subregión se integra utilizando una estimación simple de Monte Carlo. Estos valores individuales y sus estimaciones de error se combinan luego para dar un resultado general y una estimación de su error.

Muestreo de importancia

Hay una variedad de algoritmos de muestreo de importancia, como

Algoritmo de muestreo de importancia

El muestreo de importancia proporciona una herramienta muy importante para realizar la integración Monte-Carlo. [3] [8] El principal resultado del muestreo de importancia para este método es que el muestreo uniforme es un caso particular de una elección más genérica, en la que las muestras se extraen de cualquier distribución . La idea es que se pueda elegir disminuir la varianza de la medida Q N .

Considere el siguiente ejemplo en el que a uno le gustaría integrar numéricamente una función gaussiana, centrada en 0, con σ = 1, de −1000 a 1000. Naturalmente, si las muestras se extraen uniformemente en el intervalo [−1000, 1000], sólo una una parte muy pequeña de ellos sería significativa para la integral. Esto se puede mejorar eligiendo una distribución diferente a la que se eligen las muestras, por ejemplo, muestreando según una distribución gaussiana centrada en 0, con σ = 1. Por supuesto, la elección "correcta" depende en gran medida del integrando.

Formalmente, dado un conjunto de muestras elegidas de una distribución, el estimador de I viene dado por [3]

Intuitivamente, esto significa que si elegimos una muestra particular el doble que otras muestras, la ponderamos la mitad que las otras muestras. Este estimador es naturalmente válido para muestreo uniforme, caso en el que es constante.

El algoritmo de Metropolis-Hastings es uno de los algoritmos más utilizados para generar a partir de , [3], proporcionando así una forma eficiente de calcular integrales.

VEGAS Montecarlo

El algoritmo VEGAS se aproxima a la distribución exacta realizando una serie de pasadas sobre la región de integración que crea el histograma de la función f . Cada histograma se utiliza para definir una distribución de muestreo para el siguiente pase. Asintóticamente este procedimiento converge a la distribución deseada. [9] Para evitar que el número de contenedores del histograma crezca como K d , la distribución de probabilidad se aproxima mediante una función separable: de modo que el número de contenedores requeridos sea solo Kd . Esto equivale a localizar los picos de la función a partir de las proyecciones del integrando sobre los ejes de coordenadas. La eficiencia de VEGAS depende de la validez de esta suposición. Es más eficaz cuando los picos del integrando están bien localizados. Si un integrando se puede reescribir en una forma que sea aproximadamente separable, esto aumentará la eficiencia de la integración con VEGAS. VEGAS incorpora una serie de características adicionales y combina muestreo estratificado y muestreo de importancia. [9]

Ver también

Notas

  1. ^ Prensa y col. 2007, cap. 4
  2. ^ Prensa y col. 2007, cap. 7
  3. ^ abcd Newman y Barkema 1999, cap. 2
  4. ^ Newman y Barkema 1999, cap. 1
  5. ^ Prensa y col. 2007
  6. ^ MacKay 2003, págs. 284-292
  7. ^ Press y Farrar 1990, págs. 190-195
  8. ^ Kroese, Taimre y Botev 2011
  9. ^ ab Lepage 1978

Referencias

enlaces externos