Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
ĐẠI HỌC THÁI NGUYÊN
KHOA CÔNG NGHỆ THÔNG TIN Cao Thị Anh Thư

Mô hình tính toán song song giải các bài toán biên phức tạp dựa
trên tư tưởng chia miền

Chuyên 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

Người hướng dẫn Khoa học:
TS. Vũ Vinh Quang


1.3.1 Bài toán biên Dirichlet
15
1.3.2 Bài toán biên hỗn hợp
16
1.4 PHƯƠNG PHÁP LẶP VÀ CÁC SƠ ĐỒ LẶP CƠ BẢN
18
1.4.1 Không gian năng lượng
18
1.4.2 Phương pháp lặp giải phương trình toán tử
19
Chương 2: Cơ sở Toán học của phương pháp chia miền
27
2.1 CÔNG THỨC ĐA MIỀN VÀ PHƯƠNG TRÌNH STEKLOV- POICARE
28
2.2 CÁC PHƯƠNG PHÁP LẶP ĐƠN CƠ SỞ
30
2.2.1 Phương pháp Dirichlet-Neumann
30
2.2.2 Phương pháp Neumann-Neumann
31
2.2.3 Phương pháp Robin
31
2.3 MỘT SỐ THUẬT TOÁN CHIA MIỀN
33
2.3.1 Thuật toán chia miền Patrick Le Talle.
33
2.3.2 Thuật toán chia miền J.R.Rice, E.A. Vavalis, Daopi Yang
35
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
2.3.3 Thuật toán chia miền Saito-Fujita

63
DANH MỤC CÔNG TRÌNH ĐÃ CÔNG BỐ LIÊN QUAN ĐẾN LUẬN
VĂN

64
TÀI LIỆU THAM KHẢO
65
PHỤ LỤC
68
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

1
LỜI CẢM ƠN
Sau một thời gian nghiên cứu và thực hiện luận văn thạc sỹ chuyên
ngành Khoa học máy tính, đến nay luận văn :"Mô hình tính toán song song
giải các bài toán biên phức tạp dựa trên tư tưởng chia miền" của tôi đã được
hoàn thiện và đầy đủ. Để có được kết quả như mong muốn tôi luôn nhận được
sự quan tâm, chỉ bảo sự giúp đỡ từ thầy giáo hướng dẫn: Tiến sĩ Vũ Vinh
Quang - Phó trưởng Khoa Công nghệ thông tin- Đại học Thái Nguyên. Nhân
dịp này tôi xin trân trọng gửi lời cảm ơn của mình tới các thầy giáo, các vị
giáo sư của Viện Công nghệ Thông tin, các thầy cô giáo thuộc Khoa Công
nghệ thông tin - Đại học Thái Nguyên đã truyền đạt những kiến thức bổ ích
cho các học viên cao học khoá 6 nơi tôi được học tập và nghiên cứu trong
suốt 2 năm qua. Tôi xin bày tỏ tình cảm và lời cảm ơn chân thành nhất tới các
đồng nghiệp Viễn thông Thái Nguyên, tới bạn bè người thân và gia đình đã
khích lệ, động viên, giúp đỡ tôi trong thời gian qua.
Một lần nữa tôi xin gửi lời cảm ơn sâu sắc nhất tới thầy giáo Vũ Vinh

lượng tính toán giải phương trình lưới và cơ sở lý thuyết về các sơ đồ lặp tổng
quát.
Chương 2: Trình bày tóm tắt cơ sở toán học về phương pháp chia
miền, các sơ đồ lặp cơ bản trong phương pháp chia miền. Một số phương
pháp chia miền của các tác giả trên thế giới và đặc biệt là các sơ đồ lặp trên tư
tưởng hiệu chỉnh hàm hoặc đạo hàm trên biên phân chia của các tác giả Việt
Nam và Nhật Bản, phương pháp chia miền đối với bài toán biên gián đoạn
mạnh.
Chương 3: Trên cơ sở của các sơ đồ lặp theo hướng hiệu chỉnh hàm và
đạo hàm, luận văn đề xuất sơ đồ tính toán song song dựa trên tư tưởng hiệu

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

3
chỉnh hàm hoặc đạo hàm, tiến hành tính toán bằng số so sánh hai sơ đồ tính
toán song song và đồng thời áp dụng phương pháp song song giải quyết một
bài toán cơ học được các tác giả trên thế giới quan tâm.
Các kết quả lý thuyết được kiểm tra bằng các chương trình thực
nghiệm lập trình trong môi trường MATLAB trên máy tính PC.
u g x
  


 

(1.1)
trong đó
 
2
( , ) , ,x y R a x b c y d      
, chọn 2 số nguyên
>1N
và
>1M
, đặt
= ( ) /h b a N
gọi là bước lưới theo
x
,
= ( ) /k d c M
gọi là
bước lưới theo
y
. Đặt
= , = , 0 , 0 .
ij
x a ih y c jk i N j M   
Mỗi điểm
( , )

( , )u x y
xác định tại mọi
( , )xy
tạo ra hàm lưới
u
xác định bởi
,ij
u
.
Bài toán sai phân: Ký hiệu
Lu f
là tập các hàm số hai biến
,xy
có
các đạo hàm riêng đến cấp
m
liên tục trong
= 
Giả sử bài toán có
nghiệm
4
()uC
, khi đó:

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

5
4
1
( , )




2 2 3 3
4
23
= ( , ) ( )
2! 3!
ij
u h u h u
u x y h o h
x x x
  
   
  
hay
2
11
2
22
( , ) 2 ( , ) ( , )
= ( )
i j i j i j
u x y u x y u x y
u
oh
hx





2 2 3 3
4
23
= ( , ) ( )
2! 3!
ij
u k u k u
u x y k o k
y y y
  
   
  

Do đó:
2
11
2
22
( , ) 2 ( , ) ( , )
= ( )
i j i j i j
u x y u x y u x y
u
ok
ky






Khi đó chứng tỏ:
22
= ( )
kh
u u o h k   Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

6
Số hạng
22
O(h +k )
là một vô cùng bé bậc hai. Ta nói toán tử
kh

xấp xỉ
toán tử , điều đó cho phép

thay phương trình vi phân bằng phương trình sai
phân:
= , = ( , ), ( , )
hk ij ij i j i j hk
u f f f x y x y 

tức là:
1, , 1 , 1 , ,
22
2 2 1

1.2.1 Bài toán biên thứ nhất
Xét bài toán biên thứ nhất đối với phƣơng trình véc tơ ba điểm

11
=
j j j j
Y CY Y F

  
,
11jN  
,
00
=YF
,
=
NN
YF
. (1.4)
Trong đó
j
Y
là véc tơ cần tìm,
C
là ma trận vuông,
j
F
là véc tơ cho
trước. ý tưởng của phương pháp rút gọn hoàn toàn giải (1.1) là khử liên tiếp
các ẩn

N
Y
. Sau khi đã có
được
0 /2
,
N
YY
và
N
Y
thì quá trình ngược lại là việc tìm các
j
Y
với
j
là bội của
4
N
rồi bội của
8
N
,… Rõ ràng, phương pháp rút gọn hoàn toàn là một biến
thể của phương pháp khử Gauss áp dụng cho bài toán (1.4) trong đó việc khử
các biến được thực hiện theo một thứ tự đặc biệt. Sau đây, ta sẽ mô tả cụ thể
phương pháp. Giả sử
= 2 , > 0
n
Nn
Ký hiệu

2 1 1
=
j j j j
Y C Y Y F
  
  
,
(0) (0)
11
=
j j j j
Y C Y Y F

  
,
(0) (0)
1 2 1
=
j j j j
Y C Y Y F
  
  

Nhân 2 vế của phương trình thứ hai với
(0)
C
vào bên trái rồi cộng cả 3
phương trình lại ta được

(1) (1)

j
chẵn, số véc tơ ẩn
j
Y
là
1
2
N

. Do đó nếu giải được hệ này thì các
j
Y
với
j
lẻ sẽ tìm được từ phương
trình

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

8

(0) (0)
11
= , =1,3, , 1
j j j j
C Y F Y Y j N

  
(1.7)
Như vậy hệ (1.5) tương đương với hệ gồm (1.6) và (1.7).

(1)
C
vào bên trái rồi cộng cả 3
vế phương trình lại ta được

(2) (2)
44
= , = 4,8, , 4
j j j j
Y C Y Y F j N

   
,
00
=YF
,
=
NN
YF
(1.8)
trong đó:
(2) ( 2
= ( 1)) 2C C E

(2) (1) (1) (1) (1)
22
= , = 4,8, , 4
j j j j
F F c F F j N


ta nhận
được một hệ gồm
1
l
N
c

ẩn
j
Y
, trong đó
j
là bội của
2
l( ) ( )
22
= , = 2 ,2.2 ,3.2 , , 2
l l l l l l
l j l j
jj
Y C Y Y F j N

   
,
00
=YF
,

9
trong đó các ma trận
()k
C
và các véc tơ vế phải
()k
j
F
được tính theo các công
thức truy toán:
( ) ( 1) 2
= ( ) 2
kk
C C E


,
( ) ( 1) 1 ( 1)
11
22
=
k k k k
j k j k
jj
F F C F F
  



,

/2N
Y
, và tất cả
các ẩn còn lại được tìm liên tiếp từ các phương trình
( 1) ( 1)
11
22
00
1 1 1 1
=,
=
=
= 2 ,3.2 ,5.2 , , 2 ,
= , 1, ,1
kk
j j k k
jj
NN
k k k k
C Y F Y Y
YF
YF
jN
k n n



   



véc tơ
()k
j
p
và
()k
j
q
liên hệ với theo công thức sau:
( ) ( ) ( ) ( )
= , = 2 ,2.2 ,3.2 , 2 , = 0,1,2, , 1
k k k k k k k k
j j j
F C p q j N k n  
(1.14)

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

10
trong đó ta chọn
(0)
j
p
và
(0)
= , =1,2, , 1
jj
q F j N 
. Bằng các công thức toán
học, có thể thấy mối quan hệ mà

Ta sẽ chọn
()k
j
p
và
()k
j
q
thoả mãn
( ) ( ) ( 1) ( 1)
2 ( 1) 2 ( 1)
=2
k k k k
j j j k j k
q p q q

   


Khi đó, kết hợp với công thức
( ) ( 1) 2
2 = [ ]
kk
C E c


ta có
( ) ( ) ( 1) ( 1) ( 1) ( 1) ( 1)
11
22

jj
C S q p p
    




Như vậy ta thu được thuật toán sau đây để xác định các véc tơ
()k
j
p
và
()k
j
q

( 1) ( 1) ( 1) ( 1) ( 1)
11
22
=
k k k k k
j j k k
jj
C S q p p
    



,
( 1) ( ) ( 1)

=
kk
j j j
t Y p


, ta sẽ thấy rằng
j
Y
có thể tính được từ các
công thức sau
( 1) ( 1) ( 1)
11
22
=
k k k
j j k k
jj
C t q Y Y
  



,
( 1) ( 1)
=
kk
j j j
Y p t


k
k
C T C
, ta có
1
( 1) 2
( =1) , 1
=
k
k
l l k
CC




,
trong đó

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

11
,1
(2 1)
= 2cos
2
lk
k
l
C C E

1
2
=
k



Tóm lại qua các bước phân tích trên đây ta có thuật toán rút gọn hoàn
toàn giải bài toán biên thứ nhất như sau
 Quá trình xuôi
Bước 1.1 Cho các giá trị ban đầu
(0) (0)
, = , =1,2,3, , 1
j j j
p q F j N 

Bước 1.2 Với
=1k
giải phương trình
(1) (0)
=
jj
Cp q
và tính
(1) (1) (0) (0), =2,4,6, , 2
( 1) ( 1)
=2
jN
j j j j
q p q q

jN
, giải
phương trình
( ) ( 1)
,1
=
ll
l k j j
C




Khi đó
1
( ) ( 1) (2 )
=
k
kk
j j j
pp




,
( ) ( ) ( 1) ( 1)
11
( 2 ) 2
= 2 , = 2 ,2.2 ,3.2 , 2

q Y Y j N

   


  

Sau đó, với mỗi
1
=1,2, ,2
k
l

và với mỗi
1 1 1
= 2 ,3.2 2
k k k
jN
  

, giải
phương trình
( ) ( 1)
,1
=
ll
l k j j
C



11
1
= , = 0,
= ,1 1,
2 = .
j j j j
N N N
Y F j
Y CY Y F j N
Y CY F




     




(1.18)
trong đó
= 2 , > 0
n
Nn
Để giải bài toán (1.18) ta cũng thực hiện các bước khử
lần lượt như đã được trình bày ở bài toán biên thứ nhất. Sau n phép khử, ta
nhận được các phương trình

( ) ( ) ( )
0 0 (0)

13
()
00
( ) 1 ( 1) ( 1)
1 1 1
12
( ) 1 ( 1) ( 1)
1
2
( ) ( 1) 2
=,
=,
= 2 ,2.2 , , 2
= 2 ,
=[ ] 2 ,
k
k k k k
j k j k
jj
k k k
k k k k
N k N
N
kk
FF
F F C F F
jN
F F C F
C C E
  

thích hợp,
ta nhận được quá trình sau để xác định các véc tơ
()k
j
p
và
()k
j
q
với
JN

( 1) ( 1) ( 1) ( 1) ( 1)
( 1) ( 1)
22
( ) ( 1) ( 1)
( ) ( ) ( 1) ( 1)
( 1) ( 1)
22
(0) (0)=0
=
=,
= 2 ,
= 2 ,3.2 , , 2 , = 0,1,2, , 1
=,
k k k k k
j j k k
jj
k k k
j j j

( 1)
2
(0) (0)
= 2 ,
=,
= 2 2 ,
= ; = 0,
k k k k
N N k
N
k k k
N N N
k k k
N N k
N
N N N
C S q p
p p S
q p q
q F p
   










( 1) ( 1)
22
=
k
kt
k
j
j k k
jj
C q Y Y






,
Tóm lại, ta có thuật toán sau đây giải bài toán biên thứ hai.
 Quá trình xuôi
Bước 1.1 Xác định các giá trị ban đầu
(0) (0)
= 0; = , =1,2, ,
j j j
p q F j N

Bước 1.2 Với
=1,2, , 1kn
xác định các véc tơ:
(0) ( 1) ( 1) ( 1)
( 1) ( 1)

ll
l k j j
C v v



Khi đó
( ) ( 1) (2 1)
=
k k k
j j j
p p v


,
( ) ( ) ( 1) ( 1)
( 1) ( 1)
22
=2
k k k k
J j k k
jj
q p q q




,
= 2 ,2.2 , , 2
k k k

C v v



Khi đó
1
( ) ( 1) (2 )
=
k
kk
N N N
P p v



,
( ) ( ) ( 1)
1
2
= 2 2
k k k
N N k
N
q p q





 Quá trình ngƣợc

N N N
Y p v

Bước 2.2 Xác định
, =1,2, , 1
j
Y j N 

Với
= , 1, ,2,1,k n n 
xác định các véc tơ
(0) ( 1)
( 1) ( 1)
22
=
k
j j k k
jj
v q Y Y




,
1 1 1
= 2 ,3.2 , , 2
k k k
jN
  


k
j j j
Y p v



,
= 2 ,2.2 ,3.2 , 2
k k k k
jN
.
Trên đây là nội dung của thuật toán thu gọi khối lượng tính toán giải
bài toán biên thứ nhất và bài toán biên thứ hai. Trong các tài liệu của
Samaski-Nicolaev [21] đã chứng minh độ phức tạp của các thuật toán là
O
( log )M N N
.
1.3 Áp dụng đối với phƣơng trình elliptic
Trên cơ sở phương pháp lưới, ta thu được các kết quả xây dựng lược
đồ sai phân cho các bài toán Dirichlet và bài toán Neumann
1.3.1 Bài toán biên Dirichlet
Cho

là hình chữ nhật
 
2
1 2 1 1 2 2
= = ( , ) :0< < ;0< <x x x R x l x l

Xét bài toán

1
=
l
h
M
;
2
2
=
l
h
N
;
= 0,1, ,iM
;

= 0,1, ,jN
.
Bằng cách biến đổi đơn giản ta có thể đưa bài toán sai phân tương ứng
về hệ phương trình vec tơ 3 điểm có dạng như sau:
11
= , =1,2, , 1
j j j j
Y CY Y F j N

   

00
= ; =
NN

0 0 0 2( 1)
0 0 0 0 2( 1)
rr
r r r
rr
rr
r r r
rr



  








  




      2
2 1, 0,





Với
2
2
2
1
=
h
r
h

1.3.2 Bài toán biên hỗn hợp

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

17
Cho miền
 
1 2 1 1 2 2
= = ( , );0 < < ;0 < <x x x x l x l

Xét bài toán biên hỗn hợp
= ( );u x x

 

 
2 1 2 1 1
= = ( , );0x x l x l  

Tương tự, ta đưa bài toán sai phân về hệ phương trình vec tơ 3 điểm
00
=YF11
= 1 1
j j j j
Y CY Y F j N

     
(1.23)
1
2 = =
N N N
Y CY F j N



Trong đó:
0 1,0 2,0 1,0
= ( , , , )
T
M
F y y y






  




      

2
2 1, 0,
2
2 2,
2
2 2,
2
2 1, ,
jj
j
j
Mj
M j M j
h rg
h
F
h
h rg

2 1, 2 1, ,
2
2
2
2
N N N
NN
N
M N M N
M N M N M N
h h rg
hh
F
hh
h h rg
















2
( , ) , ( ).Au u u u D A

  Trong miền xác định
()DA
, xét phiếm hàm song tuyến tính
( , )Au v
mà
ta kí hiệu là
( , ) =[ , ]Au v u v
.
Ta thấy, phiếm hàm
[ , ]uv
trong
()DA
thỏa mãn mọi tiên đề của tích vô
hướng trong không gian Hilbert trừu tượng nói chung. Thật vậy, ta có

[ , ] = ( , ) = ( , ) = ( , ) = [ , ],u v Au v u Av Av u v u

1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2
[ , ]= ( ( ), ) = ( , ) ( , ) [ , ] [ , ],u u v A u u v Au v Au v u v u v
       
    

[ , ] = ( , ) 0,[ , ] = ( , ) = 0u u Au u u u Au u
khi và chỉ khi

được định
nghĩa trùng với các phép toán trong
H
.
 Chuẩn của các phần tử trong
A
h
được định nghĩa bởi (1.21).
Không gian
A
h
được định nghĩa như vậy có thể là một không gian
không đủ. Trong trường hợp này, ta làm đủ không gian
A
h
bằng phương pháp
bổ sung không gian Metric để được không gian đủ
A
H
. Không gian
A
H
này
được gọi là không gian năng lượng của toán tử
A
.
Như vậy,
A
H
gồm những phần tử cũ thuộc

Tích vô hướng của hai phần tử
,
A
u v H
được xác định bởi

[ , ] = [ , ],
lim
A n n
n
u v u v


trong đó
{ },{ }
nn
uv
là dãy cơ bản các phần tử thuộc
()DA
xác định
,uv
.
Không gian
A
H
với tích vô hướng trên là không gian Hilbert.
Ta thường nói gọn là: Không gian năng lượng
A
H
là không gian

fH
là vectơ tùy ý.
Trong mỗi phương pháp lặp, xuất phát từ
0
y
bất kỳ thuộc
H
, người ta đưa ra
cách xác định nghiệm xấp xỉ
12
, , , ,
k
y y y
của phương trình (1.25). Các xấp
xỉ như vậy được biết như là các giá trị lặp với chỉ số lặp
=1,2, k
Bản chất
của những phương pháp này là giá trị
1k
y

có thể được tính thông qua các giá
trị lặp trước:
1
, ,
kk
yy

.
Phương pháp lặp được gọi là phương pháp lặp một bước hoặc hai bước

là hàm biết trước phụ thuộc
k
và
k
y
là giá trị lặp thứ
k
. Giả thiết rằng
1
k
B

tồn tại với mọi
k
.
Một đòi hỏi tự nhiên là nghiệm chính xác
u
của phương trình (1.25)
không phụ thuộc vào
k
, thoả mãn phương trình (1.26).
( ) =
k k k
B C u F

Nhưng điều đó chỉ xảy ra nếu
1
( ) =
k k k
B C A f F




,
1
=
kk
Ff


,
= 0,1,2, k

ở đây
>0
k

là tham số.
Dạng chính tắc của lược đồ lặp hai lớp là

1
1
= , = 0,1,2,
kk
kk
k
yy
B Ay f k





(1.28)
hoặc dạng tương tự
1
1 1 1
= = ,
k k k k k k k k
y y B r y
  

  


trong đó
=
kk
r Ay f
là độ không khớp và
1
=
k k k
Br


là phần hiệu chỉnh.
Với
k
y
đã biết, giá trị của

22
.
kk
y u y u

  
(1.29)
Vì véctơ
u
chưa biết nên ta thay điều kiện (1.29) bằng bất đẳng thức
cho độ không khớp
0
.
k
Ay f Ay f

  
(1.30)
Ta chấp nhận điều kiện dừng

0
.
k
DD
y u y u

  
(1.31)
Trong đó
D

được biết.
Từ (1.32) ta thấy
1
1 1 1 1
= , = ,
k k k k k k
z S z S E B A


   


trong đó
1k
S

là toán tử chuyển tiếp từ lớp thứ
k
tới lớp thứ
1k 
. Với
=1kn
ta có
0 1 2 1
= , = .
n n n n n
z T z T S S S S


Ta có đánh giá