Mô hình tính toán song song giải bài toán biên hỗn hợp mạnh dựa trên chia miền

 Tạp chí Khoa học & Công nghệ - số 2(50)/năm 2009 Toán, Thống kê –KH tự nhiên –KH máy tính 
1 
MÔ HÌNH TÍNH TOÁN SONG SONG 
GIẢI BÀI TOÁN BIÊN HỖN HỢP MẠNH DỰA TRÊN CHIA MIỀN 
Vũ Vinh Quang – Trương Hà Hải – Cao Thị Anh Thư (Khoa Công nghệ thông tin – ĐH Thái Nguyên) 
1. Phương pháp chia miền giải bài toán biên gián đoạn mạnh 
Phương pháp chia miền đã được phát triển trong nhiều năm qua với mục đích chính là 
đưa ra phương pháp giải các bài toán biên trong miền hình học phức tạp hoặc điều kiện biên 
phức tạp bằng cách chuyển việc giải bài toán phức tạp về một số hữu hạn các bài toán đơn giản. 
Với tư tưởng trên, nhiều tác giả đã nghiên cứu và đề xuất các phương pháp hiệu quả như: 
Phương pháp hiệu chỉnh hàm (Saito-Fujita [1,2]), phương pháp hiệu chỉnh đạo hàm (DQuangA-
VVQuang [3,4,5,6,7]). Tuy nhiên, theo chúng tôi, trên thế giới chưa có công trình nào đưa ra kết 
quả tìm nghiệm gần đúng của các bài toán biên với điều kiện biên rất phức tạp trên cơ sở chia 
miền. Vì vậy, trong bài báo này, chúng tôi đề xuất các mô hình tính toán song song để giải các 
bài toán trên. 
Xét bài toán 
.\,
,,
,,
n
n
xu
x
n
u
xfu
 (1) 
Bài toán (1) được gọi là bài toán biên hỗn hợp mạnh vì trên biên d n gồm hai loại 
điều kiện biên Dirichlet và Neumann. Xuất phát từ tư tưởng chia miền, để giải quyết bài toán 
trên, ta chia miền 1 2 bởi biên phân chia (Hình 1), kí hiệu 1u là nghiệm trong miền 
1 , 2u là nghiệm trong miền 2 . Khi đó để giải bài toán (1), điểm mấu chốt là cần xác định 
được điều kiện trên biên phân chia . Sau đây ta xét cơ sở của hai phương pháp chia miền 
1.1. Phương pháp hiệu chỉnh hàm (Được đề xuất bởi Saito –Fujita, 2001) 
 Kí hiệu 2ug , khi đó giá trị g được xác định bởi sơ đồ lặp sau đây: 
Bước 1: Cho trước ( 0 )g xác định trên 2L , chẳng hạn ( 0 )g = 0. 
Bước 2: Với ( k )g xác định trên (k = 0, 1, 2,) tiến hành giải hai bài toán 
.,
,,
,\,
,,
2
)(
2
)()(
2
2
)(
2
2
)(
2
n
k
kk
d
k
k
x
n
u
xgu
xu
xfu
,\,
,,
,,
1
)(
1
2
)(
2
1
)(
1
1
)(
1
xu
x
n
u
n
u
xfu
k
kk
k
 (2) 
Bước 3: Hiệu chỉnh giá trị 
( k 1 )g theo công thức 
.,)1( )(1
)()1( xugg kkk (3) 
Trên cơ sở của lí thuyết các không gian hàm và toán tử Steklov-Poincare trong [1,2] các 
tác giả Saito –Fujita đã chứng minh sơ đồ lặp trên là hội tụ. 
1.2. Phương pháp hiệu chỉnh đạo hàm (Được đề xuất bởi Đ.Q.A – V.V. Quang, 2004) 
 Tạp chí Khoa học & Công nghệ - số 2(50)/năm 2009 Toán, Thống kê –KH tự nhiên –KH máy tính 
2 
Kí hiệu 
1
1
n
u
g , khi đó giá trị g được xác định bởi sơ đồ lặp sau đây: 
Bước 1: Cho trước ( 0 )g xác định trên 2L , chẳng hạn ( 0 )g = 0. 
Bước 2: Với ( k )g xác định trên (k = 0, 1, 2,) tiến hành giải hai bài toán 
,\,
,,
,,
1
)(
1
)(
1
)(
1
1
)(
1
xu
xg
n
u
xfu
k
k
k
k
.,
,,
,\,
,,
2
)(
2
)(
1
)(
2
2
)(
2
2
)(
2
n
k
kk
n
k
k
x
n
u
xuu
xu
xfu
 (4) 
Bước 3: Hiệu chỉnh giá trị ( k 1 )g theo công thức 
.,)1(
2
)(
2)()1( x
n
u
gg
k
kk (5) 
trong đó là tham số lặp cần xác định.Trên cơ sở của lí thuyết các không gian hàm và toán tử 
Steklov-Poincare trong [3,4,5] các tác giả đã chứng minh sơ đồ lặp trên là hội tụ. 
Có thể thấy rằng, hai phương pháp trên xuất phát từ hai tư tưởng hoàn toàn ngược nhau. 
Về mặt lí thuyết, việc chứng minh phương pháp nào hội tụ nhanh hơn là một bài toán khó, tuy 
nhiên qua thực nghiệm có thể khẳng định phương pháp Đặng Quang Á - Vũ Vinh Quang hội tụ 
có phần nhanh hơn do việc hiệu chỉnh đạo hàm [8]. 
2. Mô hình tính toán song song giải bài toán biên gián đoạn mạnh 
Mục đích chính của phương pháp chia miền là đưa ra một phương pháp hữu hiệu để giải 
quyết các bài toán phức tạp về miền hình học và điều kiện biên trong các mô hình thực tế, trong 
phần này chúng tôi sẽ trình bày các hướng đề xuất mô hình tính toán song song giải các bài toán 
biên với điều kiện biên rất phức tạp trên cơ sở chia miền. 
Xét bài toán biên: 


)...1(,,\,
),..1(,,
,,
2,4
2,4
nixu
nix
n
u
xfu
i
i
 (6) 
41 42 43 
12,4 l l2,4 12,4 l 
12,4 n 
1 
1 
2 
2 
3 
3 
. 
12l 
12l 
l2 
l2 
12l 
12l 
. 
12n 
n2 
Hình 2 
Trong đó 
1
2 2f L ; H , n là vectơ pháp tuyến ngoài của miền . Trên thế 
giới theo chúng tôi chưa có công trình nào đưa ra kết quả tìm nghiệm gần đúng của bài toán trên. 
Xuất phát từ các sơ đồ chia miền theo hướng hiệu chỉnh hàm và đạo hàm, trong phần này chúng 
tôi đề xuất các mô hình tính toán song song giải bài toán như sau: 
2.1. Hướng tiếp cận hiệu chỉnh đạo hàm 
 Tạp chí Khoa học & Công nghệ - số 2(50)/năm 2009 Toán, Thống kê –KH tự nhiên –KH máy tính 
3 
Chia 
2n 1
i
i 1
 bởi các biên phân chia i( i 1..2n ) , (Hình 2). 
Kí hiệu ),...2,1(,,
212
2
2
2
2
2
12 ni
n
u
g
n
u
g
ii
i
i
i
i
i
i . Việc giải bài toán (6) được thực hiện 
bởi sơ đồ lặp sau đây: 
Bước 1: Xuất phát ( 0 )
ig 0,i 1,2,...,2n . 
Bước 2: Tiến hành giải song song các bài toán trong các miền lẻ 
,\,
,,
,,
11
)(
1
1
)(
1
1
)(
1
1
)(
1
xu
xg
n
u
xfu
k
k
k
k
 (7) 
,,
,,
,\,
,,
12
)(
12
12
)(
12
22
)(
22
12
)(
12
21212
)(
12
12
)(
12
l
k
l
l
k
l
l
k
l
l
k
l
lll
k
l
l
k
l
xg
n
u
xg
n
u
xu
xfu
 3,...,n (8) 
,\,
,,
,,
212
)(
12
2
)(
2
12
)(
12
12
)(
12
nn
k
n
n
k
n
n
k
n
n
k
n
xu
xg
n
u
xfu
 (9) 
Bước 3: Tiến hành giải song song các bài toán trong các miền chẵn 
.\,
,,
,,
,,
,,
1222,42
)(
2
12
)(
12
)(
2
2,4
2
)(
2
12
)(
12
)(
2
2
)(
2
llll
k
l
l
k
l
k
l
l
l
k
l
l
k
l
k
l
l
k
l
xu
xuu
x
n
u
xuu
xfu
1,2,...,n (10) 
Bước 4: Hiệu chỉnh 
.,)1(
,,)1(
2
2
)(
2)(
2
)1(
2
12
2
)(
2)(
12
)1(
12
l
l
k
lk
l
k
l
l
l
k
lk
l
k
l
x
n
u
gg
x
n
u
gg
 1,2,...,n (11) 
Nhận xét: Trong mô hình tính toán (7 - 10), chúng ta có thể thấy: theo sơ đồ tính toán 
đã đưa ra, việc giải các bài toán (7 - 9) được thực hiện bởi mô hình tính toán song song. Khi 
thu được kết quả của các bài toán (7 - 9), việc giải các bài toán (10) cũng sẽ được thực hiện 
 Tạp chí Khoa học & Công nghệ - số 2(50)/năm 2009 Toán, Thống kê –KH tự nhiên –KH máy tính 
4 
bằng sơ đồ tính toán song song. Sự hội tụ của phương pháp lặp phụ thuộc vào sự hội tụ của 
sơ đồ (11). 
2.2. Hướng tiếp cận hiệu chỉnh hàm 
Kí hiệu 
ii i
g u i 1,2,...,2n . Việc giải bài toán (6) được thực hiện bởi sơ đồ lặp sau: 
Bước 1: Xuất phát 
( 0 )
ig 0,i 1,2,...,2n 
Bước 2: Tiến hành giải song song các bài toán trên các miền chẵn 
.\,
,,
,,
,,
,,
1222,42
)(
2
12
)(
12
)(
2
2,4
2
)(
2
12
)(
12
)(
2
2
)(
2
llll
k
l
l
k
l
k
l
l
l
k
l
l
k
l
k
l
l
k
l
xu
xgu
x
n
u
xgu
xfu
nl ,...,2,1 (12) 
Bước 3: Tiến hành giải song song các bài toán trên các miền lẻ 
,\,
,,
,,
11
)(
1
1
2
)(
2
1
)(
1
1
)(
1
xu
x
n
u
n
u
xfu
k
kk
k
 (13) 
,,
,,
,\,
,,
12
2
)(
2
12
)(
12
22
22
)(
22
12
)(
12
21212
)(
12
12
)(
12
l
l
k
l
l
k
l
l
l
k
l
l
k
l
lll
k
l
l
k
l
x
n
u
n
u
x
n
u
n
u
xu
xfu
(14) 
,\,
,,
,,
212
)(
12
2
2
)(
2
12
)(
12
12
)(
12
nn
k
n
n
n
k
n
n
k
n
n
k
n
xu
x
n
u
n
u
xfu
 (15) 
Bước 4: Hiệu chỉnh 
( k 1 ) ( k ) ( k )
2 1 2 1 2 1 2 1
( k 1 ) ( k ) ( k )
2 2 2 1 2
g (1 )g u ,x ,
g (1 )g u ,x
   
   
 1,2,...,n (16) 
Nhận xét: Sự hội tụ của sơ đồ hoàn toàn phụ thuộc vào sự hội tụ của các sơ đồ lặp (16), xuất 
phát từ các kết quả lí thuyết trong [1,2] cũng có thể chứng minh sự hội tụ của sơ đồ lặp (16). 
 Tạp chí Khoa học & Công nghệ - số 2(50)/năm 2009 Toán, Thống kê –KH tự nhiên –KH máy tính 
5 
Như vậy, hai mô hình tính toán song song (7)-(11) và (12)-(16) cùng giải quyết bài toán 
(6). Đây là các sơ đồ tính toán song song hoàn toàn mới chưa được công bố, sự khẳng định tính 
đúng đắn và so sánh tốc độ của hai mô hình có thể thông qua các kết quả thực nghiệm. 
3. Các kết quả thực nghiệm 
Bảng 1. 1x
1 2 2 2 1u( x ,x ) e log( x 5 ) sin( x )log( x 6 ) 
Tham số Hiệu chỉnh đạo hàm Hiệu chỉnh hàm 
n n 
0.3 16 7.10-5 27 8.10-5 
0.4 11 7.10-5 19 8.10-5 
0.5 8 6.10-5 15 5.10-5 
0.6 8 8.10-5 11 8.10-5 
0.7 14 8.10-5 13 9.10-5 
Bảng 2. 1 2x x3 3
1 2 1 2 2 1u( x ,x ) x x e x x e 
Tham số 
Hiệu chỉnh đạo hàm Hiệu chỉnh hàm 
n N 
0.3 16 9.10-5 26 2.10-4 
0.4 11 9.10-5 19 8.10-5 
0.5 8 8.10-5 15 5.10-5 
0.6 9 4.10-5 11 9.10-5 
0.7 15 7.10-5 15 7.10-5 
Bảng 3. 1 2 1 2u( x ,x ) sin x sin x 
Tham số 
Hiệu chỉnh đạo hàm Hiệu chỉnh hàm 
N N 
0.3 16 1.10-3 27 1.10-3 
0.4 11 1.10-3 19 1.10-3 
0.5 8 1.10-3 15 1.10-3 
0.6 9 1.10-3 11 1.10-3 
0.7 15 1.10-3 15 1.10-3 
Để kiểm tra tính đúng đắn của các mô hình tính toán song song, chúng tôi sử dụng 
phương pháp lưới chuyển các bài toán vi phân về các bài toán sai phân tương ứng và tiến hành 
tìm nghiệm của các bài toán sai phân bằng thuật toán thu gọn khối lượng tính toán trên cơ sở sử 
dụng các hàm trong TK2004 [7]. Trong các kết quả, chúng tôi luôn lấy lưới chia M×N = 64×64 
đối với các miền con, kí hiệu u*(x1, x2) là nghiệm đúng của phương trình, sai số *
ij ij
(i,j)
max u u
. Các kết quả thực nghiệm được tính toán đồng thời với cả hai mô hình, ngôn ngữ sử dụng 
Matlab trên máy tính PC, số miền chia luôn lấy là 21 miền. 
4. Nhận xét và kết luận 
Bài báo đã đề xuất hai mô hình tính toán song song giải bài toán biên hỗn hợp mạnh 
trên hai hướng tiếp cận hiệu chỉnh giá trị đạo hàm và hàm trên các biên chung. Đây là hai 
hướng tiếp cận trên hai quan điểm ngược nhau, việc chứng minh tính đúng đắn của các mô 
hình tính toán song song đã đề xuất bằng lí thuyết là chưa thực hiện được, nhưng qua các kết 
quả thực nghiệm tính toán có thể khẳng định: các mô hình tính toán là hội tụ với tham số 
0 1 trong đó tham số tối ưu opt 0,5 . Qua thực nghiệm có thể thấy tốc độ hội tụ của mô 
hình tính toán trên tư tưởng hiệu chỉnh đạo hàm có tốc độ hội tụ nhanh hơn. Trên cơ sở của mô 
hình này, có thể mở rộng đề xuất mô hình tính toán song song giải bài toán song điều hòa với 
điều kiện biên hỗn hợp mạnh  
Tóm tắt 
Trong bài báo này, chúng tôi trình bày các kết quả nghiên cứu khi xây dựng các mô 
hình tính toán song song trên cơ sở tiếp cận phương pháp chia miền trên hai hướng: hiệu chỉnh 
 Tạp chí Khoa học & Công nghệ - số 2(50)/năm 2009 Toán, Thống kê –KH tự nhiên –KH máy tính 
6 
hàm và hiệu chỉnh đạo hàm trên biên phân chia, từ đó đưa ra các kết quả thực nghiệm đối với 
mô hình tính toán tổng quát, đồng thời so sánh hiệu quả của hai mô hình tính toán song song 
đã đề xuất. 
Summary 
In this paper, the research results as constructing parallel calculating model basing on 
domain decomposition method approach in two directions are presented: function and 
derivative adjustment at decomposition boundary, thence by draw out experimental result to 
general calculating model, we can compare effect of given two parallel calculating models, 
concurrently. 
Tài liệu tham khảo 
[1]. Đặng Quang Á, Vũ Vinh Quang (2006), “Phương pháp chia miền giải bài toán biên hỗn hợp 
mạnh”, Tạp chí Tin học và Điều khiển học, T.22, S.4: 307-318. 
[2]. Dang Quang A and Vu Vinh Quang, A domain decomposition method for solving an elliptic 
boundary value problem, Methods of Complex and Clifford Analysis (Proceedings of ICAM Hanoi 
2004), SAS International Publications, 309-319. 
[3]. Đặng Quang Á, Vũ Vinh Quang (2005), “Nghiên cứu thực nghiệm một phương pháp chia 
miền đối với bài toán biên với điều kiện biên hỗn hợp”, Tạp chí Tin học và Điều khiển học, T.21, S.3: 
216-229. 
[4]. Vũ Vinh Quang (2006), “Một số kết quả áp dụng phương pháp chia miền giải bài toán biên 
elliptic với điều kiện biên hỗn hợp mạnh”, Tạp chí Khoa học và Công nghệ ĐH Thái Nguyên, T.4(40): 
37-45. 
[5]. Vũ Vinh Quang (2005), Các kết quả về việc ứng dụng thuật toán thu gọn khối lượng giải 
các bài toán biên elliptic với các điều kiện biên hỗn hợp, Hội thảo khoa học toàn quốc, “Phát triển 
công cụ tin học trợ giúp cho giảng dạy, nghiên cứu và ứng dụng toán học”, Hà Nội 1-2/04/2005: 247-
256. 
[6]. Vũ Vinh Quang, Nguyễn Thanh Hường, Một số kết quả so sánh hai phương pháp chia miền, 
Tạp chí Khoa học và Công nghệ Đại học Thái Nguyên (Đã nhận đăng). 
[7]. N. Saito, H. Fujita (2001), Operator Theoretical Analysis to Domain Decomposition 
Methods, 12th Int. Conf. on Domain Decomposition Methods, Editors: Tony Chan, Takashi, Hideo, 
Oliver Pinoneau, 63-70, www.ddm.org/DDI2/saito.pdf. 
[8]. N. Saito and H. Fujita (2000), ”Remarks on Traces of H1-functions Defined in a Domain with 
Corners,” J. Math. Sci. Univ. Tokyo 7: 325-345.