BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI

Bounchanh NORHER

PHƯƠNG PHÁP MONTE-CARLO
VÀ ỨNG DỤNG TRONG BÀI TOÁN NỘI SUY
HÀM NHIỀU BIẾN.

LUẬN VĂN THẠC SĨ TOÁN HỌC

Hà Nội - 2016


BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI

Bounchanh NORHER

PHƯƠNG PHÁP MONTE-CARLO
VÀ ỨNG DỤNG TRONG BÀI TOÁN NỘI SUY
HÀM NHIỀU BIẾN.

Chuyên ngành

: Lý Thuyết Xác Suất và Thống kê Toán học

Mã số

: 60.46.01.06


1

1.2

Đại lượng ngẫu nhiên và các số đặc trưng . . . . . . . . . .

2

1.3

Vectơ ngẫu nhiên và sự độc lập của các đại lượng ngẫu nhiên

4

1.4

Sự hội tụ của dãy các đại lượng ngẫu nhiên . . . . . . . . .

4

1.4.1

Kì vọng, phương sai của biến ngẫu nhiên . . . . . .

4

1.4.2

Sự độc lập của các biến ngẫu nhiên . . . . . .



. . . . . . . . . . . . 11

2.3

Đại lượng ngẫu nhiên phân bố đều và sự mô hình hóa các
phép thử . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.4

2.3.1

Các phương pháp tạo ra số ngẫu nhiên . . . . . . . . 19

2.3.2

Thể hiện đại lượng ngẫu nhiên . . . . . . . . . . . . 26

Thể hiện các mô hình rời rạc . . . . . . . . . . . . . . . . . 31

i


Chương 3. Ứng dụng trong bài toán nội suy hàm nhiều biến 35
3.1

Nội suy hàm nhiều biến . . . . . . . . . . . . . . . . . . . . 35

Kết luận




Phần mở đầu
1. Lý do chọn đề tài
Phương pháp Monte-Carlo ra đời cùng thời với thế hệ máy tính điện tử
đầu tiên. Kể từ khi xuất hiện vào khoảng những năm 1950, phương pháp
Monte-Carlo đã được quan tâm nghiên cứu cả về lý thuyết và ứng dụng.
Phương pháp Monte-Carlo là hiệu quả cho những bài toán phức tạp có
khối lượng tính toán lớn mà không dễ dàng giải được các phương pháp
khác. Một trong các ứng dụng của phương pháp Monte-Carlo là giải bài
toán nội suy hàm nhiều biến. Về mong muốn tìm hiểu về phương pháp
Monte-Carlo, dưới sự hướng dẫn của TS Nguyễn Văn Khải, tôi nghiên cứu
đề tài “Phương pháp Monte-Carlo và ứng dụng trong bài toán nội suy hàm
nhiều biến”.
2. Mục đích nghiên cứu
Luận văn nghiên cứu về phương pháp Monte-Carlo và ứng dụng trong bài
toán nội suy hàm nhiều biến.
3. Nhiệm vụ nghiên cứu
Luận văn nghiên cứu một số kiến thức cơ sở trong lý thuyết xác suất và
thống kê toán học, về phương pháp Monte-Carlo (nội dung phương pháp,
sai số phương pháp và ứng dụng trong bài toán nội suy hàm nhiều biến ).
4. Đối tượng nghiên cứu
- Phương pháp Monte-Carlo và các vấn đề liên quan.
- Ứng dụng trong bài toán nội suy hàm nhiều biến.


5. Phương pháp nghiên cứu.
Phương pháp phân tích và tổng hợp các tài liệu đã có từ đó thống lại các
vấn về liên quan.
6. Luận văn có cấu trúc 3 chương:


∞

Ak ∈ F ,
k=1

Ak ∈ F .
k=1

Mỗi phần tử của F được gọi là một biến cố.
Định nghĩa 1.1.2. Giả sử F là σ - đại số các tập con của Ω .Ta gọi
P : F −→ [0, 1] là một độ đo xác suất nếu :
i). P(∅) = 0, P(Ω) = 1;
ii). Nếu A1 , A2 , ... ∈ F là các tập đôi một rời nhau trong F thì
∞

∞

Ak

P

=

k=1

P (Ak )
k=1

Điều này kéo theo rằng A1 , A2 ∈ F : A1 ⊆ A2 thì P (A1 ) ≤ P (A2 ).

Định nghĩa 1.2.1. Cho (Ω, F, P) là một không gian xác suất . Một ánh
xạ X : Ω −→ R được gọi là một biến ngẫu nhiên nếu B ∈ B (với B là
tập các tập con Borel của R) ta có X−1 (B) ∈ F . Khi đó ta nói X là

F - đo được.
Định nghĩa 1.2.2. Hàm phân phối xác suất của biến ngẫu nhiên X được
xác định theo công thức :

FX(x) = P {X ≤ x}, ∀ x ∈ R
Nếu hàm phân phối xác suất của biến ngẫu nhiên X có đạo hàm:

f (x) = F (x), ∀x ∈ R
thì ta gọi f (x) là hàm mật độ của X .

2


Định nghĩa 1.2.3. Biến ngẫu nhiên X có phân bố đều trên đoạn [a, b]
nếu hàm mật độ của nó có dạng :

 1
b−a
f (x) =
0

khi x ∈ [a, b]
khi x ∈
/ [a, b]

Kí hiệu X ∼ U ([a, b]).

X=

ai IAi
i=1

được gọi là một biến ngẫu nhiên đơn gản giá trị thực ( ai ∈ R). Ta có :
ˆ
k
X dP :=
ai P (Ai ).
Ω

i=1

Nếu X là một biến ngẫu nhiên không âm thì :
ˆ
ˆ
X dP := sup
Y dP
Y ≤X

Ω

Ω

3


1.3



ˆ

Khi đó :
E (X) :=

XdP
Ω

được gọi là giá trị trung bình hay kì vọng của X .
ˆ
D (X) := |X − E (X)|2 dP
Ω

được gọi là phương sai của X . Trường hợp biến ngẫu nhiên X có hàm
mật độ làf (x) thì kì vọng và phương sai được tính bằng công thức :
ˆ+∞
E (X) =
xf (x)dx
−∞

D (X) = E(X − E (X))2 = E(X)2 − (E (X))2 .

4


1.4.2

Sự độc lập của các biến ngẫu nhiên


F = B[0, 1]. Xét dãy biến ngẫu nhiên :

1

 n khi 0 ≤ ω ≤
n
Xn (ω) = n.1[0, 1 ] (ω) =
1
n

 0 khi ≤ ω ≤ 1
n
Ta có Xn (0) = n → +∞, Mặt khác với ω ∈ (0, 1), ta có Xn (ω) → 0, suy
h.c.c.

ra Xn → 0 khi n −→ +∞.
5


Định nghĩa 1.4.4. Dãy biến ngẫu nhiên (Xn ) được gọi là hội tụ theo
trung bình bình phương đến biến ngẫu nhiên X nếu :

lim E(|Xn − X|)2 = 0.

n→∞

Ta kí hiệu lim Xn = X .
n→∞

Định nghĩa 1.4.5. Dãy biến ngẫu nhiên (Xn ) được gọi là hội tụ theo xác


Nội dung phương pháp Monte-Carlo
Khái niệm về phương pháp Monte-Carlo

Tinh thần cơ bản của phương pháp Monte-Carlo là đặt một mối quan
hệ giữa bài toán bằng số với lược đồ xác suất nào đó. Nghĩa là cần chỉ ra
lời giải bằng số y của kì vọng E {ξ} của một đại lượng ngẫu nhiên ξ nào
đó (hoặc xác suất P(A) của biến ngẫu nhiên A nào đó).
Từ đó để tính giá trị của y về mặt thực hành ta lấy N giá trị của
đại lượng ngẫu nhiên ξ : ξ (1) , ..., ξ (N ) (N đủ lớn ), sau đó dùng giá trị
1 N (j)
ξ của chúng thay cho kỳ vọng E {ξ} = y . Nếu
trung bình ξ N =
N j=1
m
thay cho xác
y = P(A) thì làm N phép thử độc lập để lấy tần xuất
N
suất P(A) = y của biến cố ngẫu nhiên A, trong đó m là số lần xuất hiện
biến cố A trong N phép thử. Quan điểm cơ bản nói trên phương pháp
Monte-Carlo có thể minh họa một cách cụ thể hơn bằng các ví dụ sau đây:
Ví dụ 2.1.1. tính diện tích.
Một mảnh đất S ( có hình thù phức tạp ) nằm trên một khu đất hình
chữ nhật R với diện tích đã cho là mesR.
Để tính diện tích mesS của mảnh đất S , người ta tung ngẫu nhiên n
lần cùng một hòn sỏi trên khu đất R. Trong n lần tung có m lần hòn sỏi
rơi vào mảnh đất S .
Nếu gọi A là biến cố để hòn sỏi rơi vào mảnh đất S trong một lần tung
7


ngẫu nhiên một cái kim AB có độ dài là l (l < 1).
Tính xác suất P(Ω) của biến cố Ω để chiếc kim AB cắt một trong các
đường thẳng kẻ trên mặt bàn.
Giải : Để biểu diễn biến cố Ω ta gọi :

η - là khoảng cách từ trung điểm O của chiếc kim AB (đã rơi trên mặt
bàn sau khi tung ngẫu nhiên ) đến đường thẳng gần nhất trong các đường
đã kẻ.

ϕ - là góc nhỏ nhất trong các góc lập bởi kim AB với phương vuông góc
đối với các đường song song.
Ta nhận thấy rằng :
P (Ω) = P η ≤

l
cos ϕ .
2

khi đó các đại lượng biến thiên η, ϕ là các đại lượng ngẫu nhiên độc lập
1
π
và 0 ≤ η ≤ ; 0 ≤ ϕ ≤ .
2
2
π
Đại lượng ngẫu nhiên ϕ nhận các giá trị trên đoạn [0, ] một cách đồng
2
8



/ 0, π2

1
Tương tự đại lượng ngẫu nhiên x có phân phối đều trên đoạn [0, ] với
2
hàm mật độ có dạng :

1



2
khi
x
∈
0,


2

q (x) =



1


khi x ∈
/ 0,
0

trong đó G =

(x, y), 0 ≤ x ≤

9


ngược lại. Do đó :
π

P (Ω) =

S0
=
S

´2 1
cos ϕ dϕ
π 2
−
2

1
π
2

π

=


Một loại đối tượng khá quan trọng của phương pháp Monte-Carlo là
một số bài toán tất định có thể giải được bằng cách gắn các yếu tố ngẫu
nhiên của bài toán, nghĩa là xây dựng mô hình xác suất tương ứng với các
bài toán đã cho. Để sử dụng phương pháp Monte-Carlo vào mỗi bài toán
tất định trên, trước hết ta lập bài toán xác suất tương ứng mà lời giải y
của bài toán tất định xác định được từ lời giải x của bài toán xác suất bởi
một quan hệ hàm y = f (x) nào đó.

• Nội dung thứ hai.
Sau khi thiết lập bài toán xác suất tương ứng cho bài toán tất định, ta
cần giải đúng bài toán xác suất tương ứng trong mô hình thông qua các
phép thử ngẫu nhiên. Đây là quá trình thể hiện mô hình xác suất tương
ứng. Từ kết quả các phép thử có thể thiết lập đại lượng ngẫu nhiên X ∈ Rm
xấp xỉ với lời giải x ∈ Rm của mô hình xác suất. Nếu lời giải y ∈ Rn của
bài toán tất định được xác định từ x bởi quan hệ hàm y = f (x) với hàm f
liên tục thì ta có thể xấp xỉ nó bởi đại lượng ngẫu nhiên Y = f (X) ∈ Rn ,
nghĩa là :

X ≈ x ∈ Rm ; Y = f (X) ≈ f (x) = y ∈ Rn

10


trong đó Y, X được gọi là ước lượng Monte-Carlo đối với lời giải y, x của
lần lượt các bài toán tất định và bài toán xác suất tương ứng.

• Nội dung thứ ba.
Ứng dụng của phương pháp Monte-Carlo vào việc giải bằng số các bài
toán xác suất với các hiện tượng ngẫu nhiên không quan sát được như một
số bài toán quan trọng của lý thuyết thông tin, vật lý hật nhân...

(ξi − yi )2

∆ (ξ) := ξ − y =
i=1

.
11

(2.2)


Định nghĩa 2.2.2. Xấp xỉ ξ = ξN = (ξ1N , ..., ξnN ) đối với y ∈ Rn gọi là
ước lượng tiệm cận không chệch hay ước lượng hội tụ theo trung bình nếu :
n

lim E {ξN − y}

2

N →∞

|E {ξiN − yi }|2 = 0

= lim

N →∞

(2.3)

i=1

= lim E
N →∞

=0

(2.5)

i=1

Sai số của ước lượng hội tụ theo trung bình bình phương ξN đối với y
cho bởi hệ thức :

∆ (ξN ) := E

∆ (ξN )

2

1
2

1
2

n

(ξiN − yi )2

= E



(2.7)


Sai số của ước lượng vững ξN được hiểu là độ lệch ∆ (ξN ) của ξN .
Định nghĩa 2.2.5. Xấp xỉ ξ = ξN đối với y ∈ Rn gọi là ước lượng hội tụ
hầu chắc chắn, hay ước lượng hội với xác suất 1, nếu :
P

lim ξN − y = 0

N →∞

= 1.

(2.8)

Kí hiệu: ξN −→ y (h.c.c), N −→ ∞.
nghĩa là ∀ε > 0, ∃N0 = N0 (ε) sao cho : ∀N ≥ N0 (ε) ta có công thức đánh
giá sai số :
P { ∆ (ξN ) < ε} = 1

(2.9)

Sai số của ước lượng hội tụ hầu chắc chắn được hiểu là độ lệch ∆ (ξN )
của ξN . Theo nghĩa này, ta có thể sử dựng công thức (2.9) để đánh giá sai
số của ξN một cách hầu chắc chắn.
Bây giời ta xét một loại ước lượng không chệch khá phổ biến và quan
trọng trong những xấp xỉ đó là ước lượng thử thống kê theo nghĩa sau :
Định nghĩa 2.2.6. Giả sử ξ = (ξ1 , ..., ξn ) ∈ Rn là một vectơ ngẫu nhiên



∆ ξN

1
=
N

N

ξ

(j)

N

2  12

(j)
ξi − yi  

N

N −1


−y =

j=1



∆1 = E (ξ) − ξ N .

(2.14)

hoặc

m
N
Ta xét xem các sai số ∆1 , ∆2 phụ thuộc vào N như thế nào?
∆2 = P (A) −

(2.15)

Định lý 2.2.1. Giả sử ξ N là một ước lượng thử thống kê đối với y ∈ R1 ,
sao cho : E(ξ) = y, D(ξ) < +∞. Với N đủ lớn thì ta có thể đánh giá sai
số với E(ξ) theo quy tắc k − sigma sau :
P
trong đó : σ (ξ) =

kσ (η)
ξ N − E {η} < √
N

ˆk

≈
−k

−x2

lim FN (x) = F (x) :=

N →∞

−∞

−t2

e 2
√ dt.
2π

Trong đó F (x) là hàm phân phối của đại lượng ngẫu nhiên ζ có phân
phối chuẩn với kì vọng 0 và phương sai 1.
Với N đủ lớn ta có :
ˆk
P (|ζN | < k) = P (−k < ζN < k) = FN (k) − FN (−k) ≈
−k

−x2
2

e
√

2π

dx.

Khi đó, ta có :






ξ N − E {ξ} < k

D {ξ}
N

Ta được điều phải chứng minh.
Sử dụng công thức (2.19) cho k = 3 ta có :
ˆ3
P {|ζ| ≤ 3} ≈
−3

−x2

e 2
√ dx = 0, 997.
2π

Từ đó dựa trên (2.17) ta suy ra :
P

ξ N − E {ξ} ≤ 3
15

D {ξ}
N

lượng ngẫu nhiên ξ với ξ N = E {ξ} < +∞.
Ta có kì vọng và phương sai của mẫu lần lượt là :

1
ξ N :=
N
SN2

1
:=
N

N

ξ (j) ;

(2.21)

j=1
N

ξ (j) − ξ N

2

(2.22)

j=1

Ngoài ra phương sai của mẫu còn có dạng :

ξ (j) −
N

N

2

2

ξ (j) 
j=1

Ký hiệu :
2
SN

N

N
1
=
SN2 =
ξ (j) − ξ N
N −1
N − 1 j=1

2

(2.23)


1
Kξ K + ξ (K+1) ;
K +1
1
2
2
SK+1
=
K Sk2 + ξ K + ξ (K+1)
K +1
K +1 2
2
S K+1 =
SK+1
K
ξ K+1 =

(2.25)
2

2

− ξ K+1 ;

(2.26)
(2.27)

Chứng minh. Ta có :




2

2
+ ξ (K+1)  − ξ K+1

2
1
2
[K Sk2 + ξ K + ξ (K+1) ] − ξ K+1
K +1

2

Ta được biểu thức truy hồi thứ hai.
Cuối cùng khi thay công thức (2.23) N bởi K + 1 ta thu được biểu thức
truy hồi cuối cùng.
Khi đã cho kích thước N và tập hợp mẫu ξ (1) , ..., ξ (N ) , để xác định
2

ξ N có thể sử dụng các công thức truy hồi (2.25), (2.26), (2.27) với
K = 1, ..., N − 1, ξ 1 = ξ (1) , S12 = 0. Từ đó ta xác định gần đúng phương
sai :

D {ξ} ≈

2
SN

1

E {ξ} = 0 (1 − p) + 1 (p) = p,

(2.30)

D {ξ} = E ξ 2 − (E {ξ})2 = 02 (1 − p) + 12 (p) − p2 = p (1 − p) .
(2.31)
Nếu tiến hành N phép thử độc lập thì thu được N giá trị cụ thể của ξ
là ξ (1) , ..., ξ (N ) . Rõ rằng số lần xuất hiện biến cố A trong N phép thử trên
la

N

ξ (j) .

m=
j=1

Do đó giá trị trung bình của đại lượng ξ thu được sẽ là :

1
ξ= m=
N

n

ξ (j) =
j=1

m
.


(2.34)