Transcript MONTE CARLO NUMERICAL METHOD

MONTE CARLO
NUMERICAL METHOD
BY
A. Lecture KARRAR DH.
MOHAMMED
History of the Monte
Carlo Method
• The Monte Carlo name is
taken from the Monte Carlo,
the capital of Monaco which
was a center for gambling .
• Monte Carlo methods are used
in many different ways e.g. as a
technique of integration of a
function. One of this ways is:
The Monte Carlo method as a
numerical technique for
calculating the integral by using
sequences of random numbers.
• In mathematics, Monte Carlo
integration is numerical
integration using random
numbers. That is, Monte Carlo
integration methods are
algorithms for the approximate
evaluation of definite integrals,
usually multidimensional ones.
• The usual algorithms evaluate
the integrand at a regular grid.
Monte Carlo methods, however,
randomly choose the points at
which the integrand is
evaluated, informally, to
estimate the area of a domain D,
• First, pick a simple domain E
whose area is easily calculated
and which contains D.
• Now pick a sequence of random
points that fall within E.
• Some fraction of these points
will also fall within D.
• The area of D is then estimated
as this fraction multiplied by the
area of E.
• The traditional Monte Carlo
algorithm distributes the
evaluation points uniformly over
the integration region .
Why are Monte Carlo
techniques used ?
• Two of the main reasons why
we use Monte Carlo methods:
• their ant-aliasing properties,
and
• their ability to approximate
quickly an answer that would be
very time-consuming to find out.
• if we want to use a method to
determine the exact answer,
Monte Carlo method can be
used to simulate problems that
are too difficult and timeconsuming.
• An example is in the use of
Monte Carlo techniques in
integrating very complex
multidimensional integrals.
• This is a task that other
processes can not handle well,
but which Monte Carlo can.
• The first point refers to the fact
that since Monte Carlo methods
involve a random component in
the algorithm, then they go
some way to avoid the problems
of ant-aliasing (only for certain
applications).
• An example that was brought to
my attention was that of finding
the area of the black squares on
a chess board. Now, if I was
using an acceptance-rejection
method to attack this problem,
I should come out with a fair
approximation,
• Due to the fact that I would be
going to random points on the
chessboard, I will do the same
process by using an algorithm
that moved to a certain next
point in a set of distance away
and then continued to do this,
• thus not having any random
point selection, the potential
problem is that this person may
have a bad step size and may
over evaluate or under evaluate
the number of successful trials
he has, thus inevitably giving a
poor approximation.
• These are two solid reasons
why people use Monte Carlo
techniques. Other possible
reasons could include its ease
in simulating complex physical
systems in the fields of physics,
engineering and chemistry
Transformation
Function
• T : [c,d]
[0,1]
• is defined by :• T (x) =(x-c) / (d-c)
Generate a random number
x uniform in [X min,X max]:
• Step 1:
• A random number generated by
the following relation :• ni = (k*ni) mod m . such that
• ni: integer number
• k: multiplier number
• m: modulus number
• no : initial value
•
•
•
•
step 2:
ri = ni /m in[0,1] where
ni ={n1,n2 ,n3,………}
m: modulus
• step 3:
• Xi (random) =X min + ri * (X max
– X min)
Crude Monte Carlo
• We are going to use this technique to
solve the integral I.
• I=

d
c
f ( x)dx
• The method is that you take a number
N for random number where c ≤ xi ≤ d
then for all xi we find the function
• f (xi) .
• For the f(x) we sum all of these
values and divide by N to get the
mean value for the random
number. We then multiply this
value by the interval (b-a) to get
the integral by :
• I= 
ba
n
n
*  f ( xi)
i 1
EXAMPLE :
• Solve the following integral by
using Monte Carlo method
3
• I=
 sin(x)dx
1
• Solution:- we use the previous
steps to get the solution
Step 1:-
let no=1,k=3,m=7
• We compute the random
numbers (n) as follows:•
•
•
•
•
ni=k * (ni-1) mod 7
n1=(3*1) mod 7 =3
n2=(3*3) mod 7 =2
n3=(3*2) mod 7 =6
n4=(3*6) mod 7 =4
• n5= (3*4) mod 7 =5
• n6= (3*5) mod 7 =1
• n7= (3*1) mod 7 =3 ... Stop
• Number of random m-1=7-1=6
Step 2:-by the following
we shall compute ri
ri=ni/m
r1=3/7=0.42
r2=2/7=0.28
r3=6/7=0.85
r4=4/7=0.57
r5=5/7=0.71
r6=1/7=0.14
Step 3:-now we shall compute
xi as following
• Xi= xmin+ri(xmax-xmin)
•
•
•
•
•
•
X1=1+0.42(2)=1.84
X2=1+0.28(2)=1.56
X3=1+0.85(2)=2.7
X4=1+0.57(2)=2.14
X5=1+0.71(2)=2.42
X6=1+0.44(2)=1.28
Ni
1
2
3
4
5
6
ri
0.42
0.28
0.85
0.57
0.71
0.14
xi
1.84
1.56
2.7
2.14
2.42
1.28
F(xi)=sin(xi)
0.032
0.027
0.047
0.0373
0.0422
0.0233
 f (x)  0.2078
• I=
ba n

 *  f ( xi)
 n  i 1
• I= (1/6)*(0.207)=0.0345
Example:
• Solve the following integral by using
Monte Carlo method
• I=
3
x
e
 dx
1
• Solution:- we use the same steps in
the previous example to get the
solution
Step 1:-
let no=1,k=3,m=7
• We compute the random
numbers (n) as follows:•
•
•
•
•
ni=k * (ni-1) mod 7
n1=(3*1) mod 7 =3
n2=(3*3) mod 7 =2
n3=(3*2) mod 7 =6
n4=(3*6) mod 7 =4
• n5= (3*4) mod 7 =5
• n6= (3*5) mod 7 =1
• n7= (3*1) mod 7 =3 ... Stop
• Number of random
• n5= (3*4) mod 7 =5
• n6= (3*5) mod 7 =1
• n7= (3*1) mod 7 =3 ... Stop
• Number of random m-1=7-1=6
Step 2:-by the following
we shall compute ri
ri=ni/m
r1=3/7=0.42
r2=2/7=0.28
r3=6/7=0.85
r4=4/7=0.57
r5=5/7=0.71
r6=1/7=0.14
Step 3:-now we shall
compute xi as follows
• Xi= xmin+ri(xmax-xmin)
•
•
•
•
•
•
X1=1+0.42(2)=1.84
X2=1+0.28(2)=1.56
X3=1+0.85(2)=2.7
X4=1+0.57(2)=2.14
X5=1+0.71(2)=2.42
X6=1+0.44(2)=1.28
Ni
1
2
3
4
5
6
ri
0.42
0.28
0.85
0.57
0.71
0.14
xi
1.84
1.56
2.7
2.14
2.42
1.28
F(xi)=exi
6.296
4.7588
14.879
8.4994
11.2458
3.5966
 f (x)  49.277
ba n
 *  f ( xi)
• I= 
 n  i 1
• I= (1/6)*(49.277) =8.2128
The Monte Carlo method
program by MATLAB
•
•
•
•
•
•
•
•
•
•
•
•
•
clc
clear
c=input('please enter the lower bound of interval i.e c =')
d=input('please enter the upper bound of interval i.e d =')
m=input('please enter the modulus number i.e m =')
n=m-1;
trans_fun(c,d)
a=0;
b=1;
s=0;
z=1;
h=(b-a)/n;
k=0;
• while k<n
•
p=3*z;
•
q=mod(p,m);
•
z=q;
•
r=q/m;
•
x=c+(r*(d-c));
•
f=sind(x);
•
s=s+f;
•
y=h*s;
•
k=k+1;
• end
• y
The transformation
function program
• function [g] = trans_fun(a,b)
• if (a~=0)&&(b~=1)
• w=input('please enter the number of intervals
points you wont to convert it w = ')
• for v = 1:w
• x=input('please enter the point of interval you
want to convert it x = ')
• g =(x-a)/(b-a)
• end
• disp('the original interval convert to a=0 & b=1')
• else
• disp('already a=0 & b=1')
• end