1








NGUYỄN NGỌC KHÁNH






XÂY DỰNG MỘT SỐ BỘ DỮ LIỆU PHÂN TÁN
TRONG KHÔNG GIAN 2D CHO PHƢƠNG
PHÁP RBF-FD GIẢI PHƢƠNG TRÌNH
POISSON





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

LUẬN VĂN THẠC SĨ




THÁI NGUYÊN - 2013
2




Tôi xin cam đoan:
Luận văn này là sản phẩm nghiên cứu của tôi.
Số liệu trong luận văn là trung thực.
Tài liệu nghiên cứu có nguồn gốc rõ ràng.
Tôi xin chịu trách nhiệm về nghiên cứu của mình.

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


Nguyễn Ngọc Khánh













3

LỜI CẢM ƠN
Để có thể hoàn thành luận văn thạc sĩ một cách hoàn chỉnh, bên cạnh sự
nỗ lực cố gắng của bản thân còn có sự hƣớng dẫn nhiệt tình của quý Thầy Cô,
cũng nhƣ sự động viên ủng hộ của gia đình và bạn bè trong suốt thời gian học
tập nghiên cứu và thực hiện luận văn thạc sĩ.
Xin chân thành bày tỏ lòng biết ơn đến cô giáo TS. Đặng Thị Oanh,
ngƣời đã hết lòng giúp đỡ và tạo mọi điều kiện tốt nhất cho tôi hoàn thành
luận văn này. Xin gửi lời tri ân nhất của tôi đối với những điều mà cô đã dành
cho tôi.
Xin chân thành bày tỏ lòng biết ơn đến toàn thể quý Thầy Cô trong
Trƣờng Đại Học Công Nghệ Thông Tin & Truyền Thông cũng nhƣ quý Thầy
Cô đã tận tình truyền đạt những kiến thức quý báu và tạo mọi điều kiện thuận
lợi cho tôi trong suốt quá trình học tập nghiên cứu và cho đến khi thực hiện
luận văn.
Xin chân thành bày tỏ lòng biết ơn đến gia đình, những ngƣời đã không
ngừng động viên, hỗ trợ và tạo mọi điều kiện tốt nhất cho tôi trong suốt thời
gian học tập và thực hiện luận văn.
Cuối cùng, tôi xin chân thành bày tỏ lòng biết ơn đến các anh chị và các
bạn bè đồng nghiệp đã hỗ trợ cho tôi rất nhiều trong suốt quá trình học tập,
nghiên cứu và thực hiện luận văn thạc sĩ một cách hoàn chỉnh.



Thái Nguyên, tháng 12 năm 2013
Học viên thực hiện
Nguyễn Ngọc Khánh


4

DANH MỤC CÁC TỪ VIẾT TẮT

Từ
Ý nghĩa
RBF
Radial Basic Function
FD
Finite Different
LLF
Lee Liu Fan
MQ
Multiquadric
IMQ
Inverse Multiquadric
Gauss
Gaussian
BST
Binary Search Tree
W33
Wendlend's C
6












5

DANH MỤC HÌNH VẼ

Trang
Hình 2.1
Sinh tâm ngẫu nhiên (200 tâm trong số 4000 tâm)
30
Hình 2.2
Sinh tâm ngẫu nhiên (400 tâm trong số 4000 tâm)
30
Hình 2.3
Sinh tâm ngẫu nhiên (800 tâm trong số 4000 tâm)
31
Hình 2.4
Cấu trúc ngựa vằn (200 tâm với độ rộng dải trống là 0.65)
32
Hình 2.5
Cấu trúc ngựa vằn (800 tâm với độ rộng dải trống là 0.65)
32
Hình 2.6

Cấu trúc ngựa vằn (800 tâm với độ rộng dải trống là 0.13)
33
Hình 2.7
Cấu trúc ngựa vằn (1200 tâm với độ rộng dải trống là 0.13)
33
Hình 2.8
Cấu trúc ngựa vằn (800 tâm với độ rộng dải trống là 0.15)
34
Hình 2.9
Cấu trúc ngựa vằn (1200 tâm với độ rộng dải trống là 0.15)
34
Hình 2.10
Cấu trúc co đều xung quanh các điểm có tọa độ nguyên
(200 tâm trong miền với hệ số co là 0.2)
37
Hình 2.11
Cấu trúc co đều xung quanh các điểm có tọa độ nguyên
(400 tâm trong miền với hệ số co là 0.2)
37
Hình 2.12
Cấu trúc co đều xung quanh các điểm có tọa độ nguyên
(400 tâm trong miền với hệ số co là 0.4)
38
Hình 2.13
Cấu trúc co đều xung quanh các điểm có tọa độ nguyên
(800 tâm trong miền với hệ số co là 0.4)
38
Hình 2.14
Cấu trúc co đều xung quanh các điểm có tọa độ nguyên
(400 tâm trong miền với hệ số co là 0.6)

39
Hình 2.15
Cấu trúc co đều xung quanh các điểm có tọa độ nguyên
(800 tâm trong miền với hệ số co là 0.6)
39
Hình 2.16
Cấu trúc co đều xung quanh các điểm có tọa độ nguyên
(400 tâm trong miền với hệ số co là 0.8)
40
Hình 2.17
Cấu trúc co đều xung quanh các điểm có tọa độ nguyên
40
6

(800 tâm trong miền với hệ số co là 0.8)
Hình 2.18
Bộ tâm là sản phẩm của thuật toán làm mịn thích nghi (với
số nút trên miền = 145 và số nút trên biên = 44)
45
Hình 2.19
Bộ tâm là sản phẩm của thuật toán làm mịn thích nghi (Số
nút trên miền 206 và số nút trên biên 54)
46
Hình 2.20
Bộ tâm là sản phẩm của thuật toán làm mịn thích nghi (số
nút trên miền = 283 và số nút trên biên= 74)
46
Hình 2.21
Bộ tâm là sản phẩm của thuật toán làm mịn thích nghi (với
số nút trên miền = 433 và số nút trên biên = 102)

47
Hình 3.1
Giao diện chính của chƣơng trình
49
Hình 3.2

50
Bảng1.1
Một số hàm cơ sở bán kính dùng trong báo cáo
19
Bảng 3.1
Bảng sai số RMS trên bộ tâm đƣợc biểu diễn nhƣ trong
hình 3.2
50










7

MỤC LỤC

LỜI MỞ ĐẦU 10
CHƢƠNG 1 12

MỘT SỐ KIẾN THỨC CƠ SỞ 12
1.1. ĐIỀU KIỆN VẬT LÝ DẪN ĐẾN PHƢƠNG TRÌNH
POISSON 12
1.2. HỆ PHƢƠNG TRÌNH ĐẠI SỐ TUYẾN TÍNH 13
1.3. MỘT SỐ PHƢƠNG PHÁP GIẢI HỆ PHƢƠNG TRÌNH ĐẠI
SỐ TUYẾN TÍNH 15
1.3.1. Phƣơng pháp Gauss 15
1.3.2. Phƣơng pháp truy đuổi giải hệ phƣơng trình với ma trận
ba đƣờng chéo 17
1.4. MỘT SỐ ĐỊNH NGHĨA VÀ KHÁI NIỆM CƠ BẢN 19
1.4.1. Định nghĩa bộ dữ liệu phân tán 19
1.4.2. Một số định nghĩa liên quan đến hàm Radial Basis
Function-RBF 19
1.4.3. Định nghĩa véc tơ trọng số 20
1.5. NỘI SUY HÀM RBF 20
1.5.1. Nội suy dữ liệu phân tán trong không gian
d
R
20
1.5.2. Nội suy với hàm cơ sở theo bán kính 21
1.6. PHƢƠNG PHÁP SAI PHÂN HỮU HẠN (Finite Different -
FD) 22
1.6.1. Bài toán 22
8

1.6.2. Rời rạc bài toàn Dirichlet 23
1.6.3. Lƣợc đồ sai phân hữu hạn giải bài toán Dirichlet với
phƣơng trình Poisson 23
CHƢƠNG 2 25
MỘT SỐ PHƢƠNG PHÁP XÂY DỰNG BỘ DỮ LIỆU PHÂN

TÁN TRONG KHÔNG GIAN 2D 25
2.1. PHƢƠNG PHÁP RBF-FD (Radial Basis Function Finite
Different) 25
2.1.1. Véc tơ trọng số dựa vào hàm nội suy theo cơ sở bán kính25
2.1.2. Ma trận hệ số (ma trận cứng) 27
2.1.3. Lƣợc đồ RBF 27
2.2. THUẬT TOÁN CHỌN BỘ TÂM HỖ TRỢ TÍNH HỆ SỐ
NỘI SUY HÀM RBF 28
2.3. MỘT SỐ PHƢƠNG PHÁP XÂY DỰNG BỘ DỮ LIỆU
PHÂN TÁN 32
2.3.1. Bộ tâm ngẫu nhiên 32
2.3.2. Cấu trúc Ngựa vằn (Zebra) 34
2.3.3. Cấu trúc co đều xung quanh các điểm có tọa độ nguyên . 37
2.3.4. Làm mịn thích nghi 43
CHƢƠNG 3 50
THỬ NGHIỆM SỐ 50
3.1. GIAO DIỆN CHÍNH CỦA CHƢƠNG TRÌNH 50
3.2. SAI SỐ VÀ CÁC BÀI TOÁN THỬ NGHIỆM 50
3.2.1 Sai số 50
9

3.2.2 Các bài toán 51
3.3 KẾT QUẢ THỬ NGHIỆM 51
3.3.1 Thử nghiệm trên bộ sinh tâm ngẫu nhiên 51
3.3.2 Thử nghiệm trên cấu trúc ngựa vằn 52
3.3.3 Thử nghiệm trên bộ sinh tâm co đều xung quanh các điểm
: 54
3.3.4 Thử nghiệm trên cấu trúc sinh tâm thích nghi 56
58
59

NHẬN XÉT CỦA GIÁO VIÊN HƢỚNG DẪN 61




10

LỜI MỞ ĐẦU
Trong suốt thế kỷ XX một loạt các phƣơng pháp số đã hình thành và
phát triển nhƣ các phƣơng pháp sai phân hữu hạn, phƣơng pháp phần tử hữu
hạn v.v… đã đem lại những đóng góp to lớn trong việc ứng dụng các phƣơng
pháp toán học vào thực tiễn. Các phƣơng pháp vừa nêu nói chung đều là các
phƣơng pháp lƣới. Tuy nhiên, các phƣơng pháp này còn nhiều hạn chế khi áp
dụng vào lớp các bài toán thực tế có miền hình học hoặc dữ liệu phân bố quá
phân tán.
Vào khoảng những năm cuối của thế kỷ trƣớc đã hình thành một xu
hƣớng mới của các phƣơng pháp số: Phƣơng pháp không lƣới. Cũng nhƣ các
phƣơng pháp lƣới, để giải các bài toán biên bằng phƣơng pháp không lƣới
cũng cần thiết có các tập hợp nút, mà ở đây gọi là các bộ tâm để tính toán. Từ
bộ tâm này ta xấp xỉ các toán tử vi phân bằng tổ hợp các giá trị của hàm tại
các nút. Phƣơng pháp tìm các vectơ trọng số dựa trên các hàm cơ sở bán kính
(RBF – Radial Basis Function) gọi là phƣơng pháp dựa vào nội suy dữ liệu
phân tán với các hàm cơ sở bán kính RBF – FD (Radial Basis Function –
Finite Different). Khi áp dụng phƣơng pháp này, khó khăn gặp phải là chọn
bộ tâm hỗ trợ cho việc tính véc tơ trọng số. Nhờ sự giúp đỡ của TS. Đặng Thị
Oanh, tôi đã mạnh dạn chọn đề tài: “Xây dựng một số bộ dữ liệu phân tán
trong không gian 2D cho phương pháp RBF-FD giải phương trình
Poisson”. Mục đích của đề tài là xây dựng một số bộ tâm có cấu trúc đặc biệt
để test độ mạnh của một số thuật toán chọn tâm hỗ trợ cho tính véc tơ trong số
hiện nay. Trên cơ sở thực hiện các test sẽ rút ra đƣợc một số nhận xét nhằm

cải tiến việc chọn bộ tâm sao cho nội suy hàm RBF tốt hơ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ở
11

Chƣơng này trình bày đ ;
H ;
;
; Nội suy RBF; Phƣơng pháp sai phân .
Chƣơng 2: Một số phƣơng pháp xây dựng bộ tâm dữ liệu phân
tán trong không gian 2D
Chƣơng này nghiên cứu về phƣơng pháp RBF-FD, xây dựng ma trận hệ
số, thuật toán chọn bộ tâm cho hệ số nội suy hàm RBF và chuyên sâu về
nghiên cứu một số phƣơng pháp xây dựng bộ dữ liệu phân tán nhƣ: sinh bộ
tâm ngẫu nhiên, cấu trúc ngựa vằn, cấu trúc co đều xung quanh các điểm có
tọa độ nguyên và làm mịn thích nghi.
Chƣơng 3: Thử nghiệm số
Chƣơng này dành cho phần thử nghiệm phƣơng pháp RBF-FD trên các
bộ tâm đƣợc sinh ra bởi các phƣơng pháp trình bày trong chƣơng 2.













12

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 [12]
Xét một bản mỏng vật chất , có đƣờng biên là một đƣờng cong khép
kín , đặt trong mặt phẳng Oxy.
Khi đó ta có phƣơng trình truyền nhiệt trong môi trƣờng phẳng đồng
chất

22
22
()
uu
k
t x y
,
( , ) , 0, onsx y t k c t
(1.1)
Hay trƣờng hợp tổng quát hơn:

12
( , , , ) ( , , , ) ( , , , )
u u u
k x y t u k x y t u f x y t u
t x x y y
,


( , ) , 0x y t
(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
( , , ) ( , , ) ( , , ) ( , , )
u u u
k x y t k x y t q x y t u f x y t
t x x y y
,

( , ) , 0x y t
(1.3)

Các phƣơng trình (1.1), (1.2), (1.3) gọi là các phƣơng trình truyền nhiệt
hai chiều.
Nếu đến một lúc nào đó phân bố nhiệt trên bản mỏng vật chất đã ổn
định, không thay đổi theo thời gian nữa thì ta nói hiện tƣợng truyền nhiệt đã
dừng.
Từ lúc đó nhiệt độ không thay đổi theo thời gian nên
0

u
t
và ta có
phƣơng trình truyền nhiệt dừng nhƣ sau:

22
22
0
uu
xy
,
( , )xy
(1.4)
13

Hay
12
( , , ) ( , , ) ( , , )
uu
k x y u k x y u f x y u
x x y y
,
( , )xy
(1.5)

12
( , ) ( , ) ( , ) ( , )
uu
k x y k x y q x y u f x y
x x y y

,
( , )xy
(1.6)
Khi vế phải (1.4) khác 0 ta có phƣơng trình

22
22
( , )
uu
f x y
xy
,
( , )xy
(1.7)
Ngƣời ta gọi chúng là phƣơng trình Poisson hai chiều.
Đối với phƣơng trình Poisson hai chiều (1.7) điều kiện phụ cho tại biên
của miền .
Điều kiện phụ

( , ) ( , )u x y g x y
,
( , )xy
(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 toán tìm hàm số
( , )u u x y
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 toán biên loại một hay bài toán biên Dirichlet đối với
phƣơng trình Poisson (1.7).
Ý nghĩa vật lý của bài toán này là nó mô tả sự phân bố nhiệt đã ổn định

trong miền phẳng khi phân bố nhiệt độ tại biên của ổn định là
( , )g x y
.
[12]
1.2. HỆ PHƢƠNG TRÌNH ĐẠI SỐ TUYẾN TÍNH [12]
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
x x x
đƣợc cho bởi


11 1 12 2 1 1
21 1 22 2 2 2
1 1 2 2




nn
nn
n n nn n n
a x a x a x b
a x a x a x b
a x a x a x b
(1.9)
Hệ này có thể viết dƣới dạng ma trận
Axb
, trong đó

14


11 1
12


n
n n nn
aa
A
a a a
,
12
( , , )
T
n
x x x x
,
12
( , , , )
T
n
b b b b

Nếu
det 0A
thì hệ (1.9) có nghiệm duy nhất và nghiệm của nó có thể
tính theo công thức Cramer:


det
det
j
j
A
x
A
(1.10)
trong đó
j
A
là ma trận nhận đƣợc từ ma trận A bằng cách thay cột thứ j
bởi cột b.
Công thức (1.10) thƣờng chỉ dành cho hệ với ma trận hệ số cỡ nhỏ, còn
với ma trận cỡ lớn thì chi phí cho tính toán quá lớn. Do đó, ngƣời ta đã đi xây
dựng các phƣơng pháp nhanh để giải hệ phƣơng trình đại số tuyến tính cỡ lớn
là khai thác triệt để các thông tin về ma trận của hệ.
Dƣới đây là một số dạng đặc biệt của ma trận:
1) Ma trận đƣờng chéo: Ma trận vuông cấp n mà mọi phần tử nằm
ngoài đƣờng chéo chính bằng 0, tức là
ij ji
aa
, với
i j
, đƣợc gọi là ma
trận đƣờng chéo.
2) Nếu ma trận đƣờng chéo có
ii
a 1, i 1,2, , n
thì ta gọi A là ma

trận đơn vị và ta thƣờng kí hiệu là E hoặc I.
3) Ma trận tam giác trên: Ma trận vuông A đƣợc gọi là ma trận tam giác
trên, nếu A có dạng
11 12 1
22 2

0
. . .
0 0
n
n
nn
a a a
aa
A
a

Tức là
ij
0a
nếu
ij
.
4) Ma trận tam giác dƣới: Tƣơng tự ma trận vuông A đƣợc gọi là ma
trận tam giác dƣới, nếu A có dạng
15

11
21 22
12

0 0
0
. . .

n n nn
a
aa
A
a a a

Tức là
ij
0a
nếu
ij
.
5) Ma trận thƣa: Ma trận thƣa là ma trận có rất nhiều phần tử bằng 0.
6) Ma trận đối xứng: Ma trận A đƣợc gọi là ma trận đối xứng nếu A =
A*, tức là
ij ji
a a (i 1,2, , n
,
j 1,2, , n)

1.3. MỘT SỐ PHƢƠNG PHÁP GIẢI HỆ PHƢƠNG TRÌNH ĐẠI SỐ
TUYẾN TÍNH [12]
1.3.1. Phƣơng pháp Gauss [14]
Đâ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 quá trình:
Quá trình thuận: Đƣa hệ về dạng tam giác trên.
Quá trình ngƣợc: Giải hệ tam giác trên từ dƣới lên trên.
a) Quá trình thuận: Để viết gọn ta xét hệ

11 1 12 2 1 1, 1
21 1 22 2 2 2, 1
1 1 2 2 , 1




n n n
n n n
n n nn n n n
a x a x a x a
a x a x a x a
a x a x a x a
(1.11)
Và đặt
(0)
ij ij
,( 1,2, , ; 1, , 1)a a i n j n


16


Bƣớc 1: Dùng phƣơng trình đầu tiên để khử
1
x
trong n - 1 phƣơng trình
còn lại. Giả sử
11
0a
(ta luôn có đƣợc điều này bằng cách đổi chỗ hai phƣơng
trình). Chia hai vế của phƣơng trình thứ nhất cho
11
a
ta đƣợc phƣơng trình:

1 12 2 1 1, 1

n n n
x b x b x b
(1.12)
Với
(0)
1
1
(0)
11
, 2, , 1.
j
j
a
b j n

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
a i n
ta đƣợc hệ

(1) (1) (1) (1)
22 2 23 3 2 2, 1
(1) (1) (1) (1)
32 2 33 2 3 3, 1
(1) (1) (1) (1)
2 2 2 2 , 1




n n n
n n n
n n nn n n n
a x a x a x a
a x a x a x a
a x a x a x a
(1.13)
Với
(1) (0) (1)

ij ij i1 1
, 2, , ; 2, , 1
j
a a a b i n j n

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. Quá trình đƣợc tiếp
tục nhƣ vậy. Kết quả sau bƣớc thứ m ta thu đƣợc hệ:

, 1 1 , , 1
( ) ( ) ( )
1, 1 1 1, 1, 1
( ) ( ) ( )
, 1 1 , , 1



m m m m m n n m n
m m m
m m m m n n m n
m m m
n m m m n n n n
x b x b x b
a x a x a
a x a x a

Với


( 1) ( 1)
/ , 1, , 1
mm
mj mj mm
b a a j m n


( ) ( 1) ( 1)
ij ij im
, 1, , ; 1, , 1
m m m
mj
a a a b i m n j m n

Cuối cùng, sau n bƣớc khử ta thu đƣợc hệ phƣơng trình với ma trận tam
giác trên sau đây:

1 12 2 1 1, 1

n n n
x b x b x b

17


2 2 2, 1

n n n
x b x b

(1.14)




,1n n n
xb

Các hệ số đƣợc tính theo công thức
( 1) ( 1)
/ , 1, , ; 1, , 1
mm
mj mj mm
b a a m n j m n

( ) ( 1) ( 1)
ij ij im
; 1, , ; 1, , 1
m m m
mj
a a a b i m n j m n
(1.15)
Các phần tử
( 1)m
mm
a

1, ,mn
a là các phần tử trụ hay các phần tử chủ đạo.
b) Quá trình ngƣợc: Giải hệ (1.14) từ dƣới lên trên


,1n n n
xb


,1
1
, 1, ,1
n
k k n kj j
jk
x b b x k n
(1.16)
1.3.2. Phƣơng pháp truy đuổi giải hệ phƣơng trình với ma trận ba đƣờng
chéo [14]
Xét hệ phƣơng trình
Axf
, trong đó ma trận A có dạng ba đƣờng chéo
sau

11
2 2 2
1
0 0 0
0 0
. . . . .
0 0 0 .
0 0 0
n
nn

cb
a c b
A
b
ac
(1.17)
Các phƣơng trình của hệ có thể viết trong dạng

1 1 1 2 1
1
1
,( 2, , 1)
i i i i i i i
n n n n n
c x b x f
a x c x b x f i n
a x c x f
(1.18)
Giả sử
0,( 1, , )
i
c i n
. Từ phƣơng trình thứ nhất của hệ rút ra

11
12
11
bf
xx
cc

(1.19)
Thế biểu thức trên vào phƣơng trình thứ hai khi i = 2 ta rút đƣợc biểu
18

diễn của x
2
qua x
3
. Vì thế ta sẽ đi tìm nghiệm của hệ (1.18) trong dạng

1i i i i
xx
(1.20)
trong đó
i
,
i
là các hệ số cần xác định. Muốn vậy thế biểu thức
1 1 1i i i i
xx
vào phƣơng trình thứ
1( 2)ii
ta thu đƣợc biểu diễn của
i
x
qua
1i
x



1
1
11
i i i i
ii
i i i i i i
b f a
xx
c a c a

So sánh biểu diễn này với (1.20) ta rút ra

1
11
, , 2, , 1
i i i i
ii
i i i i i i
b f a
in
c a c a
(1.21)
Để ý đến (1.19) ta có

11
11
11
,
bf
cc

(1.22)
Nhƣ vậy theo các công thức (1.21), (1.22) ta lần lƣợt đƣợc các hệ số
, , 1, , 1
ii
in
. Khi
1in
công thức (1.20) cho ta
1 1 1n n n n
xx
. Thế
biểu thức này vào phƣơng trình cuối của hệ (1.18) ta tìm đƣợc

1
1
n n n
n
n n n
fa
x
ca

Sau khi biết
n
x
và các hệ số
,
ii
theo công thức (1.20) ta sẽ lần lƣợt
tính đƣợc

i
x
với
1, 2, ,1i n n
.
Tóm lại, phƣơng pháp này gồm hai quá trình sau:
* Quá trình truy đuổi xuôi:
Tính
11
11
11
,
bf
cc
,
1
11
, , 2, , 1
i i i i
ii
i i i i i i
b f a
in
c a c a

*Quá trình truy đuổi ngƣợc: Đặt
nn
x
tính
1

, 1, ,1
i i i i
x x i n

19

1.4. MỘT SỐ ĐỊNH NGHĨA VÀ KHÁI NIỆM CƠ BẢN
1.4.1. Định nghĩa bộ dữ liệu phân tán [8]
Cho bộ dữ liệu
,
ii
xy
,
1,2, ,in
,
d
i
xR
,
i
yR
, trong đó
i
x
là các
vị trí đo,
i
y
là các kết quả tại vị trí đo. Cho
12

, , ,
n
B B B
là các hàm cơ sở của
không gian tuyến tính các hàm liên tục
d
biến. Ký hiệu:
12
1
, , ,
n
n k k k
k
F span B B B c B c R
;
1.4.2. Một số định nghĩa liên quan đến hàm Radial Basis Function-RBF
[8]
Cho miền trong không gian Ơcơlit
d
R
với biên . Trong luận văn
này sẽ dùng thuật ngữ ―Tâm‖ nhƣ là một điểm thuộc miền .

Đinh nghĩa l.1. [9] (Tập các tập rời rạc .). Tập các tâm rời rạc . là tất cả
các tâm, bao gồm cả các tâm nằm trong miền và các tâm nằm trên biên.

Định nghĩa 1.2. [8] (Hàm bán kính) Hàm
:
d
RR

đƣợc gọi là hàm bán
kính nếu tồn tại hàm một hàm
: 0, R
sao cho
xx
với mọi
d
xR
.
trong đó ||x||
2
là chuẩn Euclide.
Định nghĩa 1.3. [8] (hàm xác định dƣơng) Hàm
:
d
RR
liên tục, đƣợc gọi
là xác định dƣơng trên
d
R
nếu và chỉ nếu nó là hàm chẵn và với mọi bộ tâm
phân biệt từng đôi một
12
, , , ,
d
n
X x x x R n
và mọi véc tơ
c
2

, , ,
n
n
c c c R
thì dạng toàn phƣơng:

11
0
nn
j k j k
jk
c c x x
(1.23)
Và công thức (1.23) là đẳng thức khi và chỉ khi c là véc tơ 0.
20


Định nghĩa 1.4. [8] hàm một biến
: 0, R
đƣợc gọi là xác định dƣơng
trên
d
R
nếu hàm nhiều biến tƣơng ứng
xx
,
d
xR
là xác định dƣơng.
1.4.3. Định nghĩa véc tơ trọng số [8]

Cho D là toán tử vi phân tuyến tính và
12
, ,
n
X x x x
là bộ tâm phân tán
đã đƣợc chọn trong không gian
d
R
. Một xấp xỉ vi phân tuyến tính đối với
toán tử D.

1
w
n
ii
i
Du x x u x
(1.24)
đƣợc xác định bởi các trọng số
ww
ii
x
. Khi đó
12
w w ,w ,w
n
đƣợc
gọi là véc tơ trọng số hay còn đƣợc gọi là stencil đối với toán tử vi phân D.
1.5. NỘI SUY HÀM RBF

1.5.1. Nội suy dữ liệu phân tán trong không gian
d
R
[8]
Cho bộ dữ liệu
,
ii
xy
,
1,2, ,in
,
d
i
xR
.
bài toán nội suy: tìm hàm
Pf F
sao cho

ii
Pf x y
,
1,2, ,in
; (1.25)
Vì
Pf F
nên:

1
()

n
kk
k
Pf x c B x
,
d
xR
; (1.26)
Từ (1.25) và (1.26) ta có:

Ac y
, (1.27)
trong đó:
1 1 1
1
( ) ( )

( ) ( )
n
n n n
B x B x
A
B x B x


(1.28)
21


1

,
T
n
c c c

1
, ,
T
n
y y y
.
Bài toán (1.27) và (1.28) có thể giải đƣợc nếu
detA 0
.
Định nghĩa 1.5. [8] Cho
d
R
và
()FC
là không gian tuyến tính hữu
hạn chiều có cơ sở là
12
, , ,
n
B B B
. Ta nói F là không gian Haar trên nếu
detA 0
với mọi bộ tâm phân biệt từng đôi một
12
, ., ,

n
x x x
trong , trong
đó ma trân A đƣợc định nghĩa bởi (1.28).
Định lý 1.1. [8] (Mairhuber Curtis) Giả sử rằng
,2
d
Rd
, 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
.
Định lý Mairhuber Curtis cho thấy rằng nếu muốn giải đƣợc bài toá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 dƣơng và ma trận xác định dƣơng.
1.5.2. Nội suy với hàm cơ sở theo bán kính [8]
Ta ký kiệu:

( ) ( )
k k k
x x x x x
với
1,2, ,kn
,
d
xR
(1.29)
Khi đó, nội suy hàm số dựa trên các hàm cơ sở bán kính có nghĩa là tìm hàm:
11
()

nn
k k k k
kk
Pf x c x c x x

Tên hàm
Viết tắt
Định nghĩa
Multiquadric
MQ
mq
(r) =
2
1r

Inverse
multiquadric
IMQ
imq
(r) = 1/
2
1r

Gaussian
Gauss
g
(r) =
2
r
e


Wendland‘C
6

W33
8
32
w33
r 1 r 32 (r) 25 (r ) 8r 1

Bảng1.1: Một số hàm cơ sở bán kính dùng trong báo cáo, trong đó
k
r x x
.
22

Vì hàm (x) vẫn là xác định dƣơng khi
r
đƣợc nhân một số lớn hơn
không, nên một tham số hình dạng >0 đƣợc đƣa vào hàm và ta có bảng
1.2 tƣơng ứng.
Tên hàm
Viết tắt
Định nghĩa
Multiquadric
MQ
mq
( r) =
22
r


Inverse multiquadric
IMQ
imq
( r) = 1/
22
r

Gaussian
Gauss
g
( r) =
2
()r
e

Wendland‘C
6

W33
8
32
w33
r 1 r 32 ( r) 25 ( r ) 8 r 1

Bảng 1.2: Một số hàm cơ sở bán kính với tham số hình dạng >0.
Giả sử
()x
là hàm xác định dƣơng và đƣợc xác định theo công thức
(1.29). Khi đó mà trận A của bài toán nội suy theo hàm

()x
có dạng

1
12
21
2
12
()
(0) ( )
()
()
(0)

( ) ( ) (0)
n
n
nn
xx
xx
xx
xx
A
x x x x

(1.30)
C =
1
, ,
T

n
cc
, y =
1
, ,
T
n
yy

Theo định nghĩa hàm xác định dƣơng thì det A ≠ 0, hơn nữa A là ma trận
đối xứng và xác định dƣơng.
1.6. PHƢƠNG PHÁP SAI PHÂN HỮU HẠN (Finite Different - FD) [12]
1.6.1. Bài toán

Cho
:fR
và
:gR
là các hàm liên tục. Tìm hàm
2
uC
sao
cho:

uf
trong Ω (1.31)
23


ug

(1.32)
Lƣu ý rằng tất cả các chuẩn
.
trong luận văn này là chuẩn Ơcơlit
2
.
.
1.6.2. Rời rạc bài toàn Dirichlet
Bài toán (1.31) và (1.32) có thể đƣợc rời rạc với sự trợ giúp của công
thức
i
1
( ) ( ) ( )
n
i
i
Du x w x u x
nhƣ sau:
Cho là tập hữu hạn các tâm rời rạc. Kí hiệu:
:
và
int

:= \ . Với mỗi
int
, ta chọn một công thức vi phân tuyến tính đối với
toán tử Laplace ,

,
wuu

(1.33)
với là bộ tâm cho tính véc tơ trọng số
,,
,
ww
R. Ta thay thế
các
,
w
vào bài toán (1.31) và (1.32), cuối cùng ta đƣợc hệ phƣơng trình


,
w,uf

int
(1.34)


,ug
(1.35)
Nếu hệ phƣơng trình (1.34) – (1.35) không suy biến, tìm véc tơ nghiệm
xấp xỉ của hệ phƣơng trình này có thể so sánh đƣợc với véc tơ
u
là nghiệm
chính xác của bài toán (1.31) – (1.32).
1.6.3. Lƣợc đồ sai phân hữu hạn giải bài toán Dirichlet với phƣơng trình
Poisson
Phƣơng pháp sai phân hữu hạn thông thƣờng thu đƣợc từ trên nếu miền
Ω R

2
là hình vuông hoặc hình chữ nhật. Trong trƣờng hợp miền Ω là hình
24

vuông và là tập các điểm nằm trên lƣới đều với bƣớc lƣới h thì công thức
(1.33) là sai phân khuông 5- điểm đối với toán tử Laplace, hay

u

2
1
,0 ,0 0, 0, 4u h u h u h u h u
h

Khi đó, véc tơ trọng số
W =
2 2 2 2 2
1 ,1 ,1 ,1 , 4 ,h h h h h
trong đó
2
,
w4h

Nhận xét 2.1. Trong trƣờng hợp miền Ω là hình chữ nhật hoặc hình
vuông thì phƣơng pháp sai phân hữu hạn đơn giản vì các véc tơ trọng số
giống nhau nên không cần chi phí tính các véc tơ trọng số và tốc độ hội tụ là
O(h
2
).
Ƣu điểm : Dễ dàng thực hiện trên miền hình chữ nhật

Nhƣợc điểm : Khó khăn khi thực hiện trên các miền có hình học phức tạp





25

CHƢƠNG 2
MỘT SỐ PHƢƠNG PHÁP XÂY DỰNG BỘ DỮ LIỆU PHÂN TÁN
TRONG KHÔNG GIAN 2D
2.1. PHƢƠNG PHÁP RBF-FD (Radial Basis Function Finite Different)

2.1.1. Véc tơ trọng số dựa vào hàm nội suy theo cơ sở bán kính

Cho : [0; ) —> R là hàm xác định dƣơng, : R
d
—> R là hàm
bán kính thỏa mãn (x) := ||
x
||
2
), ||
x
||
2
là chuẩn Euclide của
x
.
X ={

x
1
,
x
2
, ,
x
n
} R
d
là bộ tâm phân biệt từng đôi một, u : R
d
—> R là
hàm liên tục. Khi đó, s là hàm nội suy cơ sở theo bán kính của hàm u đƣợc
viết dƣới dạng:

1
( ) ( )
n
jj
j
s x a x x
, (2.1)

( ) ( )
ii
s x u x
, i =1,2, ,n (2.2)
trong đó
j

a
đƣợc chọn sao cho thỏa mãn điều kiện nội suy (2.2) nghĩa là

1
( ) ( ) ( ),
n
i j i j i
j
s x a x x u x
i =1,2, ,n (2.3)
Ký hiệu:
,
,1
| ( )
nn
X i j
ij
xx
,
12
| ( ), ( ), , ( )
T
Xn
u u x u x u x
,
12
, , ,
T
n
a a a a


Khi đó ta có thể viết (2.3) dƣới dạng ma trận:

| | .
XX
au

Vì là hàm xác định dƣơng nên ma trận
|
X
là xác định dƣơng với bộ tâm x
phân biệt từng đôi một. Do đó, véc tơ a đƣợc xác định duy nhất bởi:

1
||
XX
au
(2.4)