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.