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

Chia sẻ: Thi Thi | Ngày: | Loại File: PDF | Số trang:6

Thêm vào BST

Báo xấu

49
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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. Trong bài báo này, đề xuất các mô hình tính toán song song để giải các bài toán trên.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 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 (DQuangAVVQuang [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 u f, x , u , x n, (1) n u , x \ n. 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 (Hình 1), kí hiệu u1 là nghiệm trong miền 1 2 bởi biên phân chia , u2 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) 1 Kí hiệu g u2 , khi đó giá trị g được xác định bởi sơ đồ lặp sau đây: Bước 1: Cho trước g ( 0 ) xác định trên L2 Bước 2: Với g ( k ) xác định trên (k ) 2 (k ) 2 (k ) 2 (k ) 2 u u u u n2 f, , x (k ) g , x , x 2 n 1) (1 ) g (k ) u1( k ) , x d . Bước 3: Hiệu chỉnh giá trị g ( k g (k (k = 0, 1, 2,…) tiến hành giải hai bài toán , 2 \ x , , chẳng hạn g ( 0 ) = 0. 1) . , u1( k ) (k ) 1 u n1 u1( k ) f, x (k ) u2 , x n2 , x 1 , , 1 (2) \ , theo công thức (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) 1 Tạp chí Khoa học & Công nghệ - số 2(50)/năm 2009 u1 n1 Kí hiệu g Toán, Thống kê –KH tự nhiên –KH máy tính , khi đó giá trị g được xác định bởi sơ đồ lặp sau đây: Bước 1: Cho trước g ( 0 ) xác định trên L2 Bước 2: Với g ( k ) xác định trên u1( k ) u1( k ) n1 u1( k ) f, x g (k ) , x , (k ) 2 (k ) 2 (k ) 2 u u u n2 , x 1 \ , Bước 3: Hiệu chỉnh giá trị g ( k g (k 1) (1 (k = 0, 1, 2,…) tiến hành giải hai bài toán u2( k ) 1, 1) f, , (k ) u1 , x x , 2 2 , \ n x , x n , (4) . theo công thức u2( k ) ,x n2 ) g (k ) , chẳng hạn g ( 0 ) = 0. (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: u u n u f, x , x ,  4, 2i \ x 41 42 43 1 2 3 , (6) , (i 1..n), 4, 2i , , (i 1..n). 4, 2l 1 4, 2l 4, 2l 1 2l 1 2l 2l 1 …. 1 2 3 4, 2 n 1 …. 2l 1 2l 2l 1 2n 1 2n Hình 2 1 Trong đó f L , n là vectơ pháp tuyến ngoài của miền . Trên thế ; H 2 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 2 2 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 2n 1  Chia bởi các biên phân chia i i ( i 1..2n ) , (Hình 2). i 1 Kí hiệu g 2i u2 i n2i 1 2i 1 u2 i n2i , g 2i bởi sơ đồ lặp sau đây: Bước 1: Xuất phát gi( 0 ) 2i , (i 1,2,...n) . Việc giải bài toán (6) được thực hiện 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ẻ u1( k ) f, x 1 (k ) 1 u g1( k ) , x n1 u1( k ) , x u2( kl ) 1 (k ) 2l 1 (k ) 2l 1 u u n2l 1 u2( kl ) 1 n2l 1 f, , 1 1 , , (7) \ 1, x x 2l 1 2l 1 \ , 2l 1 g 2( kl ) 2 , x 2l 2 , g 2( kl ) 1 , x 2l 1 , u2( kn) 1 f, x (k ) 2n 1 u g 2( kn) , n2 n 1 u2( kn) 1 , x 2n 1 x 2n 2n 1 2l ,  3,...,n (8) , , \ (9) 2n , Bước 3: Tiến hành giải song song các bài toán trong các miền chẵn u2( kl ) x 2l , x 2l 1 , x 4, 2l u2( kl ) u2( kl ) 1 , u2( kl ) , x 2l 1 u (k ) 2l (k ) 2l f, u (k ) 2l 1 u n2l x 2l \ 4, 2l , , ,  1,2,...,n (10)  1,2,...,n (11) , 2l 2l 1 . Bước 4: Hiệu chỉnh g 2( kl g 1) 1 ( k 1) 2l (1 (1 ) g 2( kl ) 1 )g (k ) 2l u2( kl ) ,x n2l u2( kl ) ,x n2l 2l 1 2l , . 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 3 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 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 gi ui i 1,2,...,2n . Việc giải bài toán (6) được thực hiện bởi sơ đồ lặp sau: i (0 ) Bước 1: Xuất phát gi 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 u2( kl ) f, x 2l u2( kl ) g 2( kl ) 1 , u2( kl ) , n2l u2( kl ) g 2( kl ) 1 , u2( kl ) , x 2l 1 x 4, 2l x 2l 1 x 2l \ 4, 2l , , , l 1,2,..., n (12) , 2l 2l 1 . Bước 3: Tiến hành giải song song các bài toán trên các miền lẻ u1( k ) f, x (k ) u2 , x n2 , x (k ) 1 u n1 u1( k ) u2( kl ) 1 u (k ) 2l 1 (k ) 2l 1 u n2l 1 u2( kl ) 1 n2l 1 u2( kn) 1 (k ) 2n 1 u n2 n 1 u2( kn) 1 1 1 1 f, , x (k ) u2 l 2 , n2l 2 u2( kl ) , n2l , , (13) \ 1, x 2l 1 2l 1 f, x (k ) u2 n , x n2 n , x \ , 2l 1 x 2l 2 , x 2l 1 , 2n 1 2n 2n 1 2l , (14) , , \ (15) 2n , Bước 4: Hiệu chỉnh g 2( k 1) 1 (1 )g 2( k )1 u2( k )1 ,x g 2( k 1) (1 )g 2( k ) u2( k )1 ,x 2 1 ,  1,2,...,n (16) 2 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). 4 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 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. u( x1 ,x2 ) Tham số Hiệu chỉnh đạo hàm n 16 7.10-5 11 7.10-5 8 6.10-5 8 8.10-5 14 8.10-5 0.3 0.4 0.5 0.6 0.7 Bảng 2. u( x1 ,x2 ) Tham số 0.3 0.4 0.5 0.6 0.7 e x1 log( x2 5 ) sin( x2 )log( x1 6 ) x13 x2e x1 Hiệu chỉnh đạo hàm n 16 9.10-5 11 9.10-5 8 8.10-5 9 4.10-5 15 7.10-5 x23 x1e Hiệu chỉnh hàm n 27 19 15 11 13 Bảng 3. u( x1 ,x2 ) x2 Hiệu chỉnh hàm N 26 2.10-4 19 8.10-5 15 5.10-5 11 9.10-5 15 7.10-5 Tham số 0.3 0.4 0.5 0.6 0.7 8.10-5 8.10-5 5.10-5 8.10-5 9.10-5 sin x1 sin x2 Hiệu chỉnh đạo hàm N 16 1.10-3 11 1.10-3 8 1.10-3 9 1.10-3 15 1.10-3 Hiệu chỉnh hàm N 27 1.10-3 19 1.10-3 15 1.10-3 11 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ố max uij uij* (i,j) . 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 5