1
TRẦN XN TIỆP
NGHIÊN CỨU MỘT SỐ THUẬT TỐN
CHỌN K-LÁNG GIỀNG GẦN TRONG 2D
VÀ ÁP DỤNG CHO PHƯƠNG PHÁP RBF-FD
GIẢI PHƯƠNG TRÌNH POISSON

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
Số hóa bởi Trung tâm Học liệu /> 2
TRẦN XN TIỆP

NGHIÊN CỨU MỘT SỐ THUẬT TỐN
CHỌN K-LÁNG GIỀNG GẦN TRONG 2D
VÀ ÁP DỤNG CHO PHƯƠNG PHÁP RBF-FD
GIẢI PHƯƠNG TRÌNH POISSON

CHUN NGÀNH: KHOA HỌC MÁY TÍNH
MÃ SỐ: 60.48.01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH


Số hóa bởi Trung tâm Học liệu /> i

LỜI CAM ĐOAN
Tơi xin cam đoan đây là cơng trình nghiên cứu riêng của tơi. Các số liệu, kết
quả nêu trong luận văn là trung thực và mới mẻ.
Tơi xin cam đoan rằng mọi sự giúp đỡ cho việc thực hiện luận văn này đã
được cảm ơn và các thơng tin trích dẫn trong luận văn đã được chỉ rõ nguồn gốc.

Học viên thực hiện luận văn

Trần Xn Tiệp
Số hóa bởi Trung tâm Học liệu /> ii
LỜI CẢM ƠN
Để hồn thành bản luận văn này, bên cạnh sự nỗ lực cố gắng của bản thân

MQ Multiquadric
IMQ Inverse Multiquadric
Gauss Gaussian
BST Binary Search Tree
W33 Wendlend's C
6
RMS Root Mean Square

MỘT SỐ HÀM DÙNG TRONG LUẬN VĂN
Tên hàm Viết tắt Định nghĩa
Multiquadric MQ
2
()1
mq
rr
f
=+
Inverse Multiquadric IMQ
2
()11
imq
rr
f
=+
Gausian Gauss
2
()
r
g
re

Tập các tâm rời rạc và tâm
z
(TT cung phần tư)
25
Hình 2.5
m điểm gần
z
nhất (TT cung phần tư)
26
Hình 2.6
Các điểm trên mỗi cung phần tư của hình tròn tâm
z

(TT cung phần tư)
26
Hình 2.7
Chọn 2 điểm trên mỗi cung phần tư gần
z
nhất
(TT cung phần tư)
27
Hình 2.8
Tập các tâm rời rạc và tâm
z
(TT Lee Liu Fan)
29
Hình 2.9
Bốn điểm gần
z
nhất (TT Lee Liu Fan)

Hình 3.4
Số tâm ban đầu và sau cùng (Bài tốn 2)
45
Hình 3.5
Đồ thị sai số của ba thuật tốn (Bài tốn 2)
46
Hình 3.6
Số tâm ban đầu và sau cùng (Bài tốn 3)
47
Hình 3.7
Đồ thị sai số của ba thuật tốn (Bài tốn 3)
48
Hình 3.8
Số tâm ban đầu và sau cùng (Bài tốn 4)
49
Hình 3.9
Đồ thị sai số của ba thuật tốn (Bài tốn 4)
50
Hình 3.10
Số tâm ban đầu và sau cùng (Bài tốn 5) 51
Hình 3.11
Đồ thị sai số của ba thuật tốn (Bài tốn 5)
52 Số hóa bởi Trung tâm Học liệu /> vi

MỤC LỤC

LỜI CAM ĐOAN i

2.3. Thuật tốn Lee Liu Fan (LLF) 27
2.3.1. Ý tưởng 28
2.3.2. Nội dung 28
2.3.3. Thuật tốn 28
2.3.4. Ví dụ 29
2.2.5. Ưu, nhược điểm 31
2.3. Thuật tốn Oleg&Oanh – 2011 31
2.3.1. Ý tưởng 31
2.3.2. Nội dung 32
2.3.3. Thuật tốn 33
2.3.4. Ví dụ 35
2.3.5. Ưu, nhược điểm 37
Số hóa bởi Trung tâm Học liệu /> vii
Chương 3. ÁP DỤNG THUẬT TỐN CHỌN K-LÁNG GIỀNG GẦN CHO PHƯƠNG PHÁP
RBF-FD TRONG KHƠNG GIAN 2D 38
3.1. Rời rạc hóa phương trình Poisson 38
3.2. Phương pháp RBF-FD (Radial Basis Function Finite Different) 39
3.2.1. Véc tơ trọng số dựa vào hàm nội suy theo cơ sở bán kính 39
3.2.2. Xây dựng ma trận hệ số (ma trận cứng) 41
3.2.3. Lược đồ phương pháp RBF-FD 42
3.3. Thử nghiệm số 43
3.3.1. Thử nghiệm trên miền hình chữ nhật 43
3.3.2. Thử nghiệm trên một số miền có hình học phức tạp 45
TÀI LIỆU THAM KHẢO 54
NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN 56
Số hóa bởi Trung tâm Học liệu /> 1
LỜI MỞ ĐẦU

và cài đặt thử nghiệm để so sánh hiệu quả của mỗi thuật tốn. Đồng thời tìm
ngun nhân gây ra sai số của mỗi thuật tốn, trên cơ sở đó phân loại lớp bộ tâm
phù hợp cho mỗi thuật tốn.
Nội dung luận văn bao gồm 3 chương:
Chương 1: Một số kiến thức cơ sở
Chương này trình bày một số kiến thức về hình học phẳng; Điều kiện
vật lý dẫn đến phương trình Poisson; Hệ phương trình đại số tuyến tính;
Một số phương pháp giải hệ phương trình đại số tuyến tính; Một số định
nghĩa và khái niệm cơ bản của nội suy hàm RBF; Nội suy hàm RBF;
Phương pháp sai phân hữu hạn.
Chương 2: Một số thuật tốn chọn K-láng giềng gần trong 2D
Chương này sẽ tập trung nghiên cứu ba thuật tốn tìm K-Láng giềng
gần trong 2D là: thuật tốn bốn cung phần tư, thuật tốn Lee Liu Fan,
thuật tốn Oleg&Oanh-2011, phương pháp khơng lưới có sự hỗ trợ của
thuật tốn tìm K-Láng giềng gần.
Chương 3: Áp dụng thuật tốn chọn K-láng giềng gần cho phương
pháp RBF-FD trong khơng gian 2D
Chương này dành cho phần thử nghiệm nhằm so sánh hiệu quả của các
thuật tốn tìm K-Láng giềng gần khi áp dụng để hỗ trợ phương pháp khơng
lưới giải phương trình Poisson.

Số hóa bởi Trung tâm Học liệu /> 3
Chương 1
MỘT SỐ KIẾN THỨC CƠ SỞ

1.1. Điều kiện vật lý dẫn đến phương trình Poisson
Xét một bản mỏng vật chất
W
, có đường biên là một đường cong khép kín
G

êú
êú
¶¶¶¶¶
ëû
ëû
,
(,),0xytỴW>
(1.2)
Hay khi
1
k ,
2
k ,
f
khơng phụ thuộc vào
u
thì có phương trình tuyến tính

12
(,,)(,,)(,,)(,,)
uuu
kxytkxytqxytufxyt
txxyy
éù
¶¶¶¶¶
éù
=+-+
êú
êú
¶¶¶¶¶

,
(,)xW
(1.4)
Số hóa bởi Trung tâm Học liệu /> 4
Hay

12
(,,)(,,)(,,)
uu
kxyukxyufxyu
xxyy
éù
¶¶¶¶
éù
+=
êú
êú
¶¶¶¶
ëû
ëû
,
(,)xW
(1.5)

12
(,)(,)(,)(,)
uu
kxykxyqxyufxy
xxyy
éù

miền
W
.
Điều kiện phụ

(,)(,)uxygxy=
,
(,)xG
(1.8)
G ọ i là điều kiện biên loại một hay điều kiện biên Dirichlet.
Bài tốn tìm hàm số
(,)uuxy=
thỏa mãn phương trình (1.7) với điều kiện biên
(1.8) gọi là bài tốn biên loại một hay bài tốn biên Dirichlet đối với phương trình
Poisson (1.7)
Ý nghĩa vật lý của bài tốn này là mơ tả sự phân bố nhiệt đã ổn định trong mặt
phẳng
W
khi phân bố nhiệt độ tại biên
G
của
W
ổn định là (,)
g
xy. [14]
1.2. Hệ phương trình đại số tuyến tính
Xét một hệ phương trình gồm n phương trình tuyến tính với n ẩn số
12
,, ,
n

A
xb
=
, trong đó

111
12n
nnnn
aa
A
aaa
éù
êú
=
êú
êú
ëû
,
12
(,, )
T
n
x
xxx=
,
12
(,, ,)

12
(,, ,)
n
Xxxx=

- Chuẩn dòng
(
)
1,
ax
i
in
X
mx
¥
=
=

- Chuẩn cột
1
1
n
i
i
Xx
=
=
å

- Chuẩn Ơclit

aaa
A
aaa
éù
êú
êú
=
êú
êú
ëû

- Chuẩn dòng
ij
1
1
ax
n
in
j
A
ma
¥
££
=
ỉư
=
ç÷
èø
å


=
ç÷
èø
åå
[14]
1.3.2. Phương pháp Gauss
Đây là phương pháp trực tiếp giải hệ phương trình đại số tuyến tính. Ý tưởng
của phương pháp khử Gauss là khử dần các ẩn để đưa hệ ban đầu về hệ với ma trận
tam giác trên bằng các phép biến đổi tương đương:
1) Đổi chỗ hai phương trình bất kì.
2) Nhân một phương trình với một số khác khơng.
3) Cộng vào phương trình một tổ hợp tuyến tính của một phương trình khác.
Như vậy phương pháp Gauss gồm hai q trình:
Q trình thuận: Đưa hệ về dạng tam giác trên.
Q trình ngược: Giải hệ tam giác trên từ dưới lên trên.
Số hóa bởi Trung tâm Học liệu /> 7
a) Q trình thuận: Để viết gọn ta xét hệ

11112211,1
21122222,1
1122,1

nnn
nnn
nnnnnnn
axaxaxa
axaxaxa

a ta được phương trình:

112211,1

nnn
x
bxbxb
+
+++=
(1.12)
Với
(0)
1
1
(0)
11
,2, ,1.
j
j
a
bjn
a
==+

Cộng vào phương trình thứ i của hệ (1.11) phương trình (1.12) sau khi đã nhân
với
(0)
1
,2, ,
i

ỵ
(1.13)
Với
(1)(0)(1)
ijiji11
,2, ,;2, ,1
j
aaabinjn=-==+
Như vậy sau bước 1 ta thu được phương trình (1.12) và hệ (1.13).
Bước 2: Dùng phương trình đầu tiên trong (1.13) khử x
2
trong các phương trình
còn lại tương tự như đã làm trong bước 1. Q trình được tiếp tục như vậy. Kết quả
sau bước thứ m ta thu được hệ

()()()
1,111,1,1
()()()
,11,,1
,11,,1
mmm
mmmmnnmn
mmm
nmmmnnnn
mmmmmnnmn
axaxa
axaxa

nnn
x
bxbxb
+
+++=

222,1

nnn
xbxb
+
++=
(1.14)

,1nnn
xb
+
=
Các hệ số được tính theo cơng thức
(1)(1)
/,1, ,;1, ,1
mm
mjmjmm
baamnjmn

===++


xbbxkn
+
=+
=-=-
å
(1.16)
[14]
1.4. Một số định nghĩa và khái niệm cơ bản của nội suy hàm RBF
* Định nghĩa 1.1 (K - Láng giềng gần)
Cho tập các tâm rời rạc
z
X
với
z
là tâm, tất cả các điểm thuộc
z
X
nằm
xung quanh tâm
z
được gọi là K-láng giềng của
z

* Định nghĩa 1.2 (Tập các tâm rời rạc
z
X
)
Số hóa bởi Trung tâm Học liệu /> 9
Tập các tâm rời rạc
z

ww
ii
x=
. Khi đó
[ ]
12
ww,w ,w
n
T
=
được gọi là
véc tơ trọng số hay còn được gọi là stencil đối với tốn tử vi phân D. [12]
* Định nghĩa 1.4 (Giá của véc tơ trọng số
V
º )
Giá của véc tơ trọng số
V
º là tập hợp các tâm bao gồm
V
và các tâm nằm
trong lân cận địa phương của nó.
Trong các phương pháp dựa trên lưới thì tập này bao gồm
V
và các đỉnh của
các tam giác mà được liên thơng với
V
bởi một cạnh. Còn đối với phương pháp
khơng lưới, cần một thuật tốn lựa chọn các tâm này mà chúng tơi gọi là thuật tốn
lựa chọn giá của véc tơ trọng số. [12]
* Định nghĩa 1.5 (Hàm bán kính (Radial function))

F®
được gọi là xác định dương nếu với mọi bộ tâm
phân biệt từng đơi một
{
}
12
,,
d
n
x
xxR
z
X=Ì
,
nNỴ
và mọi vectơ
n
cRỴ thì dạng
tồn phương:

11
()0
nn
jkjk
jk
CCxx
==
-³
åå
(1.18)

iiii
x
yinxRyR=ỴỴ
với
i
x
là các vị trí đo,
i
y là các kết
quả đo đạc. Giả sử rằng dữ liệu phân tán, nghĩa là các vị trí dữ liệu khơng nằm
trên lưới đều.
Cho
12
,, ,
n
BBB
là các hàm cơ sở của khơng gian tuyến tính
1
, 1,2, ,
n
ki
k
F
cBin
=
==
å

Bài tốn nội suy: Tìm
PfFỴ


111
1
() ()

() ()
n
nnn
B
xBx
A
B
xBx
éù
êú
=
êú
êú
ëû
(1.22)
[
]
[
]
11
, ,, , ,
TT
nn
cccyyy==


F
là khơng gian Haar trên
dd
R
WÌ
nếu
det0A ¹
với
mọi tập phân biệt
12
{,, ,}
n
x
xx
trong
W
, trong đó ma trận A đã được định
nghĩa bởi (1.22). [8]
Định lý 1.2 (Mairhuber Curtis). Giả sử rằng
d
R
WÌ
, chứa một điểm trong.
Khi đó khơng tồn tại khơng gian Haar của các hàm liên tục trên
W
, trừ khi
đối với khơng gian một chiều. [8]
Định lý Maihuber Curtis cho thấy rằng nếu muốn giải được bài tốn nội suy
dữ liệu phân tán nhiều biến thì cơ sở cần phụ thuộc vào các vị trí dữ liệu. Để thu
được các khơng gian xấp xỉ phụ thuộc dữ liệu, chúng ta cần xét các hàm xác định

* Lưu ý:
1) Hàm cơ sở phải gắn liền với đối tượng nghiên cứu vì vây để giải
phương trình đạo hàm riêng thì các hàm cơ sở theo bán kính phải là các hàm
khả vi liên tục và thâm chí là khả vi liên tục vơ hạn lần.
2) Để bài tốn nội suy có nghiệm duy nhất, ta cần phải chọn hàm
F
phù
hợp sao cho det
0A ¹
.
Bảng 1.1. Một số hàm nội suy theo bán kính dùng trong luận văn
Tên hàm Viết tắt Định nghĩa
Multiquadric MQ
2
()1
mq
rr
f
=+
Inverse Multiquadric IMQ
2
()11
imq
rr
f
=+
Gausian Gauss
2
()
r

fxyin==
(1.24)
Nghĩa là
( )
1
-, 1,2, ,
n
kiki
k
cxxyin
f
=
==
å

Suy ra

A
cy=
(1.25)
Trong đó
Số hóa bởi Trung tâm Học liệu /> 13

121
212
12
(0)() ()
()(0) ()

()() (0)

2
()(),
d
kkk
x
xxxxxR
f
F=F-=-"Ỵ

Nội suy hàm cơ sở theo bán kính với độ chính xác đa thức có nghĩa là cần tìm
( )
11
()-(),
nM
d
kkll
kl
PfxcxxdpxxR
f
==
=+Ỵ
åå

Trong đó
1
11
(1)!
dim
(1)!!
ddm

ẩn
k
c
và
d
l
. Vì vậy để hệ có nghiệm duy nhất, ta phải thêm vào
1
()0, 1,2, ,
n
kk
k
cpxM
=
==
å
l
l

Do đó ta có điều kiện nội suy suy rộng

( )
11
(), ,
nM
d
kikii
k
cxxdpxyxR
f

n
nn
x
xxx
x
xxx
A
xxxx
FF-F-
éù
êú
F-FF-
êú
=
êú
êú
F-F-F
ëû
(1.28)
[ ]
112,
, ,,, ,
T
T
nn
cccyyyy
éù
==
ëû


,, ,,
d
n
x
xxRnNỴỴ
, mọi véc tơ
n
cRỴ
và mọi
đa thức
p
giá trị thực bậc nhỏ hơn
l
, thỏa mãn

1
()0
n
jj
j
cx
=
=
å
(1.30)
thì dạng tồn phương

11
()0
nn

l
, có thể được sáng tỏ như là
hàm xác định dương trên khơng gian véc tơ c sao cho
Số hóa bởi Trung tâm Học liệu /> 15
1
()0
n
jj
j
cpx
=
=
å
,
trong đó
p
là đa thức bậc nhỏ hơn
l
.
Thật vậy, với cách này, ma trận A là xác định dương trên khơng gian
véc tơ trực giao c đối với đa thức bậc nhỏ hơn hằng
1-l
.
1.6. Phương pháp sai phân hữu hạn (Finite Different - FD)
1.6.1. Bài tốn truyền nhiệt dừng trong miền chữ nhật
Cho các số a, b, c, d với a < b, c < d. Xét trong mặt phẳng toạ độ vng góc
với Oxy một miền chữ nhật Ω có cạnh song song với các trục toạ dộ Ox và Oy.

{(,);}
x

,
ii
xaihycik=+=+
(1.32)
Mỗi điểm
(,)
ii
xy
là một nút lưới và còn kí hiệu là (i, j). Các nút nằm trong
miền Ω được gọi là nút trong, tập tất cả các nút trong kí hiệu là Ω
hk
. Nút ở trên
G

Số hóa bởi Trung tâm Học liệu /> 16
được gọi là các nút biên và tập tất cả các nút này kí hiệu là
G
hk
. Tập
hk
hkhk
W=WÈG
gọi là một lưới sai phân trên
W
.

Hình 1.1. Lưới sai phân
1.6.3. Hàm lưới
Kí hiệu
()

ax(,)ons.
xy
u
M
xyCct
x
ỴW
¶
£=
¶

do đó cơng thức Taylor:

2
()1
()()
()()()() ()(())
1!2!!
m
mm
xxx
FxxFxFxFxFxOx
m
+
DDD
¢¢¢
+D=+++++D

từ đó ta có:
Số hóa bởi Trung tâm Học liệu />