Departamento de Ciência da Computação - IME-USP
INSTITUTO DE GEOCIêNCIAS - SEGUNDO SEMESTRE DE 1998
Segundo Exercício-Programa
Data de entrega: até 02 de outubro de 1998
Prof. Ronaldo Fumio Hashimoto
O objetivo deste exercício-programa é estudar o Método Monte Carlo para o cálculo da integral de uma função f(x) qualquer.
O que queremos dizer por método Monte Carlo é fazer um experimento estatístico cujo valor esperado é o valor da integral (no nosso caso). O método que descrevemos a seguir se utiliza de um gerador de números aleatórios.
Suponha que queremos calcular a integral da função f(x) no intervalo entre
0 e K (o intervalo pode ser facilmente generalizado), o valor da integral
corresponde a área sob o gráfico da função, como mostra a figura abaixo.
Suponha ainda que os valores da função em [0,K] são menores ou iguais a um
valor conhecido, digamos M, e além disso que a função f(x) é positivo no
intervalo [0,K] (observe a figura acima).
A princípio é gerada aleatoriamente uma sequência (x1,y1),
(x2,y2), ... , (xn,yn) de pontos
onde 0 <= xi <= K e 0 <= yi <= M. É calculada então a proporção P de pontos que estão
entre a curva e o eixo das abscissas, i.e., a proporção de pontos tais que
0 <= yi <= f(xi). Pelo método Monte Carlo temos então que:
|
É intuitivo que quanto maior for o número de pontos gerados aleatoriamente mais o valor obtidos pelo método se aproximará do valor da integral (TESTE!!!).
A seguir é descrito como construir um gerador de números aleatórios.
A implementação de modelo de simulação em computador digital, normalmente, requer números aleatórios, com os quais é possível obter observações ao acesso que obedeçam determinadas distribuições de probabilidades.
Há um certo número de métodos para gerarmos números aleatórios, dentre os
quais de destaca o Método da congruência multiplicativo.
O método da congruência multiplicativo, proposto por D. W. Lehmer em 1951,
obtém o número inteiro aleatório xn+1 a partir do número inteiro
xn, mediante uma relação de recorrência do tipo
O primeiro número da sequência, x1, será obtido a partir de um inteiro
positivo qualquer, menor que m, escolhido como x0, e usando a relação
de recorrência (1).
Extensos testes estatísticos mostraram que a sequência gerada só será
satisfatória se forem escolhidos valores convenientes para k, m e
x0, e que apenas umas poucas combinações de k, m e x0 geram
sequências satisfatórias.
Uma dessas combinações é obtida tomando-se k = 455.470.314,
m = 2.147.483.647 e com x0 podendo ser qualquer inteiro entre 1 e
2.147.483.646. A sequência dos números assim gerados se repete em ciclos de
comprimento 2.147.483.646, o que não apresenta inconveniente pois a
quantidade de números aleatórios utilizada provavelmente será menor do que
essa. Cada inteiro gerado entre 1 e 2.147.483.646 aparece exatamente uma vez
em cada ciclo.
Assim sendo, se o computador necessita de números aleatórios de 4 dígitos
ele pode ser instruído para tomar, por exemplo, os últimos 4 dígitos (exceto
quanto aos números cujos dígitos procedentes sejam 214.748 que serão
rejeitados). Se desejamos números aleatórios entre zero e
um, podemos dividir, em ponto flutuante, cada número obtido por m, assim
gerando númeror reais (xn+1/m). Assim, podemos obter números
entre zero e uma constante T > 0 (real), simplesmente fazendo a operação
(xn+1/m)·T.
Tais números gerados em computador, sendo preditíveis e reprodutíveis, não
são exatamente aleatórios, sendo por isso denominados frequentemente de
pseudo-aleatórios.
Para armazenar valores inteiros maiores que 32.767 (o maior número inteiro
que podemos armazenar em uma variável tipo ``int'' no compilador QuickC é
32.767), vamos usar o tipo ``unsigned long int'' (que podem guardar
valores entre 0 e 4.294.967.295). Como exemplo, veja o seguinte programa em C:
# include <stdio.h>
void main (void) {
unsigned long int n, m;
int t;
double x;
n = 21483646;
m = 4836475;
t = 32000;
x = n*1.0/(m+t);
printf ("n = %ld e x = %lf\n", n, x);
}
Uma outra maneira de calcularmos uma aproximação para a integral de uma função f(x) em um intervalo [0,K] tal que f(x) >= 0 para todo x em [0,K] é através da seguinte somatória:
|
onde eps é um número real positivo ``pequeno'' (épsilon) e n é tal que n·eps <= K e (n+1)·eps > K (veja figura abaixo).
Observe que a precisão do resultado depende de eps, ou seja, quanto menor eps mais próximo estaremos do valor da integral.
Faça um programa em Linguagem C que leia:
e calcula uma aproximação da integral de f(x) = cos (x) entre 0 e K pelo método:
Para gerar os números aleatórios necessários ao método Monte Carlo, você deve usar OBRIGATORIAMENTE o método da congruência multiplicativo (descrito anteriormente) com valor inicial x0 (que deve ser lido). Utilize os últimos quatro dígitos de seu número USP para o valor de x0. Escolha um valor para n tal que o método de Monte Carlo de uma ``boa'' aproximação, utilizando o resultado do outro método (dos Retângulos) como referência.
Para o cálculo dos valores de cos(x), você deve usar OBRIGATORIAMENTE
a seguinte aproximação:
|
incluindo na soma todos os termos até que
|
Na Linguagem C, você pode escrever a constante 10-8 com 1E-8.
IMPORTANTE: Todo exercício-programa deve seguir as observações contidas no EP1. Nestas observações estão descritas as diretrizes para forma de entrega do exercício, aspectos importantes na avaliação, etc.
f(eps)·eps + f(2·eps)·eps +
··· +f(n·eps)·eps = eps
·[f(eps)+ f(2·eps)+ ··· +
f(n·eps) ]