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:
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.
6 trang |
Chia sẻ: dntpro1256 | Lượt xem: 750 | Lượt tải: 0
Bạn đang xem nội dung tài liệu 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ải tài liệu về máy bạn click vào nút DOWNLOAD ở trê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.
Các file đính kèm theo tài liệu này:
- brief_1024_9505_9_923_2053124.pdf