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

ng. 1 = , = 0,1,2,...k k k y y B Ay f k    (1.27 ’ ) Trong trường hợp này, phương trình (1.32) liên hệ với sai số xấp xỉ = k k z y u có dạng 1 0 0 = 0, = , = 0,1,2,...k k k z z B Az z y u k    (1.32 ’ ) Toán tử B nói chung là không đối xứng, có toán tử ngược 1B . Định lý: Nếu A là toán tử đối xứng, xác định dương thì 1 1 > ( , ) > ( , ), 2 2 B A hay Bx x Ax x x H    (1.34) là điều kiện đủ cho sự hội tụ của lược đồ lặp (1.27 ’) trong không gian A H với tốc độ hội tụ cấp số nhân 1 , = 0,1,2,..., <1, k kA A z z k    (1.35) trong đó 1 2 * 2 * 0 2 1 = 1 , = ( ), = ( ),min min 2 k k k k A B A B             trong đó * 0 = 2 B B B  là phần đối xứng của toán tử B . Chứng minh Từ (1.32 ’) ta có: 1 = k k z Sz  với 1=S E B A  . Do đó Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 25 2 1 1 1 1 1 2 1 1 2 1 1 = ( , ) = = ( , ) = = ( ( ) ,( ) ) = = [( , ) ( , )] ( , ). k k kA k k k k k k k k kA k k z Az z ASz Sz A E B A z E B A z z AB Az z B Az Az AB Az B Az                    Thế = k k Az Bv với 1= k k v B Az , kết hợp với điều kiện A là toán tử đối xứng ta được 2 2 1 1 = 2 (( ) , ). 2 k k k kA A z z B A v v     (1.36) Do giả thiết (1.34) của định lý ta suy ra toán tử 1 = 2 P B A là toán tử dương. Chúng ta thiết lập tính xác định dương của nó trong H * * 1 , > 0, 2 B A E    (1.34 ’ ) trong đó *  là giá trị riêng nhỏ nhất của toán tử 0 0 1 = 2 P B A . Do đó 2 * 1 2 (( ) , ) 2 . 2 k k k B A v v v    (1.36 ’ ) Mặt khác 2 1 21 21 2 2 2 = ( , ) = = ( , ) . . . . k k kA k k k k k z Az z Bv A Bv A Bv A B v B v           suy ra Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 26 2 2 2 .k k Av z B   (1.37) Kết hợp (1.36 ’), (1.36), (1.37) ta được 2 2 22 1 = k k kA A A z Sz z   với 2 * 2 2 =1 <1 B     . Từ đó ta suy ra (1.33). Còn bất đẳng thức 0 n n A A z z khẳng định sự hội tụ của phép lặp do 0,n n   . Với = k B B cố định, định lý đã đưa ra qui tắc lựa chọn giá trị  để lược đồ lặp hội tụ. Trong trường hợp =B E , điều kiện hội tụ sẽ được đảm bảo nếu tất cả các giá trị riêng thỏa mãn 1 1 ( ) =1 ( ) > 0 2 2 k k E A A    hay 1 1 > 0. 2 A Như vậy, lược đồ lặp hội tụ với mỗi 2 < A  . Kết luận: Trong chương 1, luận văn đã trình bày một số kiến thức liên quan đến việc giải số phương trình đạo hàm riêng bao gồm một số kiến thức cơ bản của phương pháp sai phân, thuật toán thu gọn khối lượng tính toán giải phương trình vec tơ 3 điểm đối với bài toán biên thứ nhất và bài toán biên thứ hai, áp dụng đối với bài toán biên Dirichlet và bài toán biên hỗn hợp, cơ sở lý thuyết về phương pháp lặp giải phương trình toán tử. Những kiến thức quan trọng này làm nền tảng cho các kết quả sẽ trình bày trong các chương tiếp theo của luận văn. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 27 Chương 2 CƠ SỞ TOÁN HỌC CỦA PHƢƠNG PHÁP CHIA MIỀN Trong chương này, chúng ta đưa ra cơ sở toán học của phương pháp chia miền bao gồm giới thiệu các khái niệm về các điều kiện chuyển giao giữa các biên chung, các công thức biến phân và đặc biệt là ứng dụng của toán tử Steklov-Poincare đối với phương pháp chia miền. các phương pháp lặp đơn trên các biên chung. Các kiến thức được trình bày trên cơ sở các tài liệu [11,12, 14, 22, 25, 26, 29, 30, 31] Hình 1 Xét bài toán , , 0, , u f x u x       (2.1) trong đó  là miền d chiều )3,2( d , với biên Lipschitz  , kí hiệu n là véc tơ pháp tuyến ngoài của miền  , f là hàm đã cho thuộc không gian 2 ( )L  , 1 d j j j D D    là toán tử Laplace và jD . Kí hiệu là đạo hàm riêng theo )..1( djx j  . Giả sử rằng miền  được chia thành hai miền con không giao nhau 1 và 2 , kí hiệu 21  (Hình 1). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 28 2.1 Công thức đa miền và phƣơng trình Steklov-Poicare Kí hiệu i u là giá trị nghiệm u trong miền )2,1(,  ii và in là hướng pháp tuyến ngoài trên i   . Ta đặt 1nn  . Khi đó bài toán (2.1) có thể viết lại dưới dạng đa miền như sau: 1 1 1 1 1 2 2 1 2 2 2 2 , , 0, , , , , , 0, , , . u f x u x u u x u u x n n u x u f x                          (2.2) Các phương trình 3 và 4 trong (2.2) là các điều kiện chuyển tiếp trên biên về mặt ý nghĩa vật lý muốn mô tả điều kiện liên tục của hàm và đạo hàm khi biến thiên qua biên chung  giữa hai miền. Kí hiệu  là giá trị chưa biết của u trên  , ta xét hai bài toán biên Dirichlet , , 0, , , . i i i i i w f x w x w x           (2.3) Với 2,1i , chúng ta có thể biểu diễn *0 iii uuw  trong đó 0 iu và * iu là nghiệm của các bài toán Dirichlet sau: 0 0 0 0, , 0, , , . i i i i i u x u x u x           (2.4) * * * , , 0, , 0, . i i i i i u f x u x u x           (2.5) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 29 Với mỗi 2,1i 0 iu là mở rộng điều hoà của  vào i và được kí hiệu là iH , ta sẽ viết i G f thay cho * iu . Bằng việc so sánh (2.2) và (2.3) ta thấy rằng )2,1(  iuw ii khi và chỉ khi .,21       x n w n w (2.6) Giá trị  trên biên chung phải thoả mãn phương trình Steklov- Poincare , ,S x   trong đó (2.7) 2 2 1 1 i i G f G f G f n n n              , (2.8) trong đó S là toán tử Steklov-Poincare được định nghĩa bởi            2 1 21 i i i n H n H n H S  . Cùng với toán tử S , ta cũng sử dụng các toán tử 1 iS và gọi là các toán tử Poincare-Steklov. Mô hình chia miền trên có thể áp dụng đối với bài toán tổng quát  xfLu , , (2.9) trong đó L là toán tử vi phân, f là hàm đã cho và u là nghiệm chưa biết. Do  được chia thành hai miền con nên phương trình (2.9) tương đương với hai phương trình      22 11 , ,, xfLu xfLu (2.10) trong đó )2,1(, iui cần thoả mãn các điều kiện chuyển dịch qua  được biểu hiện bởi hai quan hệ tổng quát Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 30      ,),()( ,),()( 21 21 xuu xuu trong đó các hàm , phụ thuộc vào từng loại bài toán, Với bài toán Poisson thì n v vvv    )(,)( . 2.2 Các phƣơng pháp lặp đơn cơ sở Trong phần này, chúng ta xét việc giải bài toán đa miền bằng các thủ tục lặp, chúng ta xét 1 dãy các bài toán con trong 21,  với các điều kiện biên Dirichlet hoặc Neumann tương ứng. Các phương pháp đó có thể thực hiện được bởi 1 trong các sơ đồ lặp sau đây, trong đó các dãy hàm    kk uu 21 , sẽ được xác định từ các giá trị ban đầu 0 2 0 1 , uu và sẽ hội tụ đến 21, uu tương ứng. 2.2.1 Phương pháp Dirichlet-Neumann Phương pháp này đã được xét đến bởi các tác giả Bjorstad và Windlund (1986), Bramble (1986), Funaro (1988), Marini và Quanrteroni (1988,1989). Cho trước 0 , với mỗi 0k  , giải hai bài toán 1 1 1 1 1 1 1 1 , , 0, , , , k k k k u f x u x u x              (2.11) 1 2 2 1 1 2 1 1 2 2 , , , , 0, , k k k k u f x u u x n n u x                  (2.12) Tính lại giá trị 1k  theo công thức Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 31 .)1(12 1 kkk u     (2.13) Trong đó  là tham số cần lựa chọn để dãy lặp hội tụ. 2.2.2 Phương pháp Neumann-Neumann Phương pháp này được nghiên cứu bởi các tác giả Bourgat (1989), Agoshkov và Lebedev (1985). Trong trường hợp này, xuất phát từ 0 , với mỗi 0k ta giải các bài toán 1 1 , , 0, , , , k i i k i i k k i u f x u x u x             (2.14) 1 1 1 1 2 1 , , , , 0, , k i i k k k i k i i f x u u x n n n x                        (2.15) Hiệu chỉnh )( 1221111   kkkk  , (2.16) trong đó  là tham số lặp, 21, là hai hệ số ước lượng trung bình dương. Việc chứng minh sự hội tụ của thuật toán này đã được đưa ra trong các tài liệu cùng với sự rời rạc các phần tử. Trong trường hợp này, tốc độ hội tụ được chỉ ra là không phụ thuộc vào mức lưới h . 2.2.3 Phương pháp Robin Phương pháp này được nghiên cứu bởi tác giả Lion(1990), Agoshkov(1988). Trong trường hợp này, xuất phát từ 0 2 u , với mỗi 0k ta giải các bài toán Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 32 1 1 1 1 11 2 1 1 1 2 1 1 1 , , , , 0, , k k k k k k u f x u u u u x n n u x                      (2.17) 1 2 2 1 1 1 12 1 2 2 2 1 1 2 2 , , , , 0, , k k k k k k u f x u u u u x n n u x                        (2.18) trong đó 1 2 ,  là các tham số gia tốc không âm thoả mãn 1 2 0   . Ta có thể xây dựng phương pháp tương tự bằng cách đổi vai trò 2 ku với 1 ku Một phương pháp khác được đề xuất bởi Agoshkov-Lebedev (1985). Xuất phát từ 0 2 0 1 , uu , với mọi 0k giải các bài toán:                    ,, ,,0 ,, 2 22/1 1 2/1 1 1 2/1 1 1 2/1 1 xup n u up n u xu xfu k k k k k k k k ,),( 11 2/1 111 1 1     xuuuu kkk kk                        ,, ,,0 ,, 1 1 1 12/1 2 1 2 2 2/1 2 2 2/1 2 xu n u qu n u q xu xfu k k k k k k k k ,),( 22 2/1 212 1 2     xuuuu kkk kk  trong đó kkkk qp  ,,0,0  là các tham số tự do. Trong thực tế, phương pháp này tổng quát cho nhiều phương pháp, ví dụ phương pháp Dirichlet-Neumann là trường hợp đặc biệt của phương pháp này với 1,0 1  kkk qp  và phương pháp Robin sẽ nhận được với )0(,/1,,1 21  kkkkk qqp  . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 33 2.3 Một số thuật toán chia miền Trên cơ sở của lý thuyết chia miền tổng quát, trên thế giới đã xuất hiện một số thuật toán chia miền của các tác giả áp dụng đối với các trường hợp cụ thể. 2.3.1 Thuật toán chia miền Patrick Le Talle. Thuật toán đưa ra nhằm sử dụng phương pháp chia miền để giải các bài toán biên Dirichlet và Neumann, đây là cơ sở cho việc tính toán đa nhiệm trên máy tính CRAY2 và INTER, đã được kiểm nghiệm trên các bài toán đàn hồi trong không gian 3 chiều, bài toán miền ảo, bài toán trong các ngành công nghiệp trên quy mô lớn. Xét mô hình đơn giản      .,0 ,, xu xfu (2.19) Chia 21  bởi biên chung S . Kí hiệu  là giá trị hàm u trên S , khi đó ta có thể tiến hành giải song song hai bài toán trong hai miền 2,1,  ii . ,, ,,0 ,, Sxu xu xfu i ii ii          (2.20) Trong đó  phải thoả mãn điều kiện tổng đạo hàm pháp tuyến trên biên chung phải triệt tiêu tức là .,0 2 2 1 1 Sx n u n u       (2.21) Như vậy phương trình (2.21) chính là phương trình xác định  . Để giải bài toán này, đưa ra hàm ),( fui  được xác định như sau Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 34         .,),( ,,0),( ,,),( Sxfu xfu xffu i ii ii    (2.22) Đưa vào toán tử Steklov-Poincare iS được xác định bởi i i i n u S    )0,(  và vế phải 2 2 1 1 )0,()0,( n u n u b        . Theo công thức này, điều kiện (2.21) trở thành bSS  )( 21 . Từ đó có thể giải bài toán theo thuật toán dốc liên kết gradien trên nghiệm theo sơ đồ lặp sau đây ))(( 21 1 bSSM kkk   , (2.23) trong đó M là toán tử trên nghiệm và  là hệ số co giãn. Điểm mấu chốt là phải tìm một toán tử trên nghiệm đơn giản và hiệu quả, theo các tài liệu đã biết thì cách chọn đơn giản và hiệu quả nhất là cách chọn .4/)( 12 1 1   SSM (2.24) Cách chọn này đạt độ chính xác nhất trong trường hợp 21 SS  và khi đó  được xác định bởi sơ đồ lặp kkk SSSS  ))(( 4 21 1 2 1 1 1   . (2.25) Để tìm lời giải của bài toán, xuất phát từ )(2 1 00 SH thực hiện giải song song hai bài toán Dirichlet         ,, ,,0 ,, Sxu xu xfu i ii ii  (2.26) Tiếp theo giải song song hai bài toán Neumann Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 35                   .),( 2 1 ,,0 ,,0 2 2 1 1 Sx n u n u n x x i i ii ii (2.27) Cập nhật lại 2/)( 21   , quá trình lặp lại cho đến khi hội tụ. Như vậy trong thuật toán chia miền trên, vấn đề quan trọng nhất là việc chọn giá trị tham số  . Thuật toán chia miền Patrick Le Talle ở trên mới được trình bày dưới mức vi phân, trong các tài liệu đã biết đã trình bày phương pháp rời rạc hoá thuật toán vi phân và trên cơ sở sử dụng sơ đồ lặp Seidel co giãn đưa ra các kết quả thực nghiệm trên máy tính điện tử với một số bài toán cụ thể. Kết quả chứng tỏ thuật toán là đúng đắn và độ chính xác phụ thuộc vào việc sai phân các đạo hàm để nhằm xác định giá trị  trên mỗi bước lặp. Xuất phát từ thuật toán cơ sở, chúng ta có thể thấy do sơ đồ lặp với mục tiêu là xác định gần đúng giá trị hàm  trên biên chung đối với cả hai bài toán trong hai miền 21 ,  nên đối với bài toán biên hỗn hợp trong miền hình học phức tạp thì chúng ta phải thực hiện phép chia thành nhiều miền con mới tránh được bài toán biên hỗn hợp mạnh. Điều này sẽ tăng khối lượng tính toán trong các sơ đồ lặp. 2.3.2 Thuật toán chia miền J.R.Rice, E.A. Vavalis, Daopi Yang. Xét  là một đa thức lồi dR ,...2,1d Với biên  , xét bài toán: Cho )();( 2/12  HgLf , hãy tìm )(1  Hu ,, ,,      xgu xfLu (2.28) trong đó Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 36 uxa x u xa x Lu j ij d ji i )())(( 0 1,         . (2.29) Chia miền  thành 2 miền con 1 và 2 như sau  2121 , ,   21 , . Ký hiệu 21  là biên chung của hai miền. Khi đó bài toán (2.28), (2.29) là tương đương với hai bài toán sau                  ,,0 ,, ,, ,, 2 2 1 1 21 11 11 x v u v u xuu xgu xfLu (2.30)                  ., ,, ,, ,, 1 1 2 2 12 22 22 x uu xuu xgu xfLu  (2.31) Trong đó 21, uu lần lượt là nghiệm trong 21, và 21, là các véc tơ pháp tuyến ngoài của  ứng với 21,  . Định nghĩa thuật toán chia miền như sau Chọn )(1)0( nn Hu  với .2,1,)0(   ngu n n  Xây dựng dãy lặp )(1)1(  Hu kn với gu n k n   )1( , ,...2,1k thoả mãn                                      .,)1(,, ,,)1(,, ,,)1(,, ,,)1(,, 1 )12( 1 2 )12( 2 2 )22( 2 2 )12( 2 2 )12( 2 1 )12( 1 1 )22( 1 1 )22( 1 )2( 1 )2( 2 )12( 22 )12( 2 )2( 2 )2( 1 )12( 11 )12( 1 x uuu xfLu x uuu xfLu xuuuxfLu xuuuxfLu kkk k kkk k kkkk kkkk             (2.32) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 37 Với )1,0(,  là các tham số giảm dư được chọn để đẩy nhanh tốc độ hội tụ của sơ đồ lặp, việc chọn các tham số này phụ thuộc vào cách chia miền và bài toán gốc. Về mặt lý thuyết thì khó xác định các giá trị tối ưu. Tuy nhiên qua phân tích lý thuyết và thực nghiệm đã chỉ ra rằng trong nhiều trường hợp nên chọn 2 1   . Khi phép lặp hội tụ, giới hạn của dãy  )(knu sẽ là nghiệm của bài toán ban đầu. Xuất phát từ sơ đồ lặp, chúng ta có thể thấy rằng do các bài toán ứng với chỉ số lẻ là nhằm hiệu chỉnh giá trị hàm, các bài toán ứng với chỉ số chẵn là hiệu chỉnh giá trị đạo hàm nên trong trường hợp bài toán biên hỗn hợp trên miền hình học phức tạp thì để tránh gặp phải các bài toán biên hỗn hợp mạnh thì phải sử dụng phép chia thành nhiều miền con. Điều này cũng tăng khối lượng tính toán trong các bước lặp. 2.3.3 Thuật toán chia miền Saito-Fujita Với tư tưởng hiệu chỉnh giá trị hàm trên biên phân chia, năm 2001, hai nhà toán học Nhật Bản là Noroshi Fujita dựa trên cơ sở sơ đồ lặp Dirichlet- Neumann đã đề xuất một phương pháp chia miền giải bài toán biên Elliptic với điều kiện biên Dirichlet. Các kết quả được tham khảo trong các tài liệu [22, 23]. Cho là miền trong R2 với biên Lipschitz . Xét bài toán: , , , u f x u x       (2.33) trong đó  2 1/2( ),f L H    . Chia miền 1 2   bởi biên chung . Kí hiệu    ( ) ( )1 2, k ku u là các dãy hàm hội tụ đến u1, u2 một cách tương ứng. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 38 Tư tưởng của phương pháp Saito-Fujita là tìm ra xấp xỉ g u   nhận được bởi sơ đồ lặp sau: 1. Cho trước (0)g xác định trên  . 2. Với ( )kg xác định trên  0k  , tiến hành giải hai bài toán (k) 1 1 (k) 1 1, (k) (k) 1 - u = f,x , u = ,x u = g ,x        (2.34) ( ) 2 2 ( ) 2 2 ( ) ( ) 2 1 2 1 , , , , k k k k u f x u x u u x n n                  (2.35) 3. Giá trị của ( )kg được tính theo công thức ( 1) ( ) ( ) 2 (1 ) , ,k k kg g u x      (2.36) trong đó  là tham số cần lựa chọn để dãy lặp hội tụ, 0<  <1. Ta thấy rằng, điều kiện liên tục của đạo hàm qua biên phân chia  đã thoả mãn, còn điều kiện liên tục của hàm qua biên phân chia  phụ thuộc vào sự hội tụ của dãy lặp (2.36). Như vậy, trong phương pháp Saito-Fujita trình bày ở trên, mỗi lần lặp cần giải quyết một bài toán Dirichlet (2.34) trong 1  , sau đó giải một bài toán Neumanm (2.35) trong 2  . Do đó phương pháp trên được phát triển trên tư tưởng của sơ đồ Dirichlet-Neumann. 2.3.4 Phương pháp DQuangA-VVQuang Xuất phát từ tư tưởng hiệu chỉnh giá trị đạo hàm trên biên phân chia, năm 2004, hai nhà toán học Việt Nam là Đặng Quang á và Vũ Vinh Quang đã Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 39 đề xuất một phương pháp chia miền mới. Các kết quả được tham khảo trong các tài liệu [1, 3, 4, 12]. Cho  là miền trong 2 với biên Lipschitz  . Xét bài toán , , , , u f x u x       Trong đó    2 1/2,f L H    . Sử dụng phương pháp chia miền cùng các kí hiệu tương tự. Kí hiệu      1 2, k k u u là các dãy hàm hội tụ đến 1 2 ,u u một cách tương ứng. Tư tưởng của phương pháp DquangA-VVQuang là tìm ra xấp xỉ 1 1 u g n     nhận được bởi sơ đồ lặp sau: 1. Cho  0 2g L  . 2. Với  kg xác định trên  0k  tiến hành giải hai bài toán         1 1 1 1 1 1 , , , , , , k k k k u x u g x n u f x           (2.37)         2 2 2 2 2 1 , , , , , . k k k k u f x u x u u x           (2.38) 3. Giá trị của  kg được tính theo công thức         1 2 2 1 , k k k u g g x n        , (2.39) trong đó  là tham số lặp cần lựa chọn để dãy lặp hội tụ 0 1  . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 40 Ta thấy rằng, điều kiện liên tục của hàm qua biên phân chia  được thoả mãn, còn điều kiện liên tục của đạo hàm biên phân chia  phụ thuộc vào sự hội tụ của dãy lặp (2.39). Như vậy, trong phương pháp DquangA-VVQuang trình bày ở trên, mỗi lần lặp cần giải quyết một bài toán Neumanm (2.37) trong 1  , sau đó giải một bài toán Dirichlet (2.38) trong 2  . Do đó phương pháp trên được phát triển trên tư tưởng ngược với sơ đồ Dirichlet-Neumann. 2.3.5 Phương pháp chia miền giải bài toán biên gián đoạn mạnh Xét bài toán , , , \ , , . n n u f x u x u x                 (2.40) trong đó 2 2 1/2, ( ), ( ).R f L H     Bài toán được gọi là bài toán biên hỗn hợp mạnh khi trên đoạn biên trơn d n   gồm cả hai loại điều kiện biên Dirichlet và Neumann (hình 2). Trên thế giới đã có nhiều tác giả đề cập các phương pháp giải bài toán biên hỗn hợp mạnh như Arad, Yosibash, Ben-Dor, Yakhot [8], Poullikkas, Karageorghis, Georgiou [18], ... Phát triển phương pháp chia miền theo tư tưởng xác định đạo hàm trên biên phân chia, các tác giả Đặng Quang á, Vũ Vinh Quang đề xuất phương pháp lặp giải bài toán biên với điều kiện biên hỗn hợp mạnh. Các kết quả được tham khảo trong các tài liệu [2, 3, 4, 6]. Chia miền 1 2 1 2 ,      bằng biên 1 2     . Kí hiệu ( 1,2) ii u u i    , 1 1 \ , d      2 2 \ n      (Hình 2) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 41 Tư tưởng của phương pháp là tìm ra các xấp xỉ của 1 1 u g      nhận được bởi sơ đồ lặp sau đây: Hình 2 Bước 1. Cho (0) 2 (0)( ), 0.g L g   (2.41) Bước 2. Với mọi ( )kg trên ( 1,2,...)k  tiến hành giải lần lượt hai bài toán ( ) 1 1 ( ) 1 1 ( ) ( )1 1 , , , , , , k k k k u f x u x u g x               (2.42) ( ) 2 2 ( ) 2 2 ( ) 2 2 ( ) ( ) 2 1 , , , , , , , . k k k n k k u f x u x u x u u x                  (2.43) Bước 3. Tính toán lại xấp xỉ mới .,)1( 2 )( 2)()1(     x u gg k kk  (2.44) trong đó  là tham số lặp cần lựa chọn. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 42 Bằng lý thuyết toán tử, các tác giả đã chứng minh phương pháp lặp là hội tụ, các kết quả thực nghiệm trên máy tính điện tử đã chứng tỏ tính hữu hiệu của phương pháp. Kết luận: Trong chương 2 đã đưa ra cơ sở lý thuyết về phương pháp chia miền cùng các sơ đồ lặp cơ bản, đặc biệt đã giới thiệu một số phương pháp chia miền của các tác giả trên thế giới và trong nước giải quyết bài toán biên Dirichlet và bài toán biên gián đoạn mạnh đã được phát triển trong những năm gần đây. Các kết quả trên là cơ sở cho việc nghiên cứu phát triển hướng đề xuất mô hình tính toán song song trên cơ sở chia miền giải quyết các bài toán cơ học phức tạp. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 43 Chương 3 MÔ HÌNH TÍNH TOÁN SONG SONG GIẢI BÀI TOÁN ELIPTIC DỰA TRÊN CHIA MIỀN 3.1 Các bƣớc lặp trên nhiều miền con Khi miền  được chia thành nhiều miền con )..1(, Mii  , kí hiệu jiij  . Khi đó dạng tách của Lu f trong  được cho bởi         Ø,,,)()( Ø,,,),()( ,..1,, ijijji ijijji ii jxuu jxuu MixfLu (3.1) Thủ tục lặp đa miền được tổng quát hoá như sau: Tô các miền bởi các mầu đen và trắng xen kẽ nhau (Hình 3), đặt  1BI i M   với i  là các miền tô màu đen, \ W B I I I , thực hiện giải các bài toán trong đó ln v vvv    )(,)( .         Ø.:,),()1()()( ,,, 1 1 ijWij k i k j k i Bi k i Ijxuuu IixfLu  (3.2) H×nh 3 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 44 Điều này tạo ra một họ các bài toán con độc lập, tương tự         Ø.,,),()( ,,, 11 1 ijBij k i k j Wj k j Iixuu IjxfLu (3.3) Sơ đồ trên tạo ra một dãy các bài toán con kiểu  và một dãy các bài toán con kiểu  , tất cả các bài toán con này đều được ghép thành từng đôi theo nguyên tắc nếu các bài toán kiểu  giải xong thì có thể tiến hành giải các bài toán con kiểu  . Như vậy ta đã tạo ra một sơ đồ lặp song song cho phép giải các bài toán con một cách độc lập có thể xử lý đồng thời trên máy tính đa nhiệm. Một dạng khác của sơ đồ là việc thay thế sơ đồ trên bằng sơ đồ         Ø.:,),()( ,,, 1 1 ijBij k i k j Wj k j Iixuu IjxfLu Trong trường hợp này, dãy khối song song đã tạo chứa một dãy khối tuần tự như một dãy con thứ 3, khi đó trong quá trình