Luận văn thạc sĩ 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
- 77 trang
- file .pdf
ĐẠI HỌC THÁI NGUYÊN
KHOA CÔNG NGHỆ THÔNG TIN
Cao Thị Anh Thư
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
Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01
Luận văn thạc sỹ Khoa học máy tính
Người hướng dẫn Khoa học:
TS. Vũ Vinh Quang
Thái Nguyên - 2009
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
MỤC LỤC
ĐẶT VẤN ĐỀ ....................................................................................................... 2
Chương 1: Các kiến thức cơ bản về giải số phương trình đạo hàm riêng....... 4
1.1 PHƯƠNG PHÁP SAI PHÂN....................................................................... 4
1.2 THUẬT TOÁN THU GỌN KHỐI LƯỢNG TÍNH TOÁN.......................... 6
1.2.1 Bài toán biên thứ nhất.............................................................................. 6
1.2.2 Bài toán biên thứ hai................................................................................ 12
1.3 ÁP DỤNG ĐỐI VỚI PHƯƠNG TRÌNH ELLIPTIC..................................... 15
1.3.1 Bài toán biên Dirichlet............................................................................. 15
1.3.2 Bài toán biên hỗn hợp.............................................................................. 16
1.4 PHƯƠNG PHÁP LẶP VÀ CÁC SƠ ĐỒ LẶP CƠ BẢN.............................. 18
1.4.1 Không gian năng lượng............................................................................ 18
1.4.2 Phương pháp lặp giải phương trình toán tử............................................ 19
Chương 2: Cơ sở Toán học của phương pháp chia miền.................................. 27
2.1 CÔNG THỨC ĐA MIỀN VÀ PHƯƠNG TRÌNH STEKLOV- POICARE.. 28
2.2 CÁC PHƯƠNG PHÁP LẶP ĐƠN CƠ SỞ.................................................. 30
2.2.1 Phương pháp Dirichlet-Neumann............................................................ 30
2.2.2 Phương pháp Neumann-Neumann............................................................ 31
2.2.3 Phương pháp Robin.................................................................................. 31
2.3 MỘT SỐ THUẬT TOÁN CHIA MIỀN....................................................... 33
2.3.1 Thuật toán chia miền Patrick Le Talle. ................................................... 33
2.3.2 Thuật toán chia miền J.R.Rice, E.A. Vavalis, Daopi Yang...................... 35
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
2.3.3 Thuật toán chia miền Saito-Fujita............................................................ 37
2.3.4 Phương pháp DQuangA-VVQuang.......................................................... 38
2.3.5 Phương pháp chia miền giải bài toán biên gián đoạn mạnh .................. 40
Chương 3: Mô hình tính toán song song giải bài toán Elliptic dựa trên chia
miền ....................................................................................................................... 43
3.1 CÁC BƯỚC LẶP TRÊN NHIỀU MIỀN CON............................................. 43
3.2 MÔ HÌNH TÍNH TOÁN SONG SONG GIẢI BÀI TOÁN BIÊN GIÁN
ĐOẠN MẠNH........................................................................................................ 45
3.2.1.Hướng tiếp cận hiệu chỉnh đạo hàm........................................................ 46
3.2.2. Hướng tiếp cận hiệu chỉnh hàm............................................................... 47
3.3. CÁC KẾT QUẢ THỰC NGHIỆM............................................................... 49
3.4. ỨNG DỤNG MÔ HÌNH SONG SONG GIẢI BÀI TOÁN CƠ HỌC.......... 51
3.4.1 Sơ đồ song song theo hướng hiệu chỉnh đạo hàm ................................... 53
3.4.2 Sơ đồ song song theo hướng hiệu chỉnh hàm .......................................... 57
3.4.3 Các kết quả thực nghiệm.......................................................................... 60
NHẬN XÉT KẾT LUẬN...................................................................................... 63
DANH MỤC CÔNG TRÌNH ĐÃ CÔNG BỐ LIÊN QUAN ĐẾN LUẬN
VĂN ....................................................................................................................... 64
TÀI LIỆU THAM KHẢO.................................................................................... 65
PHỤ LỤC............................................................................................................... 68
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
1
LỜI CẢM ƠN
Sau một thời gian nghiên cứu và thực hiện luận văn thạc sỹ chuyên
ngành Khoa học máy tính, đến nay 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" của tôi đã được
hoàn thiện và đầy đủ. Để có được kết quả như mong muốn tôi luôn nhận được
sự quan tâm, chỉ bảo sự giúp đỡ từ thầy giáo hướng dẫn: Tiến sĩ Vũ Vinh
Quang - Phó trưởng Khoa Công nghệ thông tin- Đại học Thái Nguyên. Nhân
dịp này tôi xin trân trọng gửi lời cảm ơn của mình tới các thầy giáo, các vị
giáo sư của Viện Công nghệ Thông tin, các thầy cô giáo thuộc Khoa Công
nghệ thông tin - Đại học Thái Nguyên đã truyền đạt những kiến thức bổ ích
cho các học viên cao học khoá 6 nơi tôi được học tập và nghiên cứu trong
suốt 2 năm qua. Tôi xin bày tỏ tình cảm và lời cảm ơn chân thành nhất tới các
đồng nghiệp Viễn thông Thái Nguyên, tới bạn bè người thân và gia đình đã
khích lệ, động viên, giúp đỡ tôi trong thời gian qua.
Một lần nữa tôi xin gửi lời cảm ơn sâu sắc nhất tới thầy giáo Vũ Vinh
Quang đã hướng dẫn, tạo điều kiện để tôi được học tập và nghiên cứu hoàn
thiện luận văn của mình.
Tôi xin trân trọng cảm ơn!
Thái Nguyên, ngày 30 tháng10 năm 2009.
Học viên
Cao Thị Anh Thư
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
2
ĐẶT VẤN ĐỀ
Lý thuyết về phương pháp chia miền đã được phát triển trong vòng 20
năm qua, xuất phát từ công thức đa miền và phương trình biên chung Steklov-
Poincare, các phương pháp chia miền được phát triển từ các sơ đồ lặp cơ bản
như: Sơ đồ Dirichlet-Neumann, sơ đồ Neumann-Neumann và sơ đồ Robin
được nghiên cứu bởi tác giả trên thế giới. Có thể thấy cơ sở của các phương
pháp đều xuất phát từ giá trị điều kiện trên biên phân chia từ đó xây dựng các
sơ đồ lặp dạng hai lớp đối với phương trình toán tử. Việc nghiên cứu tính chất
hội tụ của các sơ đồ lặp sử dụng kết quả của các không gian Sobolev và toán
tử Steklov-Poincare.
Nội dung chính của luận văn là trên cơ sở của lý thuyết chia miền,
luận văn đề xuất mô hình tính toán song song giải quyết các bài toán với điều
kiện biên rất phức tạp trên tư tưởng chia miền, tiến hành cài đặt thử nghiệm
mô hình đồng thời ứng dụng mô hình song song giải quyết một bài toán trong
môi trường vật lý bán dẫn. Luận văn cấu trúc gồm 3 chương:
Chương 1: Đưa ra cơ sở về phương pháp lưới, thuật toán thu gọn khối
lượng tính toán giải phương trình lưới và cơ sở lý thuyết về các sơ đồ lặp tổng
quát.
Chương 2: Trình bày tóm tắt cơ sở toán học về phương pháp chia
miền, các sơ đồ lặp cơ bản trong phương pháp chia miền. Một số phương
pháp chia miền của các tác giả trên thế giới và đặc biệt là các sơ đồ lặp trên tư
tưởng hiệu chỉnh hàm hoặc đạo hàm trên biên phân chia của các tác giả Việt
Nam và Nhật Bản, phương pháp chia miền đối với bài toán biên gián đoạn
mạnh.
Chương 3: Trên cơ sở của các sơ đồ lặp theo hướng hiệu chỉnh hàm và
đạo hàm, luận văn đề xuất sơ đồ tính toán song song dựa trên tư tưởng hiệu
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
3
chỉnh hàm hoặc đạo hàm, tiến hành tính toán bằng số so sánh hai sơ đồ tính
toán song song và đồng thời áp dụng phương pháp song song giải quyết một
bài toán cơ học được các tác giả trên thế giới quan tâm.
Các kết quả lý thuyết được kiểm tra bằng các chương trình thực
nghiệm lập trình trong môi trường MATLAB trên máy tính PC.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
4
Chương 1
CÁC KIẾN THỨC CƠ BẢN VỀ GIẢI SỐ PHƢƠNG
TRÌNH ĐẠO HÀM RIÊNG
Trong chương này, chúng tôi 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 cơ sở của phương pháp lưới,
thuật toán thu gọn khối lượng tính toán và 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 cơ sở và kết quả được tham khảo từ
các tài liệu [ 5, 10, 16, 21].
1.1 Phƣơng pháp sai phân
Lƣới sai phân:
u f , x ,
Xét bài toán (1.1)
u g, x .
trong đó ( x, y) R2 , a x b, c y d , chọn 2 số nguyên N > 1 và
M >1, đặt h = (b a) / N gọi là bước lưới theo x , k = (d c) / M gọi là
bước lưới theo y . Đặt xi = a ih, y j = c jk , i 0..N , j 0..M . Mỗi điểm
( xi , y j ) gọi là một nút lưới ký hiệu là nút (i, j ) . Tập tất cả các nút trong ký
hiệu là hk . Nút ở trên biên gọi là nút biên; tập tất cả các nút biên ký hiệu
là hk , tập hk = hk hk gọi là một lưới sai phân trên .
Hàm lƣới: Mỗi hàm số xác định tại các nút của lưới gọi là một hàm
lưới, giá trị của hàm lưới u ( x, y ) tại nút lưới (i, j ) viết tắt là ui , j . Mỗi hàm
u ( x, y ) xác định tại mọi ( x, y ) tạo ra hàm lưới u xác định bởi ui , j .
Bài toán sai phân: Ký hiệu Lu f là tập các hàm số hai biến x, y có
các đạo hàm riêng đến cấp m liên tục trong = Giả sử bài toán có
nghiệm u C 4 () , khi đó:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
5
4u 4u
max( x , y ) | 4 ( x, y) | C1 = const , max( x , y ) | 4 ( x, y ) | C2 = const .
x y
Do đó theo công thức Taylor ta có:
u h2 2u h3 3u
u ( xi 1 , y j ) = u ( xi ) h, y j = u ( xi , y j ) h o(h 4 ) hay
x 2! x 3! x
2 3
u ( xi 1 , y j ) 2u ( xi , y j ) u ( xi 1 , y j ) 2u
= 2 o( h 2 )
h 2
x
Một cách tương tự:
u k 2 2u k 3 3u
u ( xi , y j 1 ) = u ( xi , y j k ) = u ( xi , y j ) k o( k 4 )
y 2! y 3! y
2 3
u k 2 2u k 3 3u
u ( xi , y j 1 ) u ( xi , y j k ) = u ( xi , y j ) k o(k 4 )
y 2! y 3! y
2 3
Do đó:
u ( xi , y j 1 ) 2u ( xi , y j ) u ( xi , y j 1 ) 2u
= 2 o( k 2 )
k 2
y
Vậy ta có:
u ( xi 1 , y j ) 2u ( xi , y j ) u ( xi 1 , y j ) u ( xi , y j 1 ) 2u ( xi , y j ) u ( xi , y j 1 )
=
h2 k2
u o(h 2 k 2 )
Ta đặt:
ui 1, j - 2ui , j ui -1, j ui , j 1 - 2ui , j ui , j -1 -1
hk u
h2 k2
Khi đó chứng tỏ:
khu = u o(h2 k 2 )
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
6
Số hạng O(h 2 +k 2 ) là một vô cùng bé bậc hai. Ta nói toán tử kh xấp xỉ
toán tử , điều đó cho phép thay phương trình vi phân bằng phương trình sai
phân:
hk u = fij , f ij = f ( xi , y j ), ( xi , y j ) hk
tức là:
ui 1, j 2ui , j ui 1 j ui , j 1 2ui , j ui , j 1
f ( xi , y j ), ( xi , y j ) hk (1.2)
h2 k2
đồng thời thay điều kiện biên bằng điều kiện:
uij g ( xi , y j ), ( xi , y j ) hk (1.3)
Ta được bài toán sai phân hoàn chỉnh: tìm hàm lưới u tại các nút (i, j )
thoả mãn hệ phương trình sai phân (1.2) với điều kiện biên (1.3). Như vậy
việc tìm nghiệm xấp xỉ của bài toán vi phân (1.1) với độ chính xác cấp hai
được đưa về việc giải bài toán sai phân (1.2) với điều kiện (1.3) bằng các
phương pháp đại số.
1.2 Thuật toán thu gọn khối lƣợng tính toán
Được đề xuất bởi Samarski-Nicolaev.
Bằng các phép biến đổi đơn giản về vec tơ và ma trận, các bài toán sai
phân luôn luôn được đưa về hệ phương trình vec tơ 3 điểm thuộc một trong
các dạng sau đây:
1.2.1 Bài toán biên thứ nhất
Xét bài toán biên thứ nhất đối với phƣơng trình véc tơ ba điểm
Yj 1 CYj Yj 1 = Fj , 1 j N 1 , Y0 = F0 , YN = FN . (1.4)
Trong đó Yj là véc tơ cần tìm, C là ma trận vuông, Fj là véc tơ cho
trước. ý tưởng của phương pháp rút gọn hoàn toàn giải (1.1) là khử liên tiếp
các ẩn Yj đầu tiên với các j lẻ, sau đó từ các phương trình còn lại khử các Yj
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
7
với j là bội của 2, rồi bội của 4,… Mỗi bước khử sẽ giảm được một nửa số
ẩn. Như vậy nếu N = 2n thì sau một số lần khử sẽ còn lại một phương trình
chứa véc tơ ẩn YN / 2 mà từ đó YN / 2 có thể tính được qua Y0 và YN . Sau khi đã có
được Y0 ,YN / 2 và YN thì quá trình ngược lại là việc tìm các Yj với j là bội của
N N
rồi bội của ,… Rõ ràng, phương pháp rút gọn hoàn toàn là một biến
4 8
thể của phương pháp khử Gauss áp dụng cho bài toán (1.4) trong đó việc khử
các biến được thực hiện theo một thứ tự đặc biệt. Sau đây, ta sẽ mô tả cụ thể
phương pháp. Giả sử N = 2n , n > 0 Ký hiệu C (0) = C , Fj(0) = Fj ; j = 1,2,..., N 1 .
Khi đó (1.4) được viết dưới dạng
Yj 1 C 0Yj Yj 1 = Fj(0) (1 j N 1) , Y0 = F0 , YN = FN . (1.5)
Bước khử thứ nhất: Từ các phương trình đầu của (1.5) ta khử các Yj
với j lẻ. Muốn vậy ta viết 3 phương trình liên tiếp:
Yj 2 C (0)Yj 1 Yj = Fj(0)1 ,
Yj 1 C (0)Yj Yj 1 = Fj(0) ,
Yj C (0)Yj 1 Yj 2 = Fj(0)1
Nhân 2 vế của phương trình thứ hai với C (0) vào bên trái rồi cộng cả 3
phương trình lại ta được
Yj 2 C (1)Yj Yj 2 = Fj(1)1 , j = 2,4,..., N 2 , Y0 = F0 , YN = FN (1.6)
trong đó: C (1) = (C( 0))2 2 E Fj(1) = Fj(0)1 c (0) Fj(0) Fj(0)1 , j = 2,4,..., N 2 .
Nhận xét rằng hệ (1.6) chỉ chứa các Yj với j chẵn, số véc tơ ẩn Yj là
N
1. Do đó nếu giải được hệ này thì các Yj với j lẻ sẽ tìm được từ phương
2
trình
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
8
C (0)Yj = Fj(0) Yj 1 Yj 1 , j = 1,3,..., N 1 (1.7)
Như vậy hệ (1.5) tương đương với hệ gồm (1.6) và (1.7).
Bước khử thứ hai: ở bước khử này ta sẽ tiến hành khử các của hệ (1.6)
với j là bội của 2 nhưng không là bội của 4. Muốn vậy ta viết 3 phương trình
liên tiếp của (1.6)
Yj 4 C (1)Yj 2 Yj = Fj(1) 2 ,
Yj 2 C (1)Yj Yj 2 = Fj(1) ,( j = 4,8,..., N 4) ,
Yj C (1)Yj 2 Yj 4 = Fj(1) 2 .
Nhân 2 vế của phương trình thứ hai với C(1) vào bên trái rồi cộng cả 3
vế phương trình lại ta được
Yj 4 C (2)Yj Yj 4 = Fj(2) , j = 4,8,..., N 4 , Y0 = F0 , YN = FN (1.8)
trong đó: C (2) = (C(1))2 2 E Fj(2) = Fj(1)2 c (1) Fj(1) Fj(1) 2 , j = 4,8,..., N 4 .
N
Hệ (1.8) chỉ chứa 1 Véc tơ ẩn Yj , trong đó j là bội của 4. Nếu
4
giải được hệ này thì các Yj , với j là bội của 4 sẽ tìm được từ phương trình 2
nhưng không là bội của 4 sẽ tìm được từ phương trình:
C (1)Yj = Fj 2 Yj 2 Fj(1) , j = 2,6,10..., N 2 .
Cứ tiếp tục quá trình khử này. Kết qủa là sau bước khử thứ l ta nhận
N
được một hệ gồm l
1 ẩn Yj , trong đó j là bội của 2l
c
Yj 2l C ( l )Yj Yj 2l = Fj( l ) , j = 2l ,2.2l ,3.2l ,..., N 2l , Y0 = F0 , YN = FN (1.9)
và nhóm các phương trình:
C ( k 1)Yj = Fj( k 1) Yj 2k 1 Y j 2k 1 , j = 2k 1 ,3.2k 1 ,..., N 2 , k = l , l 1,...,1, (1.10)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
9
trong đó các ma trận C ( k ) và các véc tơ vế phải Fj( k ) được tính theo các công
thức truy toán:
C ( k ) = (C ( k 1) )2 2E , Fj( k ) = Fj(k2k1)1 C k 1Fj (k 1) Fj 2k 1 ,
j = 2k ,2.2k ,3.2k ,..., N 2k , k =1,2,3... , (1.11)
Từ các bước khử trên suy ra rằng sau n 1 bước khử (l = n 1) ta thu
được hệ chỉ gồm một phương trình đối với biến Y2N 1 = YN /2 là
C ( n 1)Yj = Fj( n 1) Y j 2n 1 Y j 2n 1 = Fj( n 1) Y0 YN ,Y0 = F0YN = FN (1.12)
Với vế phải đã biết. Vì vậy từ (1.12) ta có thể tìm được YN / 2 , và tất cả
các ẩn còn lại được tìm liên tiếp từ các phương trình
C ( k 1)Yj = Fj( k 1) Yj 2k 1 Yj 2k 1 ,
Y0 = F0
YN = FN
(1.13)
j = 2k 1 ,3.2k 1 ,5.2k 1 ,..., N 2k 1 ,
k = n, n 1,...,1
Các công thức trên đã mô tả phương pháp rút gọn hoàn toàn giải. Việc
tính các Fj( k ) theo công thức truy toán có thể dẫn đến việc tích luỹ sai số nếu
như chuẩn của ma trận C ( k 1) lớn hơn 1. Ngoài ra các ma trận C ( k ) nói chung
là các ma trận đầy đủ, thậm chí cả với ma trận ban đầu là C (0) = C là ma trận
ba đường chéo. Điều này dẫn đến tăng khối lượng tính toán khi tính các Fj( k )
theo (1.13). Để khắc phục những khó khăn trên, thay cho Fj( k ) ta sẽ tính các
véc tơ p (j k ) và q (j k ) liên hệ với theo công thức sau:
Fj( k ) = C ( k ) p (j k ) q (j k ) , j = 2k ,2.2k ,3.2k..., N 2k , k = 0,1,2,..., n 1 (1.14)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
10
trong đó ta chọn p (0)j và q (0)j = Fj , j = 1,2,..., N 1 . Bằng các công thức toán
học, có thể thấy mối quan hệ mà p (j k ) và q (j k ) phải thoả mãn như sau.
C ( k ) p (j k ) q (j k ) = C ( k 1) [q (j k 1) p (j k21)k 1 C ( k 1) p (j k 1) p (j k21)k 1 ] q (j k21)k 1 q (j k21)k 1 ,
j = 2k ,2.2k ,3.2k ,...,N 2k ,k = 1,2,3...,
Ta sẽ chọn p (j k ) và q (j k ) thoả mãn q (j k ) = 2 p (j k ) q (j k21)( k 1) q (j k21)( k 1)
Khi đó, kết hợp với công thức C ( k ) 2 E = [c ( k 1) ]2 ta có
C ( k ) p (j k ) = q (j k 1) p (j k21)k 1 C ( k 1) p (j k 1) p (j k21)k 1
Đặt S (j k 1) = p (j k ) p (j k 1) , suy ra S (j k 1) phải thoả mãn
C ( k 1) S (j k 1) = q (j k 1) p (j k21)k 1 p (j k21)k 1
Như vậy ta thu được thuật toán sau đây để xác định các véc tơ p (j k ) và q (j k )
C ( k 1) S (j k 1) = q (j k 1) p (j k21)k 1 p (j k21)k 1 , S (j k 1) = p (j k ) p (j k 1) ,
q (j k ) = 2 p (j k ) q (j k21)( k 1) q (j k21)( k 1) (1.15)
q (0)j = Fj ; p (0)j = 0 , j = 2k ,2.2k ,3.2k ,...,N 2k , k = 0,1,2,...,n 1.
Ký hiệu t (j k 1) = Yj p (j k 1) , ta sẽ thấy rằng Yj có thể tính được từ các
công thức sau
C ( k 1)t (j k 1) = q (j k 1) Yj 2k 1 Y j 2k 1 , Yj = p (j k 1) t j( k 1) ,
Y0 = F0 ;YN = FN , j = 2k ,2.2k ,3.2k ,...,N 2k , k = n, n 1,...,1 (1.16)
Nhận xét rằng các quá trình (1.15) và (1.16) luôn cần tính ma trận
nghịch đảo [C ( k 1)]1 . Bằng các phép biến đổi sơ cấp từ các mối quan hệ của
1 k 1
ma trận C ( k ) và đa thức Chebysev C ( k ) = 2T2k ( C ) , ta có C ( k 1) = (2l =1)Cl ,k 1 ,
2
trong đó
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
11
(2l 1)
Cl ,k 1 = C 2cos E.
2k
Như vậy, chẳng hạn ta có phương trình
C ( k 1) = , (1.17)
thì với việc giải lần lượt các phương trình
Cl ,k 1 l = l 1 , l = 1,2,...,2k 1 , 0 =
sẽ cho ta nghiệm của (1.17) là = 2k 1
Tóm lại qua các bước phân tích trên đây ta có thuật toán rút gọn hoàn
toàn giải bài toán biên thứ nhất như sau
Quá trình xuôi
Bước 1.1 Cho các giá trị ban đầu p (0)j , q (0)j = Fj , j = 1,2,3,..., N 1
Bước 1.2 Với k = 1 giải phương trình
Cp (1)j = q (0)j và tính q (1)j = 2 p (1)j q((0)j 1) q((0),j 1)j =2,4,6,..., N 2
Bước 1.3 Với k = 2,3,..., n 1 xác định các véc tơ
(0)j = q (j k 1) p(( kj 21)k 1 ) p (j k 21)k 1 , j = 2k ,2.2 k ,3.2 k..., N 2k .
Sau đó, với mỗi l = 1,2,...2k 1 và với mỗi j = 2k ,2.2k ,3.2k..., N 2k , giải
phương trình
Cl ,k 1 (j l ) = (j l 1)
Khi đó
k 1 )
p (j k ) = p (j k 1) (2j , q (j k ) = 2 p (j k ) q((kj 21)k 1 ) q j(k2k1)1 , j = 2k ,2.2k ,3.2k..., N 2k
Quá trình ngƣợc
Bước 2.1 Cho các giá trị ban đầu Y0 = F0 ,YN = FN
Bước 2.2 Với k = n, n 1,...,2 tính
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
12
(0)j = q (j k 1) Yj 2k 1 Yj 2k 1 , j = 2k 1 ,3.2k 1...N 2k 1
Sau đó, với mỗi l = 1,2,...,2k 1 và với mỗi j = 2k 1 ,3.2k 1...N 2k 1 , giải
phương trình
Cl ,k 1 (j l ) = (j l 1)
Khi đó:
k 1 )
Yj = p (j k 1) (2j , j = 2 k , 2.2 k ,3.2 k ,...N 2 k
Bước 2.3 Với k = 1, giải phương trình
CYj = q (0)j Yj 1 Yj 1 , j = 1,3,5,..., N 1
1.2.2 Bài toán biên thứ hai
Xét bài toán thứ hai
Y0 = F0 , j = 0,
Yj 1 CYj Yj 1 = Fj ,1 j N 1, (1.18)
2YN 1 CYN = FN .
trong đó N = 2n , n > 0 Để giải bài toán (1.18) ta cũng thực hiện các bước khử
lần lượt như đã được trình bày ở bài toán biên thứ nhất. Sau n phép khử, ta
nhận được các phương trình
Y0 = F0( n ) , 2Y(0) C ( n )YN = FN( n ) . (1.19)
Và nhóm các phương trình
C ( k 1)Yj = Fj( k 1) Y j 2k 1 Y j 2k 1 , j = 2k 1 ,3.2k 1 ,..., N 2 k 1 , k = n, n 1,...,1.
Trong đó Fj( k ) và C ( k ) được xác định bởi công thức truy toán sau
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
13
F0( k ) = F0 ,
Fj( k ) = Fjk1k11 C ( k 1) Fj 1 Fj(k2k1)1 ,
j = 2k ,2.2k ,..., N 2k
FN( k ) = 2 FNk21k 1 C ( k 1) FN( k 1) ,
C ( k ) = [C ( k 1) ]2 2 E ,
Kí hiệu: Fj( k ) = C ( k ) p(jk) q(jk) ,
j = 2k ,2.2k ,..., N 2k , N , k = 0,1,2,..., n
Bằng các phép biến đổi đơn giản và cách chọn p (j k ) và q (j k ) thích hợp,
ta nhận được quá trình sau để xác định các véc tơ p (j k ) và q (j k ) với J N
C ( k 1) S (j k 1) = q (j k 1) p (j k21)( k 1) q (j k21)( k 1)
p (j k ) = p (j k 1) S (j k 1) ,
q (j k ) = 2 p (j k ) q (j k21)( k 1) q (j k21)( k 1) ,
j = 2k ,3.2k ,..., N 2k , k = 0,1,2,..., n 1
q (0)j = Fj , p (0)=0
j
Tương tự, với j = N , ta có:
C ( k 1) S Nk 1 = qN( k 1) 2 pN( k21)(k 1) ,
pN( k ) = pN( k 1) S N( k 1) ,
qN( k ) = 2 pN( k ) 2qN( k21)(k 1) ,
qN(0) = FN ; pN(0) = 0,
Trong đó
Yj = pJ( k 1) t (j k 1) , j = 2k 1 ,3.2k 1 ,..., N 2k 1 , k = n, n 1,...,2,1
Trong đó t (j k 1) là nghiệm của phương trình .
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
14
( k 1) t ( k 1)
C j
= q (j k 1) Yj 2( k 1) Yj 2( k 1) ,
Tóm lại, ta có thuật toán sau đây giải bài toán biên thứ hai.
Quá trình xuôi
Bước 1.1 Xác định các giá trị ban đầu p (0)j = 0; q (0)j = Fj , j = 1,2,..., N
Bước 1.2 Với k = 1,2,..., n 1 xác định các véc tơ:
v (0)j = q (j k 1) p (j k21)( k 1) p (j k21)( k 1) , j = 2k ,2.2k ,..., N 2k
Sau đó, với l = 1,2,...,2( k 1) và với mỗi j = 2k ,2.2k ,..., N 2k , giải
phương trình
Cl ,k 1v (j l ) = v (j l 1)
Khi đó
p (j k ) = p (j k 1) v (2j k 1) , qJ( k ) = 2 p (j k ) q j(k2(1)k 1) q j(k2(1)k 1) , j = 2k ,2.2k ,..., N 2k
Bước 1.3 Với k = 1,2,..., n 1xác định các véc tơ
vN(0) = qN( k 1) 2 pN( k21)(k 1)
Sau đó, với l = 1,2,...,2( k 1) , giải phương trình
Cl ,k 1vN( l ) = vN( l 1)
Khi đó
k 1 )
PN( k ) = pN( k 1) vN(2 , qN( k ) = 2 pN( k ) 2qN( k21)k 1
Quá trình ngƣợc
Bước 2.1 Xác định YN . Xác định véc tơ
vN(0) = qN( n ) 2Y0
Sau đó, với l = 1,2,..., n , giải hệ
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
15
Cl ,n vN( l ) = vN( l 1)
Khi đó
YN = pN( n ) vN( n )
Bước 2.2 Xác định Yj , j = 1,2,..., N 1
Với k = n, n 1,...,2,1, xác định các véc tơ
v (0)j = q (j k 1) Y j 2( k 1) Y j 2( k 1) , j = 2k 1 ,3.2k 1 ,..., N 2k 1
Sau đó, với l = 1,2,...,2k 1 và với mỗi j = 2k 1 ,2.2k 1 ,..., N 2k 1 , giải
phương trình
Cl ,k 1v (j l ) = v (j l 1)
Khi đó
k 1 )
Y j = p (j k 1) v (2j , j = 2k ,2.2k ,3.2k ..., N 2k .
Trên đây là nội dung của thuật toán thu gọi khối lượng tính toán giải
bài toán biên thứ nhất và bài toán biên thứ hai. Trong các tài liệu của
Samaski-Nicolaev [21] đã chứng minh độ phức tạp của các thuật toán là
O ( M N log N ) .
1.3 Áp dụng đối với phƣơng trình elliptic
Trên cơ sở phương pháp lưới, ta thu được các kết quả xây dựng lược
đồ sai phân cho các bài toán Dirichlet và bài toán Neumann
1.3.1 Bài toán biên Dirichlet
Cho là hình chữ nhật = x = ( x1 , x2 ) R2 : 0 < x1 < l1;0 < x2 < l2
Xét bài toán
u = ( x) x
u = g ( x) x = (1.20)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
16
trong đó L2 (); g L2 ()
Rời rạc hoá miền bằng lưới h
h = x = (i, j ) = ( x1i , x2 j ); x1i = ih1 ; x2 j = jh2 ;
l1 l
h1 = ; h2 = 2 ; i = 0,1,..., M ; j = 0,1,..., N .
M N
Bằng cách biến đổi đơn giản ta có thể đưa bài toán sai phân tương ứng
về hệ phương trình vec tơ 3 điểm có dạng như sau:
Yj 1 CYj Yj 1 = Fj , j = 1,2,..., N 1
Y0 = F0 ;YN = FN
Yj = ( y1, j ; y2, j ;...; yM 1, j )T (1.21)
F0 = ( g1,0 ; g 2,0 ;...; g M 1,0 )T
FN = ( g1, N ; g 2, N ;...; g M 1, N )T
Ma trận C có dạng
2(r 1) r 0 ... 0 0 0
r 2(r 1) r ... 0 0 0
0 r 2(r 1) ... 0 0 0
C=
0 0 0 ... 2( r 1) r 0
0 0 0 ... r 2( r 1) r
0 0 0 ... 0 r 2( r 1)
h2 1, j rg 0, j
2
h222, j
h22
Fj Với r = 2
h1
h2 M 2, j
2
h2 M 1, j rg M , j
2
1.3.2 Bài toán biên hỗn hợp
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
17
Cho miền = x = ( x1 , x2 );0 < x1 < l1;0 < x2 < l2
Xét bài toán biên hỗn hợp
u = ( x); x
u = g ( x) với x1 (1.22)
u
= ( x) với x 2
x2
Trong đó: L2 (); g L2 (1 ); L2 (2 )
1 = x = ( x1 ,0);0 x1 l1 x = (l1 , x2 );0 x2 l2 x = (0, x2 );0 x2 l2
2 = x = ( x1 , l2 );0 x1 l1
Tương tự, ta đưa bài toán sai phân về hệ phương trình vec tơ 3 điểm
Y0 = F0
Yj 1 CYj Yj 1 = Fj 1 j N 1 (1.23)
2YN 1 CYN = FN j=N
Trong đó:
F0 = ( y1,0 , y2,0 ,..., yM 1,0 )T ; Yj = ( y1, j , y2, j ,..., yM 1, j )T ; j = 1,..., N
2(r 1) r 0 ... 0 0 0
r 2(r 1) r ... 0 0 0
0 r 2(r 1) ... 0 0 0
C=
0 0 0 ... 2( r 1) r 0
0 0 0 ... r 2( r 1) r
0 0 0 ... 0 r 2( r 1)
h2 1, j rg 0, j
2
h222, j
Fj
h2
2
M 2, j
h22 M 1, j rg M , j
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
KHOA CÔNG NGHỆ THÔNG TIN
Cao Thị Anh Thư
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
Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01
Luận văn thạc sỹ Khoa học máy tính
Người hướng dẫn Khoa học:
TS. Vũ Vinh Quang
Thái Nguyên - 2009
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
MỤC LỤC
ĐẶT VẤN ĐỀ ....................................................................................................... 2
Chương 1: Các kiến thức cơ bản về giải số phương trình đạo hàm riêng....... 4
1.1 PHƯƠNG PHÁP SAI PHÂN....................................................................... 4
1.2 THUẬT TOÁN THU GỌN KHỐI LƯỢNG TÍNH TOÁN.......................... 6
1.2.1 Bài toán biên thứ nhất.............................................................................. 6
1.2.2 Bài toán biên thứ hai................................................................................ 12
1.3 ÁP DỤNG ĐỐI VỚI PHƯƠNG TRÌNH ELLIPTIC..................................... 15
1.3.1 Bài toán biên Dirichlet............................................................................. 15
1.3.2 Bài toán biên hỗn hợp.............................................................................. 16
1.4 PHƯƠNG PHÁP LẶP VÀ CÁC SƠ ĐỒ LẶP CƠ BẢN.............................. 18
1.4.1 Không gian năng lượng............................................................................ 18
1.4.2 Phương pháp lặp giải phương trình toán tử............................................ 19
Chương 2: Cơ sở Toán học của phương pháp chia miền.................................. 27
2.1 CÔNG THỨC ĐA MIỀN VÀ PHƯƠNG TRÌNH STEKLOV- POICARE.. 28
2.2 CÁC PHƯƠNG PHÁP LẶP ĐƠN CƠ SỞ.................................................. 30
2.2.1 Phương pháp Dirichlet-Neumann............................................................ 30
2.2.2 Phương pháp Neumann-Neumann............................................................ 31
2.2.3 Phương pháp Robin.................................................................................. 31
2.3 MỘT SỐ THUẬT TOÁN CHIA MIỀN....................................................... 33
2.3.1 Thuật toán chia miền Patrick Le Talle. ................................................... 33
2.3.2 Thuật toán chia miền J.R.Rice, E.A. Vavalis, Daopi Yang...................... 35
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
2.3.3 Thuật toán chia miền Saito-Fujita............................................................ 37
2.3.4 Phương pháp DQuangA-VVQuang.......................................................... 38
2.3.5 Phương pháp chia miền giải bài toán biên gián đoạn mạnh .................. 40
Chương 3: Mô hình tính toán song song giải bài toán Elliptic dựa trên chia
miền ....................................................................................................................... 43
3.1 CÁC BƯỚC LẶP TRÊN NHIỀU MIỀN CON............................................. 43
3.2 MÔ HÌNH TÍNH TOÁN SONG SONG GIẢI BÀI TOÁN BIÊN GIÁN
ĐOẠN MẠNH........................................................................................................ 45
3.2.1.Hướng tiếp cận hiệu chỉnh đạo hàm........................................................ 46
3.2.2. Hướng tiếp cận hiệu chỉnh hàm............................................................... 47
3.3. CÁC KẾT QUẢ THỰC NGHIỆM............................................................... 49
3.4. ỨNG DỤNG MÔ HÌNH SONG SONG GIẢI BÀI TOÁN CƠ HỌC.......... 51
3.4.1 Sơ đồ song song theo hướng hiệu chỉnh đạo hàm ................................... 53
3.4.2 Sơ đồ song song theo hướng hiệu chỉnh hàm .......................................... 57
3.4.3 Các kết quả thực nghiệm.......................................................................... 60
NHẬN XÉT KẾT LUẬN...................................................................................... 63
DANH MỤC CÔNG TRÌNH ĐÃ CÔNG BỐ LIÊN QUAN ĐẾN LUẬN
VĂN ....................................................................................................................... 64
TÀI LIỆU THAM KHẢO.................................................................................... 65
PHỤ LỤC............................................................................................................... 68
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
1
LỜI CẢM ƠN
Sau một thời gian nghiên cứu và thực hiện luận văn thạc sỹ chuyên
ngành Khoa học máy tính, đến nay 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" của tôi đã được
hoàn thiện và đầy đủ. Để có được kết quả như mong muốn tôi luôn nhận được
sự quan tâm, chỉ bảo sự giúp đỡ từ thầy giáo hướng dẫn: Tiến sĩ Vũ Vinh
Quang - Phó trưởng Khoa Công nghệ thông tin- Đại học Thái Nguyên. Nhân
dịp này tôi xin trân trọng gửi lời cảm ơn của mình tới các thầy giáo, các vị
giáo sư của Viện Công nghệ Thông tin, các thầy cô giáo thuộc Khoa Công
nghệ thông tin - Đại học Thái Nguyên đã truyền đạt những kiến thức bổ ích
cho các học viên cao học khoá 6 nơi tôi được học tập và nghiên cứu trong
suốt 2 năm qua. Tôi xin bày tỏ tình cảm và lời cảm ơn chân thành nhất tới các
đồng nghiệp Viễn thông Thái Nguyên, tới bạn bè người thân và gia đình đã
khích lệ, động viên, giúp đỡ tôi trong thời gian qua.
Một lần nữa tôi xin gửi lời cảm ơn sâu sắc nhất tới thầy giáo Vũ Vinh
Quang đã hướng dẫn, tạo điều kiện để tôi được học tập và nghiên cứu hoàn
thiện luận văn của mình.
Tôi xin trân trọng cảm ơn!
Thái Nguyên, ngày 30 tháng10 năm 2009.
Học viên
Cao Thị Anh Thư
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
2
ĐẶT VẤN ĐỀ
Lý thuyết về phương pháp chia miền đã được phát triển trong vòng 20
năm qua, xuất phát từ công thức đa miền và phương trình biên chung Steklov-
Poincare, các phương pháp chia miền được phát triển từ các sơ đồ lặp cơ bản
như: Sơ đồ Dirichlet-Neumann, sơ đồ Neumann-Neumann và sơ đồ Robin
được nghiên cứu bởi tác giả trên thế giới. Có thể thấy cơ sở của các phương
pháp đều xuất phát từ giá trị điều kiện trên biên phân chia từ đó xây dựng các
sơ đồ lặp dạng hai lớp đối với phương trình toán tử. Việc nghiên cứu tính chất
hội tụ của các sơ đồ lặp sử dụng kết quả của các không gian Sobolev và toán
tử Steklov-Poincare.
Nội dung chính của luận văn là trên cơ sở của lý thuyết chia miền,
luận văn đề xuất mô hình tính toán song song giải quyết các bài toán với điều
kiện biên rất phức tạp trên tư tưởng chia miền, tiến hành cài đặt thử nghiệm
mô hình đồng thời ứng dụng mô hình song song giải quyết một bài toán trong
môi trường vật lý bán dẫn. Luận văn cấu trúc gồm 3 chương:
Chương 1: Đưa ra cơ sở về phương pháp lưới, thuật toán thu gọn khối
lượng tính toán giải phương trình lưới và cơ sở lý thuyết về các sơ đồ lặp tổng
quát.
Chương 2: Trình bày tóm tắt cơ sở toán học về phương pháp chia
miền, các sơ đồ lặp cơ bản trong phương pháp chia miền. Một số phương
pháp chia miền của các tác giả trên thế giới và đặc biệt là các sơ đồ lặp trên tư
tưởng hiệu chỉnh hàm hoặc đạo hàm trên biên phân chia của các tác giả Việt
Nam và Nhật Bản, phương pháp chia miền đối với bài toán biên gián đoạn
mạnh.
Chương 3: Trên cơ sở của các sơ đồ lặp theo hướng hiệu chỉnh hàm và
đạo hàm, luận văn đề xuất sơ đồ tính toán song song dựa trên tư tưởng hiệu
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
3
chỉnh hàm hoặc đạo hàm, tiến hành tính toán bằng số so sánh hai sơ đồ tính
toán song song và đồng thời áp dụng phương pháp song song giải quyết một
bài toán cơ học được các tác giả trên thế giới quan tâm.
Các kết quả lý thuyết được kiểm tra bằng các chương trình thực
nghiệm lập trình trong môi trường MATLAB trên máy tính PC.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
4
Chương 1
CÁC KIẾN THỨC CƠ BẢN VỀ GIẢI SỐ PHƢƠNG
TRÌNH ĐẠO HÀM RIÊNG
Trong chương này, chúng tôi 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 cơ sở của phương pháp lưới,
thuật toán thu gọn khối lượng tính toán và 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 cơ sở và kết quả được tham khảo từ
các tài liệu [ 5, 10, 16, 21].
1.1 Phƣơng pháp sai phân
Lƣới sai phân:
u f , x ,
Xét bài toán (1.1)
u g, x .
trong đó ( x, y) R2 , a x b, c y d , chọn 2 số nguyên N > 1 và
M >1, đặt h = (b a) / N gọi là bước lưới theo x , k = (d c) / M gọi là
bước lưới theo y . Đặt xi = a ih, y j = c jk , i 0..N , j 0..M . Mỗi điểm
( xi , y j ) gọi là một nút lưới ký hiệu là nút (i, j ) . Tập tất cả các nút trong ký
hiệu là hk . Nút ở trên biên gọi là nút biên; tập tất cả các nút biên ký hiệu
là hk , tập hk = hk hk gọi là một lưới sai phân trên .
Hàm lƣới: Mỗi hàm số xác định tại các nút của lưới gọi là một hàm
lưới, giá trị của hàm lưới u ( x, y ) tại nút lưới (i, j ) viết tắt là ui , j . Mỗi hàm
u ( x, y ) xác định tại mọi ( x, y ) tạo ra hàm lưới u xác định bởi ui , j .
Bài toán sai phân: Ký hiệu Lu f là tập các hàm số hai biến x, y có
các đạo hàm riêng đến cấp m liên tục trong = Giả sử bài toán có
nghiệm u C 4 () , khi đó:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
5
4u 4u
max( x , y ) | 4 ( x, y) | C1 = const , max( x , y ) | 4 ( x, y ) | C2 = const .
x y
Do đó theo công thức Taylor ta có:
u h2 2u h3 3u
u ( xi 1 , y j ) = u ( xi ) h, y j = u ( xi , y j ) h o(h 4 ) hay
x 2! x 3! x
2 3
u ( xi 1 , y j ) 2u ( xi , y j ) u ( xi 1 , y j ) 2u
= 2 o( h 2 )
h 2
x
Một cách tương tự:
u k 2 2u k 3 3u
u ( xi , y j 1 ) = u ( xi , y j k ) = u ( xi , y j ) k o( k 4 )
y 2! y 3! y
2 3
u k 2 2u k 3 3u
u ( xi , y j 1 ) u ( xi , y j k ) = u ( xi , y j ) k o(k 4 )
y 2! y 3! y
2 3
Do đó:
u ( xi , y j 1 ) 2u ( xi , y j ) u ( xi , y j 1 ) 2u
= 2 o( k 2 )
k 2
y
Vậy ta có:
u ( xi 1 , y j ) 2u ( xi , y j ) u ( xi 1 , y j ) u ( xi , y j 1 ) 2u ( xi , y j ) u ( xi , y j 1 )
=
h2 k2
u o(h 2 k 2 )
Ta đặt:
ui 1, j - 2ui , j ui -1, j ui , j 1 - 2ui , j ui , j -1 -1
hk u
h2 k2
Khi đó chứng tỏ:
khu = u o(h2 k 2 )
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
6
Số hạng O(h 2 +k 2 ) là một vô cùng bé bậc hai. Ta nói toán tử kh xấp xỉ
toán tử , điều đó cho phép thay phương trình vi phân bằng phương trình sai
phân:
hk u = fij , f ij = f ( xi , y j ), ( xi , y j ) hk
tức là:
ui 1, j 2ui , j ui 1 j ui , j 1 2ui , j ui , j 1
f ( xi , y j ), ( xi , y j ) hk (1.2)
h2 k2
đồng thời thay điều kiện biên bằng điều kiện:
uij g ( xi , y j ), ( xi , y j ) hk (1.3)
Ta được bài toán sai phân hoàn chỉnh: tìm hàm lưới u tại các nút (i, j )
thoả mãn hệ phương trình sai phân (1.2) với điều kiện biên (1.3). Như vậy
việc tìm nghiệm xấp xỉ của bài toán vi phân (1.1) với độ chính xác cấp hai
được đưa về việc giải bài toán sai phân (1.2) với điều kiện (1.3) bằng các
phương pháp đại số.
1.2 Thuật toán thu gọn khối lƣợng tính toán
Được đề xuất bởi Samarski-Nicolaev.
Bằng các phép biến đổi đơn giản về vec tơ và ma trận, các bài toán sai
phân luôn luôn được đưa về hệ phương trình vec tơ 3 điểm thuộc một trong
các dạng sau đây:
1.2.1 Bài toán biên thứ nhất
Xét bài toán biên thứ nhất đối với phƣơng trình véc tơ ba điểm
Yj 1 CYj Yj 1 = Fj , 1 j N 1 , Y0 = F0 , YN = FN . (1.4)
Trong đó Yj là véc tơ cần tìm, C là ma trận vuông, Fj là véc tơ cho
trước. ý tưởng của phương pháp rút gọn hoàn toàn giải (1.1) là khử liên tiếp
các ẩn Yj đầu tiên với các j lẻ, sau đó từ các phương trình còn lại khử các Yj
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
7
với j là bội của 2, rồi bội của 4,… Mỗi bước khử sẽ giảm được một nửa số
ẩn. Như vậy nếu N = 2n thì sau một số lần khử sẽ còn lại một phương trình
chứa véc tơ ẩn YN / 2 mà từ đó YN / 2 có thể tính được qua Y0 và YN . Sau khi đã có
được Y0 ,YN / 2 và YN thì quá trình ngược lại là việc tìm các Yj với j là bội của
N N
rồi bội của ,… Rõ ràng, phương pháp rút gọn hoàn toàn là một biến
4 8
thể của phương pháp khử Gauss áp dụng cho bài toán (1.4) trong đó việc khử
các biến được thực hiện theo một thứ tự đặc biệt. Sau đây, ta sẽ mô tả cụ thể
phương pháp. Giả sử N = 2n , n > 0 Ký hiệu C (0) = C , Fj(0) = Fj ; j = 1,2,..., N 1 .
Khi đó (1.4) được viết dưới dạng
Yj 1 C 0Yj Yj 1 = Fj(0) (1 j N 1) , Y0 = F0 , YN = FN . (1.5)
Bước khử thứ nhất: Từ các phương trình đầu của (1.5) ta khử các Yj
với j lẻ. Muốn vậy ta viết 3 phương trình liên tiếp:
Yj 2 C (0)Yj 1 Yj = Fj(0)1 ,
Yj 1 C (0)Yj Yj 1 = Fj(0) ,
Yj C (0)Yj 1 Yj 2 = Fj(0)1
Nhân 2 vế của phương trình thứ hai với C (0) vào bên trái rồi cộng cả 3
phương trình lại ta được
Yj 2 C (1)Yj Yj 2 = Fj(1)1 , j = 2,4,..., N 2 , Y0 = F0 , YN = FN (1.6)
trong đó: C (1) = (C( 0))2 2 E Fj(1) = Fj(0)1 c (0) Fj(0) Fj(0)1 , j = 2,4,..., N 2 .
Nhận xét rằng hệ (1.6) chỉ chứa các Yj với j chẵn, số véc tơ ẩn Yj là
N
1. Do đó nếu giải được hệ này thì các Yj với j lẻ sẽ tìm được từ phương
2
trình
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
8
C (0)Yj = Fj(0) Yj 1 Yj 1 , j = 1,3,..., N 1 (1.7)
Như vậy hệ (1.5) tương đương với hệ gồm (1.6) và (1.7).
Bước khử thứ hai: ở bước khử này ta sẽ tiến hành khử các của hệ (1.6)
với j là bội của 2 nhưng không là bội của 4. Muốn vậy ta viết 3 phương trình
liên tiếp của (1.6)
Yj 4 C (1)Yj 2 Yj = Fj(1) 2 ,
Yj 2 C (1)Yj Yj 2 = Fj(1) ,( j = 4,8,..., N 4) ,
Yj C (1)Yj 2 Yj 4 = Fj(1) 2 .
Nhân 2 vế của phương trình thứ hai với C(1) vào bên trái rồi cộng cả 3
vế phương trình lại ta được
Yj 4 C (2)Yj Yj 4 = Fj(2) , j = 4,8,..., N 4 , Y0 = F0 , YN = FN (1.8)
trong đó: C (2) = (C(1))2 2 E Fj(2) = Fj(1)2 c (1) Fj(1) Fj(1) 2 , j = 4,8,..., N 4 .
N
Hệ (1.8) chỉ chứa 1 Véc tơ ẩn Yj , trong đó j là bội của 4. Nếu
4
giải được hệ này thì các Yj , với j là bội của 4 sẽ tìm được từ phương trình 2
nhưng không là bội của 4 sẽ tìm được từ phương trình:
C (1)Yj = Fj 2 Yj 2 Fj(1) , j = 2,6,10..., N 2 .
Cứ tiếp tục quá trình khử này. Kết qủa là sau bước khử thứ l ta nhận
N
được một hệ gồm l
1 ẩn Yj , trong đó j là bội của 2l
c
Yj 2l C ( l )Yj Yj 2l = Fj( l ) , j = 2l ,2.2l ,3.2l ,..., N 2l , Y0 = F0 , YN = FN (1.9)
và nhóm các phương trình:
C ( k 1)Yj = Fj( k 1) Yj 2k 1 Y j 2k 1 , j = 2k 1 ,3.2k 1 ,..., N 2 , k = l , l 1,...,1, (1.10)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
9
trong đó các ma trận C ( k ) và các véc tơ vế phải Fj( k ) được tính theo các công
thức truy toán:
C ( k ) = (C ( k 1) )2 2E , Fj( k ) = Fj(k2k1)1 C k 1Fj (k 1) Fj 2k 1 ,
j = 2k ,2.2k ,3.2k ,..., N 2k , k =1,2,3... , (1.11)
Từ các bước khử trên suy ra rằng sau n 1 bước khử (l = n 1) ta thu
được hệ chỉ gồm một phương trình đối với biến Y2N 1 = YN /2 là
C ( n 1)Yj = Fj( n 1) Y j 2n 1 Y j 2n 1 = Fj( n 1) Y0 YN ,Y0 = F0YN = FN (1.12)
Với vế phải đã biết. Vì vậy từ (1.12) ta có thể tìm được YN / 2 , và tất cả
các ẩn còn lại được tìm liên tiếp từ các phương trình
C ( k 1)Yj = Fj( k 1) Yj 2k 1 Yj 2k 1 ,
Y0 = F0
YN = FN
(1.13)
j = 2k 1 ,3.2k 1 ,5.2k 1 ,..., N 2k 1 ,
k = n, n 1,...,1
Các công thức trên đã mô tả phương pháp rút gọn hoàn toàn giải. Việc
tính các Fj( k ) theo công thức truy toán có thể dẫn đến việc tích luỹ sai số nếu
như chuẩn của ma trận C ( k 1) lớn hơn 1. Ngoài ra các ma trận C ( k ) nói chung
là các ma trận đầy đủ, thậm chí cả với ma trận ban đầu là C (0) = C là ma trận
ba đường chéo. Điều này dẫn đến tăng khối lượng tính toán khi tính các Fj( k )
theo (1.13). Để khắc phục những khó khăn trên, thay cho Fj( k ) ta sẽ tính các
véc tơ p (j k ) và q (j k ) liên hệ với theo công thức sau:
Fj( k ) = C ( k ) p (j k ) q (j k ) , j = 2k ,2.2k ,3.2k..., N 2k , k = 0,1,2,..., n 1 (1.14)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
10
trong đó ta chọn p (0)j và q (0)j = Fj , j = 1,2,..., N 1 . Bằng các công thức toán
học, có thể thấy mối quan hệ mà p (j k ) và q (j k ) phải thoả mãn như sau.
C ( k ) p (j k ) q (j k ) = C ( k 1) [q (j k 1) p (j k21)k 1 C ( k 1) p (j k 1) p (j k21)k 1 ] q (j k21)k 1 q (j k21)k 1 ,
j = 2k ,2.2k ,3.2k ,...,N 2k ,k = 1,2,3...,
Ta sẽ chọn p (j k ) và q (j k ) thoả mãn q (j k ) = 2 p (j k ) q (j k21)( k 1) q (j k21)( k 1)
Khi đó, kết hợp với công thức C ( k ) 2 E = [c ( k 1) ]2 ta có
C ( k ) p (j k ) = q (j k 1) p (j k21)k 1 C ( k 1) p (j k 1) p (j k21)k 1
Đặt S (j k 1) = p (j k ) p (j k 1) , suy ra S (j k 1) phải thoả mãn
C ( k 1) S (j k 1) = q (j k 1) p (j k21)k 1 p (j k21)k 1
Như vậy ta thu được thuật toán sau đây để xác định các véc tơ p (j k ) và q (j k )
C ( k 1) S (j k 1) = q (j k 1) p (j k21)k 1 p (j k21)k 1 , S (j k 1) = p (j k ) p (j k 1) ,
q (j k ) = 2 p (j k ) q (j k21)( k 1) q (j k21)( k 1) (1.15)
q (0)j = Fj ; p (0)j = 0 , j = 2k ,2.2k ,3.2k ,...,N 2k , k = 0,1,2,...,n 1.
Ký hiệu t (j k 1) = Yj p (j k 1) , ta sẽ thấy rằng Yj có thể tính được từ các
công thức sau
C ( k 1)t (j k 1) = q (j k 1) Yj 2k 1 Y j 2k 1 , Yj = p (j k 1) t j( k 1) ,
Y0 = F0 ;YN = FN , j = 2k ,2.2k ,3.2k ,...,N 2k , k = n, n 1,...,1 (1.16)
Nhận xét rằng các quá trình (1.15) và (1.16) luôn cần tính ma trận
nghịch đảo [C ( k 1)]1 . Bằng các phép biến đổi sơ cấp từ các mối quan hệ của
1 k 1
ma trận C ( k ) và đa thức Chebysev C ( k ) = 2T2k ( C ) , ta có C ( k 1) = (2l =1)Cl ,k 1 ,
2
trong đó
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
11
(2l 1)
Cl ,k 1 = C 2cos E.
2k
Như vậy, chẳng hạn ta có phương trình
C ( k 1) = , (1.17)
thì với việc giải lần lượt các phương trình
Cl ,k 1 l = l 1 , l = 1,2,...,2k 1 , 0 =
sẽ cho ta nghiệm của (1.17) là = 2k 1
Tóm lại qua các bước phân tích trên đây ta có thuật toán rút gọn hoàn
toàn giải bài toán biên thứ nhất như sau
Quá trình xuôi
Bước 1.1 Cho các giá trị ban đầu p (0)j , q (0)j = Fj , j = 1,2,3,..., N 1
Bước 1.2 Với k = 1 giải phương trình
Cp (1)j = q (0)j và tính q (1)j = 2 p (1)j q((0)j 1) q((0),j 1)j =2,4,6,..., N 2
Bước 1.3 Với k = 2,3,..., n 1 xác định các véc tơ
(0)j = q (j k 1) p(( kj 21)k 1 ) p (j k 21)k 1 , j = 2k ,2.2 k ,3.2 k..., N 2k .
Sau đó, với mỗi l = 1,2,...2k 1 và với mỗi j = 2k ,2.2k ,3.2k..., N 2k , giải
phương trình
Cl ,k 1 (j l ) = (j l 1)
Khi đó
k 1 )
p (j k ) = p (j k 1) (2j , q (j k ) = 2 p (j k ) q((kj 21)k 1 ) q j(k2k1)1 , j = 2k ,2.2k ,3.2k..., N 2k
Quá trình ngƣợc
Bước 2.1 Cho các giá trị ban đầu Y0 = F0 ,YN = FN
Bước 2.2 Với k = n, n 1,...,2 tính
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
12
(0)j = q (j k 1) Yj 2k 1 Yj 2k 1 , j = 2k 1 ,3.2k 1...N 2k 1
Sau đó, với mỗi l = 1,2,...,2k 1 và với mỗi j = 2k 1 ,3.2k 1...N 2k 1 , giải
phương trình
Cl ,k 1 (j l ) = (j l 1)
Khi đó:
k 1 )
Yj = p (j k 1) (2j , j = 2 k , 2.2 k ,3.2 k ,...N 2 k
Bước 2.3 Với k = 1, giải phương trình
CYj = q (0)j Yj 1 Yj 1 , j = 1,3,5,..., N 1
1.2.2 Bài toán biên thứ hai
Xét bài toán thứ hai
Y0 = F0 , j = 0,
Yj 1 CYj Yj 1 = Fj ,1 j N 1, (1.18)
2YN 1 CYN = FN .
trong đó N = 2n , n > 0 Để giải bài toán (1.18) ta cũng thực hiện các bước khử
lần lượt như đã được trình bày ở bài toán biên thứ nhất. Sau n phép khử, ta
nhận được các phương trình
Y0 = F0( n ) , 2Y(0) C ( n )YN = FN( n ) . (1.19)
Và nhóm các phương trình
C ( k 1)Yj = Fj( k 1) Y j 2k 1 Y j 2k 1 , j = 2k 1 ,3.2k 1 ,..., N 2 k 1 , k = n, n 1,...,1.
Trong đó Fj( k ) và C ( k ) được xác định bởi công thức truy toán sau
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
13
F0( k ) = F0 ,
Fj( k ) = Fjk1k11 C ( k 1) Fj 1 Fj(k2k1)1 ,
j = 2k ,2.2k ,..., N 2k
FN( k ) = 2 FNk21k 1 C ( k 1) FN( k 1) ,
C ( k ) = [C ( k 1) ]2 2 E ,
Kí hiệu: Fj( k ) = C ( k ) p(jk) q(jk) ,
j = 2k ,2.2k ,..., N 2k , N , k = 0,1,2,..., n
Bằng các phép biến đổi đơn giản và cách chọn p (j k ) và q (j k ) thích hợp,
ta nhận được quá trình sau để xác định các véc tơ p (j k ) và q (j k ) với J N
C ( k 1) S (j k 1) = q (j k 1) p (j k21)( k 1) q (j k21)( k 1)
p (j k ) = p (j k 1) S (j k 1) ,
q (j k ) = 2 p (j k ) q (j k21)( k 1) q (j k21)( k 1) ,
j = 2k ,3.2k ,..., N 2k , k = 0,1,2,..., n 1
q (0)j = Fj , p (0)=0
j
Tương tự, với j = N , ta có:
C ( k 1) S Nk 1 = qN( k 1) 2 pN( k21)(k 1) ,
pN( k ) = pN( k 1) S N( k 1) ,
qN( k ) = 2 pN( k ) 2qN( k21)(k 1) ,
qN(0) = FN ; pN(0) = 0,
Trong đó
Yj = pJ( k 1) t (j k 1) , j = 2k 1 ,3.2k 1 ,..., N 2k 1 , k = n, n 1,...,2,1
Trong đó t (j k 1) là nghiệm của phương trình .
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
14
( k 1) t ( k 1)
C j
= q (j k 1) Yj 2( k 1) Yj 2( k 1) ,
Tóm lại, ta có thuật toán sau đây giải bài toán biên thứ hai.
Quá trình xuôi
Bước 1.1 Xác định các giá trị ban đầu p (0)j = 0; q (0)j = Fj , j = 1,2,..., N
Bước 1.2 Với k = 1,2,..., n 1 xác định các véc tơ:
v (0)j = q (j k 1) p (j k21)( k 1) p (j k21)( k 1) , j = 2k ,2.2k ,..., N 2k
Sau đó, với l = 1,2,...,2( k 1) và với mỗi j = 2k ,2.2k ,..., N 2k , giải
phương trình
Cl ,k 1v (j l ) = v (j l 1)
Khi đó
p (j k ) = p (j k 1) v (2j k 1) , qJ( k ) = 2 p (j k ) q j(k2(1)k 1) q j(k2(1)k 1) , j = 2k ,2.2k ,..., N 2k
Bước 1.3 Với k = 1,2,..., n 1xác định các véc tơ
vN(0) = qN( k 1) 2 pN( k21)(k 1)
Sau đó, với l = 1,2,...,2( k 1) , giải phương trình
Cl ,k 1vN( l ) = vN( l 1)
Khi đó
k 1 )
PN( k ) = pN( k 1) vN(2 , qN( k ) = 2 pN( k ) 2qN( k21)k 1
Quá trình ngƣợc
Bước 2.1 Xác định YN . Xác định véc tơ
vN(0) = qN( n ) 2Y0
Sau đó, với l = 1,2,..., n , giải hệ
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
15
Cl ,n vN( l ) = vN( l 1)
Khi đó
YN = pN( n ) vN( n )
Bước 2.2 Xác định Yj , j = 1,2,..., N 1
Với k = n, n 1,...,2,1, xác định các véc tơ
v (0)j = q (j k 1) Y j 2( k 1) Y j 2( k 1) , j = 2k 1 ,3.2k 1 ,..., N 2k 1
Sau đó, với l = 1,2,...,2k 1 và với mỗi j = 2k 1 ,2.2k 1 ,..., N 2k 1 , giải
phương trình
Cl ,k 1v (j l ) = v (j l 1)
Khi đó
k 1 )
Y j = p (j k 1) v (2j , j = 2k ,2.2k ,3.2k ..., N 2k .
Trên đây là nội dung của thuật toán thu gọi khối lượng tính toán giải
bài toán biên thứ nhất và bài toán biên thứ hai. Trong các tài liệu của
Samaski-Nicolaev [21] đã chứng minh độ phức tạp của các thuật toán là
O ( M N log N ) .
1.3 Áp dụng đối với phƣơng trình elliptic
Trên cơ sở phương pháp lưới, ta thu được các kết quả xây dựng lược
đồ sai phân cho các bài toán Dirichlet và bài toán Neumann
1.3.1 Bài toán biên Dirichlet
Cho là hình chữ nhật = x = ( x1 , x2 ) R2 : 0 < x1 < l1;0 < x2 < l2
Xét bài toán
u = ( x) x
u = g ( x) x = (1.20)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
16
trong đó L2 (); g L2 ()
Rời rạc hoá miền bằng lưới h
h = x = (i, j ) = ( x1i , x2 j ); x1i = ih1 ; x2 j = jh2 ;
l1 l
h1 = ; h2 = 2 ; i = 0,1,..., M ; j = 0,1,..., N .
M N
Bằng cách biến đổi đơn giản ta có thể đưa bài toán sai phân tương ứng
về hệ phương trình vec tơ 3 điểm có dạng như sau:
Yj 1 CYj Yj 1 = Fj , j = 1,2,..., N 1
Y0 = F0 ;YN = FN
Yj = ( y1, j ; y2, j ;...; yM 1, j )T (1.21)
F0 = ( g1,0 ; g 2,0 ;...; g M 1,0 )T
FN = ( g1, N ; g 2, N ;...; g M 1, N )T
Ma trận C có dạng
2(r 1) r 0 ... 0 0 0
r 2(r 1) r ... 0 0 0
0 r 2(r 1) ... 0 0 0
C=
0 0 0 ... 2( r 1) r 0
0 0 0 ... r 2( r 1) r
0 0 0 ... 0 r 2( r 1)
h2 1, j rg 0, j
2
h222, j
h22
Fj Với r = 2
h1
h2 M 2, j
2
h2 M 1, j rg M , j
2
1.3.2 Bài toán biên hỗn hợp
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
17
Cho miền = x = ( x1 , x2 );0 < x1 < l1;0 < x2 < l2
Xét bài toán biên hỗn hợp
u = ( x); x
u = g ( x) với x1 (1.22)
u
= ( x) với x 2
x2
Trong đó: L2 (); g L2 (1 ); L2 (2 )
1 = x = ( x1 ,0);0 x1 l1 x = (l1 , x2 );0 x2 l2 x = (0, x2 );0 x2 l2
2 = x = ( x1 , l2 );0 x1 l1
Tương tự, ta đưa bài toán sai phân về hệ phương trình vec tơ 3 điểm
Y0 = F0
Yj 1 CYj Yj 1 = Fj 1 j N 1 (1.23)
2YN 1 CYN = FN j=N
Trong đó:
F0 = ( y1,0 , y2,0 ,..., yM 1,0 )T ; Yj = ( y1, j , y2, j ,..., yM 1, j )T ; j = 1,..., N
2(r 1) r 0 ... 0 0 0
r 2(r 1) r ... 0 0 0
0 r 2(r 1) ... 0 0 0
C=
0 0 0 ... 2( r 1) r 0
0 0 0 ... r 2( r 1) r
0 0 0 ... 0 r 2( r 1)
h2 1, j rg 0, j
2
h222, j
Fj
h2
2
M 2, j
h22 M 1, j rg M , j
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn