Документ взят из кэша поисковой машины. Адрес оригинального документа : http://acat02.sinp.msu.ru/presentations/tobimatsu/tobimatsuk.pdf Дата изменения: Tue Jul 2 18:04:20 2002 Дата индексирования: Mon Oct 1 20:27:44 2012 Кодировка:

A new Monte Carlo method of the numerical integration

"Superposing Method"
T.Kaneko and K.Tobimatsu * KEK, Tsukuba Japan *Kogakuin University, Tokyo Japan


1. Basic idea
Division method

Random Sampling

Superposing method

Regions are deterministic
ACAT2002 in Moscow, Superposing method TK & KT

Regions are randomly taken
2


The method is more flexible than usual division method in choosing a shape for sub -region. The shape can be changed for each level . level 1 level 2 etc. heigher levels

singularity

level1

level2

ACAT2002 in Moscow, Superposing method

TK & KT

3


2. General Formulation
NaОve MonteCarlo
S : Integration volume N:Number of samplings

I=



S

S f ( x ) dx = N


i =1

N

f ( xi )

We extend the above expression. 1. Formally we enlarge the integration volume beyond S. 2. Introduce a probability distribution as a weight , t ( x), x R

n



d n xt ( x) = 1

For example, we consider a region ,' which include the origin of coordinate axes inside and whose volume is T. t(x) takes a constant value 1/T in the region and takes a zero value outside.

1 / T t ( x) = 0
ACAT2002 in Moscow, Superposing method

xr otherwise
TK & KT 4


We multiply "1" on the integral I

I = d n xf ( x )
n

= d xf ( x ) d zt ( z )
n

Changing the variables (x,z) into (y,x) where z=y-x, we have
Master Formula ·F

I = d n y d n xf ( x)t ( y - x)

We apply Monte Calro method to the last expression : 1. A y value is randomly chosen then t(y-x) is a function of x. 2. The meaning of x integration is to compute the average of f(x) around y using the probability distribution t(y-x). 3. We take many sampling for y. For each y, we have average value of f(x) by the distribution t(y-x) and finally we obtain the average of each estimate.
ACAT2002 in Moscow, Superposing method TK & KT 5


Examples of t(y)
(1-dimension)
A range of ў

1 t ( y ) = ( - | y |) 2
1 1 2 t ( y1 , y2 ) = ( - | y1 |) ( - | y 2 |) 1 2 2 2 4 2 t ( y1 , y2 ) = 2 ( - y12 + y2 ) 2

(2-dimension)
A rectangle

A circle

An ellipse and the other shapes are , in principle, OK.

ACAT2002 in Moscow, Superposing method

TK & KT

6


3. An example of 1-dim. integration
I=



+

-

dx f ( x ) =



+

-

dy J ( y )

Jў ) is the average of f(x) over the range of ўaround y, (y

1 J (y)



2 y- 2 y+

dxf ( x )

When the integration range is finite, i.e., step functions in the integrand:

I=

f ( x) f ( x) (b - x) ( x - a)



b

a

dxf ( x )
2 a- 2 b+

, we introduce

I = (b - a + ) J
ACAT2002 in Moscow, Superposing method

1 J= b-a+
TK & KT



dy J ( y )
7


I = (b - a + ) J

1 J= b-a+



2 a- 2 b+

dy J ( y )

J ( y)



b

a

dxf ( x )

, a = y - , b = y + 2 2

Recursive Method

J ( y ) = (b - a + ) J b + 1 2 J= dz J ( z ) - a + a - 2 b 1 z+ 2 J ( z ) z - 2 dxf ( x )
ACAT2002 in Moscow, Superposing method TK & KT 8


We introduce g(y)>0, which is a probability distribution function.

1 J= b-a+
1 b-a+



2 a- 2 b+

1 dy g ( y )
1 M


M

2 y- 2 y+

f (x) dx g ( y)
MN N



2 a- 2 b+

dy g ( y ) = 1


j =1

g( y j ) = 1 g( y j )
N
j

j

1 J= M



M

j =1

g ( y j )J

j

1 Jj = N

j k =1



f ( xk ) g(yj )


j =1
j

M

Nj = N

M:Number of samplings for dy integration Nj:Number of samplings for dx integration around y
ACAT2002 in Moscow, Superposing method TK & KT

9


I3 =



1

1

1

-1 - 1 -1

dx 1dx 2 dx

3

r (1 - r ) (r 2 - a 2 )2 +
2

r=
2

2 x12 + x 2 + x

2 3

= 10

-5

a = 0 .8
High Pink

Low Lightblue

Sampling density distribution
ACAT2002 in Moscow, Superposing method TK & KT 10

Density


I3 =



1

1

1

-1 -1 -1

r (1 - r 2 ) dx1dx2 dx3 2 (r - a 2 )2 +

2

2 2 r = x12 + x2 + x3 = 10 -5 a = 0.8

Only Level 1 calculation

ACAT2002 in Moscow, Superposing method

Relative accuracy # of samplings
TK & KT 11


4. Use of the singularity information
We assume that a ridge of the integrand is parameterized by a fu nction t ( s ), s R. w( x) is a probability distribution function.
n

f ( x) = d xw ( x - t ) w( x - t ) 1m f ( x) n = d s d xw( x - t ( s)) S w( x - t (s))
n

I = d n xf ( x)

s

Volume of parameter space For example, w could be a Normal Distribution. xk 2 m is the freedom of the singularity. -2
I = d n xf ( x)

w( x ) =
ACAT2002 in Moscow, Superposing method

n

e



k

k =1

We concentrate samplings around the singular region.
TK & KT

2

k

Circular Singularity
12


We use random numbers of the Normal distribution.

1 f ( x) m n I = d s d xw( x - t ( s)) S w( x - t ( s))
Denominator becomes very small far from x= t(s). We add a uniform distribution w0.

1 w

W (x - t ( s) ) = w(x - t ( s) ) + (1 - )w0 (x - t ( s)
w : normal distribution w0 : uniform distribution

)

x = t ( s)


1 -
)
13

1 f ( x) m n I = d s d xW ( x - t ( s)) S W ( x - t (s )) 1 f ( x) f (x m n n = d s d xw + (1 - ) d xw0 S W W
ACAT2002 in Moscow, Superposing method TK & KT


I2 =



1

1

-1 -1

x (1 - r ) dx1dx2 2 (r - a 2 ) 2 +
2 2 2

2

2 r = x12 + x2 = 10 -4 a = 0.5 i =

= 0.0 = 0 .5

ACAT2002 in Moscow, Superposing method

Relative accuracy # of samplings
TK & KT 14


Summary
· We proposed a new Monte Carlo integration method in which sub-regions are randomly taken. · We proposed a method of using the singularity information when the location can be parameterized. · We are developing an integration program which uses the methods.
ACAT2002 in Moscow, Superposing method TK & KT 15