Métodos de Monte Carlo (Implementações)

Autor: Ângelo Polotto – Aluno de Iniciação Científica

Professor orientador: Rafael Frigori Bertolini

Sumário

Introdução Limitações Exemplo 1 Implementação em Linguagem C Pré-Definições Cadeias de Markov Exemplo 2 Implementação em Linguagem C

Introdução:

O intuido da simulação de monte carlo é trabalhar com modelos (físicos e/ou matemáticos) que possuem, em alguma de suas definições, indeterminações, as quais são definidas aleatoriamente durante a simulação. Por exemplo, a posição espacial de uma molécula em um determinado instante de tempo, em um gás.

Um fato que vale ressaltar é que esse tipo de simulação é totalmente dependente dos pulsos de clock do computador, já que os números aleatórios são gerados dessa forma.

Apesar parecer estranho obtermos resultados conclusivos usando numeros aleatórios, nós conseguimos obtê-los tratando as sequências aleatórias por equações, seja ela de probabilidade ou de proporcionalidade.

Limitações

Nas simulações de Monte Carlo temos o problema de o valor estimado se aproximar muito lentamente do exato.

Esse fato acarreta um aumento muito grande do tempo execução para se conseguir pequenas diminuições no valor do erro.

Para determinados problemas podemos ter um tempo maior que 1000 anos!!!

Exemplo 1

Uma gama de problemas físicos podem ser resolvidos usando o Método de Monte Carlo. Podemos citar a estimativa de quanto tempo irá durar uma máquina sabendo apenas o tempo de duração das peças. Tabém é de grande importância a solução de problemas ligados à mecânica estatística.

A seguir será mostrado a implementação em linguagem C para encontrar a área de uma figura.

Problema da Área

Temos a área de um quadrado conhecido (em azul claro) e a de um desconhecido que desejamos descobrir a área:

Primeiramente dividiremos o quadrado em pequenos pedaços de forma que podemos sortear duas coordenadas em x e y:

Após o sorteio de cara coordenada, temos que contar a quantidade de coordenadas que está contida na figura que queremos descobrir a área e o numero de pontos total:

Com essas informações, vamos aplicar a seguinte relação de proporcionalidade (Regra de três):

ÁreaTotal⇔Número Total de PontosÁrea Desconhecida⇔NúmeroContidos

Resolvendo:

Área Desconhecida=ÁreaTotal∗NúmerosContidosNúmeroTotal de Pontos

Como consequência do fato de, muitas vezes, não conseguirmos preencher todos os pontos da área, já que isso tem um custo computacional muito grande, geramos sempre um erro estatístico junto com os nossos resultados.

Para o nosso exemplo anterior, temos que o erro é dado por:

σ=1/√Número deTotal de Pontos

Pela fómula anterior é fácil estimar que a diminuição do erro implica em um aumento significativo no número de pontos sorteados. Há uma relação quadrática entre ambos.

Essa análise de erro não se limita a esse exemplo, extende-se para todos problemas resolvidos com MC.

Isso é um fato de grande limitação no Método de Monte Carlo, já que, em certos casos, trazer o erro para um valor considerável custa um tempo de simulação muito grande.

Implementação em Linguagem C

O exemplo anterior foi implementado em linguagem C. O procedimento e a figura foram exatamente as mesmas descritas anteriormente.

As figuras foram desenhadas em uma matriz 300x400.

A toda a matriz foi preenchida com zero, sinalização de área fora da figura, e um, sinalização de área interna à figura.

Compilando o código, obtemos na saida :

Vale ressaltar que os valores obtidos para a Área da figura mudarão a cada execução do código.

Pré-Definições

Antes de iniciar com as Cadeias de Markov vale definir duas características importantes para funções aleatórias.

A primeira é o fato destas poderem ser contínuas, por exemplo, um termômetro que pudesse ser capaz de medir temperaturas em todos os periodos de tempo.

A segunda é o fato destas porderem ser discretas, por exemplo, um termômetro que medisse a temperatura de 10 em 10 minutos.

Cadeias de Markov

As cadeias de Markov são sistemas estocásticos em que o futuro depende somente do estado presente e não do passado

As Markovianas são válidas somente para: o parâmetro n é discreto (ex: tempo) o espaço de estados E é discreto (coleção de

estados possíveis) O espaço pode ser finito ou infinito e enumerável.

Vamos considerar o mesmo finito. O estado inicial do processo ou o espaço de

estados é conhecido.

Exemplo 2

Imaginemos uma cidade que possui somente três classes sociais (A, B e C), em que de tempos em tempos a probabilidade de alguém passar de uma classe para outra é constante e só depende da classe atual.

Para esse problema, consideraremos a seguintes matrizes:

Pinicial=[3 /84/81 /8 ] T=[1/ 2 1/ 4 0

1/ 2 1/ 2 1 /20 1/ 4 1 /2] Pfinal=[??? ]

Onde Pinicial é a distribuição da população entre as três classes inicialmente, T é a matriz de transição, ou seja, armazena a probabilidade de transição entre as classes, e Pfinal é a matriz a ser calcula.

Para impletar visualizar a mudança da distribuição da população entre as classes em cada preriodo de tempo, a matriz Pfinal ganhou uma dimensão a mais para armazenar os valores antigos.

Implementação em liguagem C

Compilando o código, obtemos na saida :

É de se observar que após um determinado tempo a os valores não se altera, ou seja, chegamos no ponto de equilíbrio da equação.

Algorítmo de Metrópolis

Em pendência.

Referências

Landau, David P. - Guide to Monte Carlo Simulations in Statistical Physics.

www.mec.ita.br/~denise/teaching/.../aula03-Cadeias_de_Markov.pdf - Instituto Tecnológico de Aeronáutica Divisão de Engenharia Mecânica-Aeronáutica MOQ-12 Cadeias de Markov, - acesso em 02/11/2011.

Santos, Reginaldo J. - Cadeias de Markov, Departamento de Matemática-ICEx, Universidade Federal de Minas Gerais.

www.nre.seed.pr.gov.br/curitiba/arquivos/File/CRTE/Math-crte.pdf - Utilizando o editor de fórmulas BrOffice.org Math – acesso em 03/11/2011.

pt.wikipedia.org/wiki/Cadeias_de_Markov – acesso em 03/11/2011.

Castro, J. - Linguagem C na Pratica