ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
------------------

NGUYỄN TIẾN ĐÀ

CÁC PHƯƠNG PHÁP TÍNH TÍCH PHÂN GẦN ĐÚNG
CHO HÀM SỐ CÓ SỐ BIẾN RẤT LỚN
VÀ ỨNG DỤNG TRONG TÀI CHÍNH

Chuyên ngành : TOÁN GIẢI TÍCH
Mã số
: 60 46 01 02

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

NGƯỜI HƯỚNG DẪN KHOA HỌC:
GS. TSKH. ĐINH DŨNG

HÀ NỘI - Năm 2013


Mục lục
Lời nói đầu

2

1 CÁC PHƯƠNG PHÁP TÍNH TÍCH PHÂN CÓ SỐ CHIỀU RẤT
LỚN
1.1 Phân rã ANOVA . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.1 Phân rã ANOVA cổ điển . . . . . . . . . . . . . . . . . . . . .

3.2.1 Mô hình bài toán . . . . . . . . . . . . . . .
3.2.2 Số chiều hiệu dụng . . . . . . . . . . . . . .
3.2.3 Sai số và chi phí tích phân . . . . . . . . . .
3.3 Trái phiếu lãi suất không . . . . . . . . . . . . . . .
3.3.1 Mô hình bài toán . . . . . . . . . . . . . . .
3.3.2 Số chiều hiệu dụng . . . . . . . . . . . . . .
1

KẾT QUẢ SỐ
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .

33
33
34
34
35
36
37
38
39

.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.

.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

42
43
44
45
45

Kết luận

toán như thế được gọi là không khả thi. Tuy nhiên nhiều bài toán ứng dụng đôi khi
lại xuất hiện trong lớp bài toán nhỏ hơn có thể là khả thi, thêm vào đó có thể tồn
tại thuật toán có thể phá vỡ thảm họa của số chiều, thuật toán ngẫu nhiên Monte
Carlo (MC) là một trong những thuật toán có dạng như thế. Mặc dù tốc độ hội
tụ của nó là khá thấp và phải sử dụng một số lượng tương đối lớn các điểm đánh
giá. Sau đó phương pháp tựa Monte Carlo (QMC) được thay thế cho phương pháp
Monte Carlo, phương pháp này có thể giành được tốc độ hội tụ nhanh hơn. Sai số

2


của phương pháp này có thể đạt được là ε(n) = O(n−1 (log n)d ) cho các hàm dưới
dấu tích phân có phương sai bị chặn .
Với nhiều bài toán trong tài chính, các chuyên gia lý thuyết số đã chứng minh
rằng phương pháp tựa Monte Carlo hội tụ gần như độc lập với số chiều, đồng thời
nhanh hơn và chính xác hơn phương pháp Monte Carlo.
Với những hàm đủ trơn, những kết quả tương tự có thể tìm thấy cho phương
pháp tính tích phân trên lưới thưa. Một sự giải thích cho sự thành công của phương
pháp này là dựa trên sự phân tích của phân rã phương sai gọi tắt là ANOVA. Trong
luận văn, tác giả trình bày lại một số phương pháp tính tích phân gần đúng cho hàm
số có số chiều rất lớn dựa theo nội dung của bài báo: Michael Griebel, Markus Holtz,
"Dimension - wise integration of high - dimensional functions with applications to
finance", Journal of Complexity 26 (2010), pp. 455 - 489. Đồng thời cũng dựa theo
nội dung của bài báo này tác giả cũng đưa ra một vài kết quả số quan trọng và
một số ứng dụng trong tài chính. Cụ thể là, phương pháp tính tích phân được xây
dựng trên cơ sở của sự chặt cụt và sự rời rạc hóa của phân rã ANOVA có điểm neo.
Những phương pháp này được thiết lập nhằm khai thác số chiều hiệu dụng thấp
của hàm dưới dấu tích phân mà ở đó phương pháp lưới thưa là một trường hợp đặc
biệt. Hơn nữa những phương pháp này có thể được áp dụng theo cách thích nghi
theo số chiều và thích nghi địa phương. Hiệu quả của chúng được kiểm tra bởi các

cảm ơn!
Hà Nội, ngày 28 tháng 10 năm 2013
Tác giả
Nguyễn Tiến Đà

4


Chương 1
CÁC PHƯƠNG PHÁP TÍNH TÍCH PHÂN CÓ SỐ CHIỀU RẤT LỚN

1.1

Phân rã ANOVA

Trong mục này chúng ta sẽ giới thiệu phép phân tích phương sai cổ điển (ANOVA
cổ điển) và phép phân tích phương sai có điểm neo (ANOVA có điểm neo) của hàm
nhiều biến f . Dựa trên những phân rã này, chúng ta sẽ định nghĩa những khái niệm
khác nhau về số chiều hiệu dụng của f . Để bắt đầu, cho Ωd ⊆ Rd là tập xác định
của f và giả sử dµ(x) =

n
∏

dµj (x) là kí hiệu của tích các độ đo được định nghĩa

j=0

trên tập con Borel của Ωd . Ở đây x = (x1 , . . . , xd ) và µj với j = 1, 2, ..., d là các độ
đo trên Ω. Với

của x mà chỉ số của nó thuộc u và dµD\u (x) :=

5

∏

j̸∈u

dµj (xj ).


Phép chiếu này định nghĩa một phân rã f ∈ V (d) thành tổng hữu hạn
f (x1 , . . . , xd ) = f0 +

d
∑

d
∑

fj1 (xj1 ) +

j1

fj1 ,j2 (xj1 , xj2 ) + ... + fj1 ,...,jd (xj1 , ..., xjd ).

j1
hay một ví dụ khác cho độ đo Dirac đặt tại a ∈ Ω1 với dµ(x) = δ(x − a)dx là

∫

P f (x) =

f (x)dx = f (a).
Ω1

Điều này dẫn đến phân rã
f (x) = f0 + f1 (x),

∫

trong đó

f (x)dµ(x) ∈ Span {1}

f0 = P f (x) =
Ω1

∫

và
f1 (x) = (I − P )f (x) = f (x) −

f (x)dµ(x) ∈ W.
Ω1

6

d
1
f1 (x1 ) = (b + )(x1 − ),
2
2
d
1
f2 (x2 ) = (c + )(x2 − ),
2
2
d
f1,2 (x1 x2 ) = (2x1 − 1)(2x2 − 1).
4
f0 = a +

Nếu ta chọn a = 0; b = 12; c = 6; d = −6 thì
f (x) = f (x1 , x2 ) = 12x1 + 6x2 − 6x1 x2 ,
15
f0 =
,
2
9
f1 (x1 ) = 9x1 − ,
2
3
f2 (x2 ) = 3x2 − ,
2
3
f1,2 (x1 , x2 ) = 3x1 + 3x2 − 6x1 x2 − .
2

(1j ⊗ Wj )

j=1

Ở đây với 1j = 1; Wj = W , chúng ta có một công thức biểu diễn tường minh

⊕

V (d) =

Wu .

u⊆{1,...,d}

Khi đó
f (x) =

∑

fu (xu ) với fu ∈ Wu , xu = (xi1 , ..., xi|u| ) và i1 , ..., i|u| ∈ u

(3)

u⊆D

được gọi là một phân rã ANOVA của hàm d - chiều.
Ở đây trong (3) có 2d số hạng, trong đó mỗi số hạng fu mô tả sự phụ thuộc của f
vào u với độ đo µ. Chúng được định nghĩa tường minh
fu (xu ) := Pu f (xu ) −


∫

gj (x)dx và σ 2 (gi ) :=

[0,1]

∫

(Igj − gj (x))2 dx. Xét các hàm cộng và nhân thuần túy

[0,1]

+

f (x) :=

d
∑

∗

gj (xj ) và f (x) =

i=1

i=1

Bằng các phép tính đơn giản ta thu được
If


Đồng thời,
∗

If =

d
∏

Igj ,

i=1
2

∗

σ (f ) =

d
∏

(I 2 (gj ) + σ 2 (gj )) − I 2 f ∗ .

i=1

Hơn thế nữa các số hạng trong phân hoạch và phương sai của nó được tính tường
minh như sau
fu+ (xu )

σ


fu∗ (xu ) =

1.1.1

∏

∏

j∈u

j̸∈u

(gj (xj ) − Igj )

Igj và σ 2 (fu∗ ) =

∏
j∈u

σ 2 (gj )

∏

I 2 gj .

j̸∈u

Phân rã ANOVA cổ điển

Trước hết ta sử dụng kí hiệu xu = (xi1 , ..., xi|u| ) với i1 , ..., i|u| ∈ u. Khi đó ta có

∑
u⊆D
u̸=∅

9

σ 2 (fu ), ở đây σ 2 (fu ) là


σ 2 (fu )
là chỉ số độ nhạy toàn cục dùng để đo
σ 2 (f )
mức độ quan trọng tương đối của số hạng fu với f . Bây giờ ta dựa vào việc phân

phương sai của fu . Đồng thời giá trị

tích phương sai, để đưa ra những khái niệm về số chiều hiệu dụng cho α ∈ (0, 1] như
sau
Định nghĩa 1.2.

Số chiều hiệu dụng theo ý nghĩa chặt cụt của hàm f là số

nguyên dương nhỏ nhất dt sao cho

∑

σ 2 (fu ) ≥ ασ 2 (f ).

(8)



∫

fu (xu )dxu = 0 với mọi u ̸=

[0,1]|u|

∫

2

σ (fu ) =

∫

(I − fu ) dxu (trong đó I =

fu (xu )dxu = 0 vì u ̸= ∅).

2

[0,1]|u|

[0,1]|u|

∫

Khi đó

(fu )2 dxu = ||fu ||2L .


u̸⊆{1,...,dt }

u⊆{1,...,dt }

Điều này cho ta điều phải chứng minh.
10

||fu ||2L2

σ 2 (fu )

(1 − α)σ 2 (fu ).


Bổ đề 1.2. Cho ds là số chiều chồng chất của f . Khi đó với α ∈ (0, 1] và fds :=

∑

|u|≤ds

fu (xu ) ta có ||f − fds ||2L2 ≤ (1 − α)σ 2 (f ).

Chứng minh. Tương tự bổ đề 1.1, ta có
||f − fds ||2L2 =||

∑

fu (xu ) −



||fu (xu )||2

|u|≤ds

u⊆D
u̸=∅

=σ 2 (f ) −

∑

σ 2 (fu ) ≤ (1 − α)σ 2 (f ).

|u|≤ds

Từ đây ta có điều phải chứng minh.
Nhận xét.
1. Từ hai bổ đề trên ta nhận thấy phương pháp tính tích phân tạo ra sai số nhỏ
nếu α gần 1. Các điểm tựa ngẫu nhiên là được phân bố đều theo số chiều lớn đến
mức mà ta có thể hi vọng rằng Ifdt là được xấp xỉ tốt khi số chiều chặt cụt dt nhỏ.
Đồng thời đánh giá
|If − Iftr | ≤

√
1 − ασ(f )

(10)

giải thích một phần thành công của phương pháp lưới thưa cho tích phân có số


Phân hoạch ANOVA có điểm neo

Sử dụng các kí hiệu như trong Định nghĩa 1.1 ta có
Định nghĩa 2.1. Cho Ω = [0, 1] và dµ(x) = δ(x − a)dx là độ đo Dirac đặt tại
a ∈ [0, 1]d cho trước. Khi đó phân rã
f (x) =

∑

fu (xu ),

u⊆D

trong đó fu (xu ) := Pu f (xu ) −

∑
v ⊂u

fv (xv ) với phép chiếu Pu f (xu ) = f (x )|x =a\xu

được gọi là phân rã ANOVA có điểm neo.
Ở đây ta sử dụng f (x)|x=a\xi = f (a1 , . . . , ai−1 , xi , ai+1 . . . , ad ) và f (x)|x=a\xu =
f (a1 , . . . , x1 , xi1 , ..., xiu , . . . , ad ) với xu = (xi1 , xi2 , ..., xiu ).
Ta thấy rằng các số hạng của phân rã ANOVA có điểm neo do vậy khác với các
số hạng của phân rã phương sai cổ điển ở chỗ là tất cả các hàm dưới dấu tích phân
được thay thế bởi sự đánh giá hàm tại điểm neo a ∈ [0, 1]d cho trước. Phương pháp
này đã được xem xét trong [2] dưới cái tên Cut-HDMR.
Trong khi phân rã ANOVA cổ điển là rất hữu ích để phân tích tầm quan trọng
của các số hạng với số chiều khác nhau và tương tác giữa chúng nhưng nó không

u⊆D
u̸=∅

u⊆D
u̸=∅

12

||fu ||L1

(11)


là tổng các giá trị tuyệt đối của tích phân của tất cả các số hạng trong phân rã. Sau
đó, tương tự như (8), (9) cho α ∈ (0, 1] ta có
Định nghĩa 2.2.

Số chiều chặt cụt trong trường hợp có neo là số nguyên dương

nhỏ nhất dt sao cho

∑

|Ifu |

ασ(f ).

(12)

u⊆{1,...,dt }

|If − Ifdt | ≤ (1 − α)σ(f ).
Chứng minh. Ta có
||If − Ifdt || =|

∑

∑

|Ifu | =

u⊆{1..dt }

=σ(f ) −

Ifu | = |

u⊆{1,..,dt }

u⊆D

≤

∑

Ifu −

∑

∑


|If − Ifds | ≤ (1 − α)σ(f ).

13


Chứng minh. Ta có
|If − Ifds | =|

∑

=

Ifu | = |

|u|≤ds

u⊆D

∑

∑

Ifu −

|Ifu | −

∑
|u|>ds

∑


Bây giờ chúng ta sử dụng phân rã ANOVA có điểm neo để định nghĩa một lớp
mới các phương pháp cho việc tính toán tích phân với số chiều cao. Ta kí hiệu

∫

f (x)dx

(14)

f (z)φd (z)dz,

(15)

If :=
[0,1]d

và

∫
Iφ f :=
Rd

trong đó φd là hàm trọng Gauss. Hai loại này là điển hình trong ứng dụng cho tính
tích phân có số chiều cao.
1.2.1

Sự chặt cụt và rời rạc hóa

Tiếp theo chúng ta phát triển lớp mới các phương pháp tính tích phân. Chúng

Ifi +

i=1

u⊆D

d
∑

Ifi,j + · · · + If1,...,d .

(17)

i,j=1
j

là số các điểm đánh giá của hàm f , ở đây nu là kí hiệu của các số điểm đánh giá
hàm của Qu .

1.3

Sai số và chi phí

Đầu tiên chúng ta xem xét trường hợp của phương pháp tính tích phân tùy ý
Qu . Đầu tiên chúng ta có đánh giá sai số
|If − AS f | = |

∑

u⊆D

Ifu −

∑

qu |

∑
u∈S

u∈S

15

|Ifu − qu | +

ε
eddt s (djt )

ta có

|I(f ) − AS f | ≤ ε + 2(1 − α)σ(f ).
Chứng minh. Ta có |I(f ) − AS f |

∑

If − Ifdt ,ds + Ifdt ,ds − AS f , trong đó fdt ds :=

fu . Mặt khác, ta lại có sai số mô hình hóa được đánh giá bởi

u∈Sdt ds

∑

|If − Ifdt ds | = |

Ifu | ≤

u̸∈Sdt ds

∑

∑

|Ifu | +



|u| ( )
∑
|u|
j=1

(|u|)
j

j

ε(j)

|u| ( )
∑
dt
j=1

j

ε(j).

tập v ⊆ u thỏa mãn điều kiện |v| = j. Sử dụng

16


định nghĩa của ε(j) ta có thể đánh giá được sai số rời rạc hóa bởi

∑

eddt s

k=1

k

j=1

ε(j)

j

j=1

( )

ds
ε ∑ dt
= d
k
k
edt s

eddt s

ddt s
ε
k=
k!
e

]

Um với m := n1/ds thì
|If − AS f |

c(dt , ds )n− ds + 2(1 − α)σ(f )
r

với tất cả hàm f ∈ C r ([0, 1]d ). Ở đây hằng số c(dt , ds ) phụ thuộc vào số chiều hiệu
dụng dt và ds trong trường hợp có điểm neo nhưng không phụ thuộc vào số chiều d.
Chứng minh. Tương tự như bổ đề trên ta có
|If − AS f |

ở đây fdt ,ds :=

∑

Ifdt ,ds − AS f + 2(1 − α)σ(f ),

fu .Vì f ∈ C r ([0, 1]d ), đồng thời fu ∈ C r ([0, 1]|u| ) với mọi

u∈Sdt ,ds

u ⊆ D nên Qu hội tụ với tốc độ

r
.
|u|

[

− drs

=

ds ( ) ∑
k ( )
∑
dt
k
k=1

r

=c(dt , ds )n− ds .
17

k

j=1

j

c(j)n− ds
r

|u|
ds

]



k!

c(j)

j

c(ds )

ds ( )
∑
dt
k=1

k

2k

c(ds )(e2 − 1)(dt )ds ,

2k

c(j). Như vậy đến đây định lí được chứng minh hoàn

toàn.
Chú ý rằng số hạng đầu tiên trong giới hạn sai số diễn tả sai số rời rạc hóa phụ
thuộc vào n tuy nhiên số hạng thứ hai diễn tả sai số mô hình hóa, nó phụ thuộc
vào α, hơn nữa chi phí dùng để giành được một sai số rời rạc hóa đã quy định trước
không phụ thuộc theo số mũ vào số chiều thông thường nhưng lại phụ thuộc vào số
chiều chồng chất trong trường hợp có điểm neo.



• Giả sử rằng ta có một chuỗi các trọng
γ1 ≥ γ2 ≥ ... ≥ γd ≥ 0,
khi đó trọng tích được xác định bởi
γu :=

∏

γj ,

(24)

j∈u

trong đó u ⊆ D. Ở đây
γj :=

|qj |
|Qj (Pj f ) − f (a)|
=
,
|q∅ |
|f (a)|

với j = 1, 2..., d. Theo cách này ta có thể hi vọng tập chỉ số Sγ bao gồm các số hạng
quan trọng nhất đối với những hàm f có số chiều chặt cụt nhỏ. Chú ý rằng các kí
hiệu này sẽ được sử dụng thường xuyên trong các phần tiếp theo của luận văn. Để
ý là cũng có nhiều trọng phổ biến có thể được sử dụng trong việc xây dựng của
chúng ta miễn là điều kiện chấp nhận được thỏa mãn. Tuy nhiên ở đây chúng ta chỉ

là kí hiệu của một phép tính tích phân với mk điểm xi,k và trọng wi,k đồng thời
chuỗi này hội tụ tới If khi k → ∞. Chúng ta quy ước rằng m1 = 1, U1 f = f ( 12 ) và
công thức tính tích phân sai phân
∆k := Umk − Umk−1

(26)

với Um0 = 0 và mọi k ≥ 1. Bây giờ cho f : [0, 1]d → R là hàm nhiều biến . Khi đó
tích phân d - chiều có thể được viết thành tổng thu gọn vô hạn
If =

∑

∆k , f

(27)

k∈Nd

ở đây k ∈ Nd là kí hiệu tích các chỉ số với kj > 0 và
∆k f := (∆k1 ⊗ ∆k2 .... ⊗ ∆kd )f.

(28)

Một lớp đặc biệt các phương pháp tính tích phân cho xấp xỉ của If là dựa vào
sự chặt cụt tổng trên bằng việc sử dụng tập chỉ số xấp xỉ I ⊂ Nd . Tập này có thể
20


coi như là sự làm mịn của tập S ⊆ D. Tuy nhiên tập I phải thỏa mãn điều kiện

ở đây |k|1 =

d
∑

}

l+d−1 ,

(31)

kj , hoặc đối với phương pháp tích thì tập I lại có dạng

j=1

{

I = k ∈ Nd : |k|∞

}

l ,

(32)

ở đây |k|∞ := max {kj : j = 1, 2..., d}.

2.2

Mối quan hệ giữa phương pháp tính tích phân trên lưới


v⊂u

Ta có fv (xv )|xj = 1 = 0 với mọi j ∈ v, điều này có được là do tính trực giao của
2

phép phân hoạch có điểm neo, từ đó cho ta kết luận ∆k fv = 0 với mọi v ∈ u và
k ∈ Nu , điều này dẫn đến ∆k f = ∆k (Pu f ) = ∆k fu với mọi k ∈ Nu . Từ đó suy ra
điều phải chứng minh.

∑

Bây giờ sử dụng bổ đề trên và If =

∆k f ta được

k∈Nd

If =

∑∑

∆k f.

u⊆D k∈Nu

∑

Lại do (17) nên ta cũng thu được If =


u⊆D

qu =

∑

∪

∆k f , ở đây I =

Iu .

u⊆D

k∈I

Ta định nghĩa

{

}

Iu := k ∈ I : kj > 1 khi và chỉ khi j ∈ u = I ∩ Nu .

(34)

Định lý 2.1. Phương pháp tính tích phân (20) với điểm neo a = ( 12 , ..., 12 ), tập chỉ
số S = D và phương pháp tính tích phân
Qu f :=



∑∑

(∆k (Pu f ) − ∆k f

v⊂u k∈Iv

k∈Iu

∑

∆k f

v⊂u k∈Iv

v⊆u k∈Iv

∑

∑∑

∆k f = qu .

k∈Iu

Từ đó suy ra điều phải chứng minh.

2.3

Lưới thưa tối ưu trong không gian có trọng


Chú ý là mỗi u ⊆ D ta có một trọng γu . Tiếp theo, ta định nghĩa không gian
tích tenxơ
Hγ1,mix ([0, 1]d )
trong đó chuẩn xác định bởi ||f ||21,γ :=

∫
||fu ||21,mix

d
⊗

:=

∑

Hγ1j ([0, 1]),

j=1

γu−1 ||fu ||21,mix , ở đây

u∈D

:=

2

∂ |u|
f (xu , 0) dxu .