Tài liệu Đề tài 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: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
ĐẠ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
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..................................................
77 trang |
Chia sẻ: hunglv | Lượt xem: 1369 | Lượt tải: 0
Bạn đang xem trước 20 trang mẫu tài liệu Đề tài 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, để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
ĐẠ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
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
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
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
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
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
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:
Xét bài toán , ,
, .
u f x
u g x
(1.1)
trong đó
2( , ) , ,x y R a x b c y d
, chọn 2 số nguyên
>1N
và
>1M
, đặ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
= , = , 0.. , 0.. .
i j
x a ih y c jk i N j M
Mỗi điểm
( , )
i j
x y
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à
,i j
u
. 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
,i j
u
.
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
4 ( )u C
, khi đó:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
5
4
1( , ) 4
| ( , ) | =
x y
u
max x y C const
x
, 4
2( , ) 4
| ( , ) | =
x y
u
max x y C const
y
.
Do đó theo công thức Taylor ta có:
1
( , ) = ( ) ,
i j i j
u x y u x h y
2 2 3 3
4
2 3
= ( , ) ( )
2! 3!
i j
u h u h u
u x y h o h
x x x
hay
2
1 1 2
2 2
( , ) 2 ( , ) ( , )
= ( )i j i j i j
u x y u x y u x y u
o h
h x
Một cách tương tự:
1
( , ) = ( , )
i j i j
u x y u x y k
2 2 3 3
4
2 3
= ( , ) ( )
2! 3!
i j
u k u k u
u x y k o k
y y y
1
( , ) ( , )
i j i j
u x y u x y k
2 2 3 3
4
2 3
= ( , ) ( )
2! 3!
i j
u k u k u
u x y k o k
y y y
Do đó:
2
1 1 2
2 2
( , ) 2 ( , ) ( , )
= ( )i j i j i j
u x y u x y u x y u
o k
k y
Vậy ta có:
1 1 1 1
2 2
2 2
( , ) 2 ( , ) ( , ) ( , ) 2 ( , ) ( , )
=
( )
i j i j i j i j i j i j
u x y u x y u x y u x y u x y u x y
h k
u o h k
Ta đặt:
1, , -1, , 1 , , -1
2 2
- 2 - 2 -1
i j i j i j i j i j i j
hk
u u u u u u
u
h k
Khi đó chứng tỏ:
2 2= ( )
kh
u u o h k
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
6
Số hạng
2 2O(h +k )
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 ij ij i j i j hk
u f f f x y x y
tức là:
1, , 1 , 1 , ,
2 2
2 2 1
( , ), ( , )i j i j i j i j i j i j
i j i j hk
u u u u u u
f x y x y
h k
(1.2)
đồng thời thay điều kiện biên bằng điều kiện:
( , ), ( , )
ij i j i j hk
u g x y x y
(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
1 1
=
j j j j
Y CY Y F
,
1 1j N
,
0 0
=Y F
,
=
N N
Y F
. (1.4)
Trong đó
j
Y
là véc tơ cần tìm,
C
là ma trận vuông,
j
F
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
j
Y
đầu tiên với các
j
lẻ, sau đó từ các phương trình còn lại khử các
j
Y
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
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
= 2nN
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
/2N
Y
mà từ đó
/2N
Y
có thể tính được qua
0
Y
và
N
Y
. Sau khi đã có
được
0 /2
,
N
Y Y
và
N
Y
thì quá trình ngược lại là việc tìm các
j
Y
với
j
là bội của
4
N rồi bội của
8
N ,… Rõ ràng, phương pháp rút gọn hoàn toàn là một biến
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ử
= 2 , > 0nN n
Ký hiệu
(0) (0)= , = ; =1,2,..., 1
j j
C C F F j N
.
Khi đó (1.4) được viết dưới dạng
0 (0)
1 1
= (1 1)
j j j j
Y C Y Y F j N
,
0 0
=Y F
,
=
N N
Y F
. (1.5)
Bước khử thứ nhất: Từ các phương trình đầu của (1.5) ta khử các
j
Y
với
j
lẻ. Muốn vậy ta viết 3 phương trình liên tiếp:
(0) (0)
2 1 1
=
j j j j
Y C Y Y F
,
(0) (0)
1 1
=
j j j j
Y C Y Y F
,
(0) (0)
1 2 1
=
j j j j
Y C Y Y F
Nhân 2 vế của phương trình thứ hai với
(0)C
vào bên trái rồi cộng cả 3
phương trình lại ta được
(1) (1)
2 2 1
= , = 2,4,..., 2
j j j j
Y C Y Y F j N
,
0 0
=Y F
,
=
N N
Y F
(1.6)
trong đó:
(1) ( 2= ( 0)) 2C C E
(1) (0) (0) (0) (0)
1 1
= , = 2,4,..., 2
j j j j
F F c F F j N
.
Nhận xét rằng hệ (1.6) chỉ chứa các
j
Y
với
j
chẵn, số véc tơ ẩn
j
Y
là
1
2
N
. Do đó nếu giải được hệ này thì các
j
Y
với
j
lẻ sẽ tìm được từ phương
trình
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
8
(0) (0)
1 1
= , =1,3,..., 1
j j j j
C Y F Y Y j N
(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)
(1) (1)
4 2 2
=
j j j j
Y C Y Y F
,
(1) (1)
2 2
= ,( = 4,8,..., 4)
j j j j
Y C Y Y F j N
,
(1) (1)
2 4 2
=
j j j j
Y C Y Y F
.
Nhân 2 vế của phương trình thứ hai với
(1)
C
vào bên trái rồi cộng cả 3
vế phương trình lại ta được
(2) (2)
4 4
= , = 4,8,..., 4
j j j j
Y C Y Y F j N
,
0 0
=Y F
,
=
N N
Y F
(1.8)
trong đó:
(2) ( 2= ( 1)) 2C C E
(2) (1) (1) (1) (1)
2 2
= , = 4,8,..., 4
j j j j
F F c F F j N
.
Hệ (1.8) chỉ chứa
1
4
N
Véc tơ ẩn
j
Y
, trong đó
j
là bội của 4. Nếu
giải được hệ này thì các
j
Y
, 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:
(1) (1)
2 2
= , = 2,6,10..., 2
j j j j
C Y F Y F j N
.
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
được một hệ gồm
1
l
N
c
ẩn
j
Y
, trong đó
j
là bội của
2l
( ) ( )
2 2
= , = 2 ,2.2 ,3.2 ,..., 2l l l l l l
l j l jj j
Y C Y Y F j N
,
0 0
=Y F
,
=
N N
Y F
(1.9)
và nhóm các phương trình:
( 1) ( 1)
1 12 2
=k k
j j k kj j
C Y F Y Y
,
1 1= 2 ,3.2 ,..., 2k kj N
,
= , 1,...,1,k l l
(1.10)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
9
trong đó các ma trận
( )kC
và các véc tơ vế phải
( )k
j
F
được tính theo các công
thức truy toán:
( ) ( 1) 2= ( ) 2k kC C E
,
( ) ( 1) 1 ( 1)
1 12 2
=k k k k
j k j kj j
F F C F F
,
= 2 ,2.2 ,3.2 ,..., 2 , =1,2,3...k k k kj N k
, (1.11)
Từ các bước khử trên suy ra rằng sau
1n
bước khử
( = 1)l n
ta thu
được hệ chỉ gồm một phương trình đối với biến
2 /2
1=N
N
Y Y
là
( 1) ( 1) ( 1)
1 1 0 0 02 2
= = , = =n n n
j j n n j N N Nj j
C Y F Y Y F Y Y Y FY F
(1.12)
Với vế phải đã biết. Vì vậy từ (1.12) ta có thể tìm được
/2N
Y
, 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
( 1) ( 1)
1 12 2
0 0
1 1 1 1
= ,
=
=
= 2 ,3.2 ,5.2 ,..., 2 ,
= , 1,...,1
k k
j j k kj j
N N
k k k k
C Y F Y Y
Y F
Y F
j N
k n n
(1.13)
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
( )k
j
F
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
( 1)kC
lớn hơn 1. Ngoài ra các ma trận
( )kC
nói chung
là các ma trận đầy đủ, thậm chí cả với ma trận ban đầu là
(0) =C 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
( )k
j
F
theo (1.13). Để khắc phục những khó khăn trên, thay cho
( )k
j
F
ta sẽ tính các
véc tơ
( )k
j
p
và
( )k
j
q
liên hệ với theo công thức sau:
( ) ( ) ( ) ( )= , = 2 ,2.2 ,3.2 ..., 2 , = 0,1,2,..., 1k k k k k k k k
j j j
F C p q j N k n
(1.14)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
10
trong đó ta chọn
(0)
j
p
và
(0) = , =1,2,..., 1
j j
q F j N
. Bằng các công thức toán
học, có thể thấy mối quan hệ mà
( )k
j
p
và
( )k
j
q
phải thoả mãn như sau.
( ) ( ) ( ) =k k k
j j
C p q ( 1) ( 1) ( 1) ( 1) ( 1) ( 1) ( 1) ( 1)
1 1 1 12 2 2 2
[ ]k k k k k k k k
j k j k k kj j j j
C q p C p p q q
,
= 2 ,2.2 ,3.2 ,..., 2 , =1,2,3...k k k kj N k
,
Ta sẽ chọn
( )k
j
p
và
( )k
j
q
thoả mãn
( ) ( ) ( 1) ( 1)
2 ( 1) 2 ( 1)
= 2k k k k
j j j k j k
q p q q
Khi đó, kết hợp với công thức
( ) ( 1) 22 = [ ]k kC E c
ta có
( ) ( ) ( 1) ( 1) ( 1) ( 1) ( 1)
1 12 2
=k k k k k k k
j j k j kj j
C p q p C p p
Đặt
( 1) ( ) ( 1)=k k k
j j j
S p p
, suy ra
( 1)k
j
S
phải thoả mãn
( 1) ( 1) ( 1) ( 1) ( 1)
1 12 2
=k k k k k
j j k kj j
C S q p p
Như vậy ta thu được thuật toán sau đây để xác định các véc tơ
( )k
j
p
và
( )k
j
q
( 1) ( 1) ( 1) ( 1) ( 1)
1 12 2
=k k k k k
j j k kj j
C S q p p
,
( 1) ( ) ( 1)=k k k
j j j
S p p
,
( ) ( ) ( 1) ( 1)
2 ( 1) 2 ( 1)
= 2k k k k
j j j k j k
q p q q
(1.15)
(0) (0)= ; = 0
j j j
q F p
,
= 2 ,2.2 ,3.2 ,..., 2k k k kj N
,
= 0,1,2,..., 1k n
.
Ký hiệu
( 1) ( 1)=k k
j j j
t Y p
, ta sẽ thấy rằng
j
Y
có thể tính được từ các
công thức sau
( 1) ( 1) ( 1)
1 12 2
=k k k
j j k kj j
C t q Y Y
,
( 1) ( 1)= k k
j j j
Y p t
,
0 0
= ; =
N N
Y F Y F
,
= 2 ,2.2 ,3.2 ,..., 2k k k kj N
,
= , 1,...,1k n n
(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
( 1[ 1)]C k
. Bằng các phép biến đổi sơ cấp từ các mối quan hệ của
ma trận
( )kC
và đa thức Chebysev
( )
2
1
= 2 ( )
2
k
k
C T C
, ta có
1( 1) 2
( =1) , 1
=
kk
l l k
C C
,
trong đó
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
11
, 1
(2 1)
= 2cos
2
l k k
l
C C E
.
Như vậy, chẳng hạn ta có phương trình
( 1) =kC
, (1.17)
thì với việc giải lần lượt các phương trình
1
, 1 1
= , =1,2,...,2k
l k l l
C l
,
0
=
sẽ cho ta nghiệm của (1.17) là
12
=
k
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
(0) (0), = , =1,2,3,..., 1
j j j
p q F j N
Bước 1.2 Với
=1k
giải phương trình
(1) (0)=
j j
Cp q
và tính
(1) (1) (0) (0), =2,4,6,..., 2
( 1) ( 1)
= 2 j N
j j j j
q p q q
Bước 1.3 Với
= 2,3,..., 1k n
xác định các véc tơ
(0) ( 1) ( 1) ( 1)
1 1( 2 ) 2
= , = 2 ,2.2 ,3.2 ..., 2k k k k k k k
j j k kj j
q p p j N
.
Sau đó, với mỗi
1=1,2,...2kl
và với mỗi
= 2 ,2.2 ,3.2 ..., 2k k k kj N
, giải
phương trình
( ) ( 1)
, 1
=l l
l k j j
C
Khi đó
1( ) ( 1) (2 )=
kk k
j j j
p p
,
( ) ( ) ( 1) ( 1)
1 1( 2 ) 2
= 2 , = 2 ,2.2 ,3.2 ..., 2k k k k k k k k
j j k kj j
q p q q j N
Quá trình ngƣợc
Bước 2.1 Cho các giá trị ban đầu
0 0
= , =
N N
Y F Y F
Bước 2.2 Với
= , 1,...,2k n n
tính
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
12
(0) ( 1) 1 1 1
1 12 2
= , = 2 ,3.2 ... 2k k k k
j j k kj j
q Y Y j N
Sau đó, với mỗi
1=1,2,...,2kl
và với mỗi
1 1 1= 2 ,3.2 ... 2k k kj N
, giải
phương trình
( ) ( 1)
, 1
=l l
l k j j
C
Khi đó:
1( 1) (2 )= , = 2 ,2.2 ,3.2 ,... 2
kk k k k k
j j j
Y p j N
Bước 2.3 Với
=1k
, giải phương trình
(0)
1 1
= , =1,3,5,..., 1
j j j j
CY q Y Y j N
1.2.2 Bài toán biên thứ hai
Xét bài toán thứ hai
0 0
1 1
1
= , = 0,
= ,1 1,
2 = .
j j j j
N N N
Y F j
Y CY Y F j N
Y CY F
(1.18)
trong đó
= 2 , > 0nN n
Để 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
( ) ( ) ( )
0 0 (0)
= , 2 =n n n
N N
Y F Y C Y F
. (1.19)
Và nhóm các phương trình
( 1) ( 1) 1 1 1
1 12 2
= , = 2 ,3.2 ,..., 2 , = , 1,...,1.k k k k k
j j k kj j
C Y F Y Y j N k n n
Trong đó
( )k
j
F
và
( )kC
đượ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
13
( )
0 0
( ) 1 ( 1) ( 1)
1 1 11 2
( ) 1 ( 1) ( 1)
12
( ) ( 1) 2
= ,
= ,
= 2 ,2.2 ,..., 2
= 2 ,
= [ ] 2 ,
k
k k k k
j k j kj j
k k k
k k k k
N k NN
k k
F F
F F C F F
j N
F F C F
C C E
Kí hiệu:
( ) ( ) ( ) ( )=k k k k
j j j
F C p q
,
= 2 ,2.2 ,..., 2 , , = 0,1,2,...,k k kj N N k n
Bằng các phép biến đổi đơn giản và cách chọn
( )k
j
p
và
( )k
j
q
thích hợp,
ta nhận được quá trình sau để xác định các véc tơ
( )k
j
p
và
( )k
j
q
với
J N
( 1) ( 1) ( 1) ( 1) ( 1)
( 1) ( 1)
2 2
( ) ( 1) ( 1)
( ) ( ) ( 1) ( 1)
( 1) ( 1)
2 2
(0) (0)=0
=
= ,
= 2 ,
= 2 ,3.2 ,..., 2 , = 0,1,2,..., 1
= ,
k k k k k
j j k k
j j
k k k
j j j
k k k k
j j k k
j j
k k k
j j j
C S q p q
p p S
q p q q
j N k n
q F p
Tương tự, với
=j N
, ta có:
( 1) 1 ( 1) ( 1)
( 1)
2
( ) ( 1) ( 1)
( ) ( ) ( 1)
( 1)
2
(0) (0)
= 2 ,
= ,
= 2 2 ,
= ; = 0,
k k k k
N N k
N
k k k
N N N
k k k
N N k
N
N N N
C S q p
p p S
q p q
q F p
Trong đó
( 1) ( 1)= k k
j J j
Y p t
,
1 1 1= 2 ,3.2 ,..., 2 , = , 1,...,2,1k k kj N k n n
Trong đó
( 1)k
j
t
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
14
( 1)
( 1)
( 1)
( 1) ( 1)
2 2
=
k
k t
kj
j k k
j j
C q Y Y
,
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
(0) (0)= 0; = , =1,2,...,
j j j
p q F j N
Bước 1.2 Với
=1,2,..., 1k n
xác định các véc tơ:
(0) ( 1) ( 1) ( 1)
( 1) ( 1)
2 2
= k k k
j j k k
j j
v q p p
,
= 2 ,2.2 ,..., 2k k kj N
Sau đó, với
( 1)=1,2,...,2 kl
và với mỗi
= 2 ,2.2 ,..., 2k k kj N
, giải
phương trình
( ) ( 1)
, 1
=l l
l k j j
C v v
Khi đó
( ) ( 1) (2 1)=k k k
j j j
p p v
,
( ) ( ) ( 1) ( 1)
( 1) ( 1)
2 2
= 2k k k k
J j k k
j j
q p q q
,
= 2 ,2.2 ,..., 2k k kj N
Bước 1.3 Với
=1,2,..., 1k n
xác định các véc tơ
(0) ( 1) ( 1)
( 1)
2
= 2k k
N N k
N
v q p
Sau đó, với
( 1)=1,2,...,2 kl
, giải phương trình
( ) ( 1)
, 1
=l l
l k N N
C v v
Khi đó
1( ) ( 1) (2 )=
kk k
N N N
P p v
,
( ) ( ) ( 1)
12
= 2 2k k k
N N kN
q p q
Quá trình ngƣợc
Bước 2.1 Xác định
N
Y
. Xác định véc tơ
(0) ( )
0
= 2n
N N
v q Y
Sau đó, với
=1,2,...,l n
, giải hệ
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
15
( ) ( 1)
,
=l l
l n N N
C v v
Khi đó
( ) ( )= n n
N N N
Y p v
Bước 2.2 Xác định
, =1,2,..., 1
j
Y j N
Với
= , 1,...,2,1,k n n
xác định các véc tơ
(0) ( 1)
( 1) ( 1)
2 2
= k
j j k k
j j
v q Y Y
,
1 1 1= 2 ,3.2 ,..., 2k k kj N
Sau đó, với
1=1,2,...,2kl
và với mỗi
1 1 1= 2 ,2.2 ,..., 2k k kj N
, giải
phương trình
( ) ( 1)
, 1
=l l
l k j j
C v v
Khi đó
1( 1) (2 )=
kk
j j j
Y p v
,
= 2 ,2.2 ,3.2 ..., 2k k k kj N
.
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
( log )M N 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
21 2 1 1 2 2= = ( , ) :0 < < ;0 < <x x x R x l x l
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
16
trong đó
2 2( ); ( )L g L
Rời rạc hoá miền
bằng lưới
h
1 2 1 1 2 2= = ( , ) = ( , ); = ; = ;h i j i jx i j x x x ih x jh
1
1
=
l
h
M
;
2
2
=
l
h
N
;
= 0,1,...,i M
;
= 0,1,...,j 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:
1 1
= , =1,2,..., 1
j j j j
Y CY Y F j N
0 0
= ; =
N N
Y F Y F
1, 2, 1,
= ( ; ;...; )T
j j j M j
Y y y y
(1.21)
0 1,0 2,0 1,0
= ( ; ;...; )T
M
F g g g
1, 2, 1,
= ( ; ;...; )T
N N N M N
F g g g
Ma trận C có dạng
C=
2( 1) 0 ... 0 0 0
2( 1) ... 0 0 0
0 2( 1) ... 0 0 0
0 0 0 ... 2( 1) 0
0 0 0 ... 2( 1)
0 0 0 ... 0 2( 1)
r r
r r r
r r
r r
r r r
r r
2
2 1, 0,
2
2 2,
2
2 2,
2
2 1, ,
j j
j
j
M j
M j M j
h rg
h
F
h
h rg
Với 2
2
2
1
=
h
r
h
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
17
Cho miền
1 2 1 1 2 2= = ( , );0 < < ;0 < <x x x x l x l
Xét bài toán biên hỗn hợp
= ( );u x x
= ( )u g x
với
1
x
(1.22)
2
= ( )
u
x
x
với
2
x
Trong đó:
2 2 2
1 2
( ); ( ); ( )L g L L
1 1 1 1 1 2 2 2= = ( ,0);0 = ( , );0x x x l x l x x l 2 2 2= (0, );0x x x l
2 1 2 1 1= = ( , );0x x l x l
Tương tự, ta đưa bài toán sai phân về hệ phương trình vec tơ 3 điểm
0 0
=Y F
1 1
= 1 1
j j j j
Y CY Y F j N
(1.23)
1
2 = =
N N N
Y CY F j N
Trong đó:
0 1,0 2,0 1,0
= ( , ,..., )T
M
F y y y
;
1, 2, 1,
= ( , ,..., ) ; =1,...,T
j j j M j
Y y y y j N
C=
2( 1) 0 ... 0 0 0
2( 1) ... 0 0 0
2( 1) ... 0 0 0
0 0 0 ... 2( 1) 0
0 0 0 ... 2( 1)
0 0 0 ... 0 2( 1)
r r
r r r
r r
r r
r r r
r r
2
2 1, 0,
2
2 2,
2
2 2,
2
2 1, ,
j j
j
j
M j
M j M j
h rg
h
F
h
h rg
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
18
2
2 1, 2 1, 0,
2
2 2, 2 2,
2
2 2, 2 2,
2
2 1, 2 1, ,
2
2
2
2
N N N
N N
N
M N M N
M N M N M N
h h rg
h h
F
h h
h h rg
1.4 Phƣơng pháp lặp và các sơ đồ lặp cơ bản
1.4.1 Không gian năng lượng
Giả sử
H
là không gian Hilbert thực với tích vô hướng
(,)
và chuẩn
.
.
A
là toán tử đối xứng, xác định dương trong
H
, tức là miền xác định
( )D A
trù mật trong
H
,
( , ) = ( , ), , ( )Au v u Av u v D A
và tồn tại hằng số dương
sao cho
2
( , ) , ( ).Au u u u D A
Trong miền xác định
( )D A
, xét phiếm hàm song tuyến tính
( , )Au v
mà
ta kí hiệu là
( , ) = [ , ]Au v u v
.
Ta thấy, phiếm hàm
[ , ]u v
trong
( )D A
thỏa mãn mọi tiên đề của tích vô
hướng trong không gian Hilbert trừu tượng nói chung. Thật vậy, ta có
[ , ] = ( , ) = ( , ) = ( , ) = [ , ],u v Au v u Av Av u v u
1 1 2 2 1 1 2 2 1 1 2 2 1 1 2 2
[ , ] = ( ( ), ) = ( , ) ( , ) [ , ] [ , ],u u v A u u v Au v Au v u v u v
[ , ] = ( , ) 0,[ , ] = ( , ) = 0u u Au u u u Au u
khi và chỉ khi
0u
.
Do đó, đại lượng
[ , ]u u
thỏa mãn các tính chất của một chuẩn. Ta kí
hiệu chuẩn đó là
.
.
2
= [ , ] = ( , ).u u u Au u
(1.24)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
19
Bây giờ ta xây dựng một không gian tuyến tính định chuẩn
A
h
như
sau:
Các phần tử của
A
h
trùng với các phần tử của
( )D A
và các phép toán
cộng hai phần tử, nhân một số với một phần tử trong
A
h
được định
nghĩa trùng với các phép toán trong
H
.
Chuẩn của các phần tử trong
A
h
được định nghĩa bởi (1.21).
Không gian
A
h
được định nghĩa như vậy có thể là một không gian
không đủ. Trong trường hợp này, ta làm đủ không gian
A
h
bằng phương pháp
bổ sung không gian Metric để được không gian đủ
A
H
. Không gian
A
H
này
được gọi là không gian năng lượng của toán tử
A
.
Như vậy,
A
H
gồm những phần tử cũ thuộc
( )D A
và những phần tử
thu được sau phép bổ sung. Chuẩn của
A
u H
được xác định bởi
2 2
= lim nA
n
u u
trong đó
{ }
n
u
là dãy cơ bản (theo metric
.
trong
A
h
) các phần tử thuộc
( )D A
xác định
u
.
Tích vô hướng của hai phần tử
,
A
u v H
được xác định bởi
[ , ] = [ , ],limA n n
n
u v u v
trong đó
{ },{ }
n n
u v
là dãy cơ bản các phần tử thuộc
( )D A
xác định
,u v
.
Không gian
A
H
với tích vô hướng trên là không gian Hilbert.
Ta thường nói gọn là: Không gian năng lượng
A
H
là không gian
Hilbert thu được bằng cách bổ sung tập
( )D A
cho thành không gian đủ theo
tích vô hướng
( , )Au v
.
1.4.2 Phương pháp lặp giải phương trình toán tử
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
20
Lược đồ lặp hai lớp
Xét bài toán
= ,Au f
(1.25)
trong đó
:A H H
là toán tử tuyến tính trong không gian Hilbert thực
N
chiều
H
với tích vô hướng
(,)
và chuẩn
= ( , )y y y
.
Giả sử
A
là toán tử đối xứng, xác định dương,
f H
là vectơ tùy ý.
Trong mỗi phương pháp lặp, xuất phát từ
0
y
bất kỳ thuộc
H
, người ta đưa ra
cách xác định nghiệm xấp xỉ
1 2
, ,..., ,...
k
y y y
của phương trình (1.25). Các xấp
xỉ như vậy được biết như là các giá trị lặp với chỉ số lặp
=1,2,...k
Bản chất
của những phương pháp này là giá trị
1k
y
có thể được tính thông qua các giá
trị lặp trước:
1
, ,...
k k
y y
.
Phương pháp lặp được gọi là phương pháp lặp một bước hoặc hai bước
nếu xấp xỉ
1k
y
có thể tính được thông qua một hoặc hai giá trị lặp trước đó.
Phương pháp lặp một bước có thể được viết như sau:
1
= ( = 0,1,2...)
k k k k
B Y Cy F k
(1.26)
ở đây
k
B
và
k
C
là toán tử tuyến tính từ không gian
H
vào không gian
H
nói
chung phụ thuộc vào chỉ số lặp
k
,
k
F H
là hàm biết trước phụ thuộc
k
và
k
y
là giá trị lặp thứ
k
. Giả thiết rằng
1
k
B
tồn tại với mọi
k
.
Một đòi hỏi tự nhiên là nghiệm chính xác
u
của phương trình (1.25)
không phụ thuộc vào
k
, thoả mãn phương trình (1.26).
( ) =
k k k
B C u F
Nhưng điều đó chỉ xảy ra nếu
1( ) =
k k k
B C A f F
, kéo theo
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
21
+ Toán tử ngược
1( )
k k
B C
tồn tại.
+
1= ( )
k k k
f A B C F
Điều này được thoả mãn nếu
1
1
( ) =
k k k
B C A
,
1
=
k k
F f
,
= 0,1,2,...k
ở đây
> 0
k
là tham số.
Dạng chính tắc của lược đồ lặp hai lớp là
1
1
= , = 0,1,2,...k k
k k
k
y y
B Ay f k
(1.27)
trong đó
1k
là các tham số lặp.
Giả thiết
k
B
là toán tử tuyến tính từ
H
vào
H
, tồn tại toán tử ngược
1
k
B
. Do đó từ (1.27) ta có
1
1 1
= ( )
k k k k k
y y B Ay f
(1.28)
hoặc dạng tương tự
1
1 1 1
= = ,
k k k k k k k k
y y B r y
trong đó
=
k k
r Ay f
là độ không khớp và
1=
k k k
B r
là phần hiệu chỉnh.
Với
k
y
đã biết, giá trị của
1k
y
có thể tính được từ (1.28). Biết
0
y
ta
xác định được
1 2
, ,...y y
Tất nhiên, nó chỉ có nghĩa khi phép lặp hội tụ, tức là
0, .
k
y u k
Thông thường, nghiệm được tìm với độ chính xác
(liên quan đến độ
chính xác
0
)k
y u
y u
, có nghĩa là sự tính toán được dừng khi
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
22
.
k k
y u y u
(1.29)
Vì véctơ
u
chưa biết nên ta thay điều kiện (1.29) bằng bất đẳng thức
cho độ không khớp
0
.
k
Ay f Ay f
(1.30)
Ta chấp nhận điều kiện dừng
0
.
k D D
y u y u
(1.31)
Trong đó
D
là toán tử đối xứng, xác định dương. Với 2=D A , từ
(1.31) ta suy ra được (1.30).
Bây giờ chúng ta xét phương trình liên quan đến phần dư
= .
k k
z y u
Từ
=Au f
ta có
1
1
= 0, = 0,1,2,...k k
k k
k
z z
B Az k
(1.32)
trong đó
0
z H
được biết.
Từ (1.32) ta thấy
1
1 1 1 1
= , = ,
k k k k k k
z S z S E B A
trong đó
1k
S
là toán tử chuyển tiếp từ lớp thứ
k
tới lớp thứ
1k
. Với
= 1k n
ta có
0 1 2 1
= , = ... .
n n n n n
z T z T S S S S
Ta có đánh giá
0 0
.
n n nD D D D
z T z T z
hay
0
. ; =
n n n nD D D
z q z q T
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
23
Từ đó ta suy ra điều kiện dừng là
n
q
. Từ đây dẫn đến vấn đề về sự
hội tụ của phép lặp theo ước lượng chuẩn của toán tử
n
T
.
Lược đồ (1.27) cho ta xấp xỉ nghiệm
u
của phương trình
=Au f
với
bất kỳ toán tử
n
B
và cách chọn tham số
1k
. Nhưng
n
q
phụ thuộc vào cả
{ }
n
B
và
1
{ }
k
. Vấn đề ở đây là nên chọn
{ }
k
B
và
1
{ }
k
như thế nào để cực tiểu
chuẩn
=
n nD
q
của toán tử
n
T
của lược đồ (1.27) và để cực tiểu toàn bộ số
phép toán số học cần để phục hồi giá trị
1k
y
từ phương trình
1 1
; ( )
k k k k k k k k
B y F F B y Ay f
với
k
y
đã biết.
Đặt
( )Q
là tổng số phép toán số học cần thiết để đạt được nghiệm
của phương trình (1.25) với độ chính xác
0
cho trước. Thành phần
k
B
và
k
T
nên được chọn để cực tiểu lượng
( )Q
. Nếu độ chính xác qui định có thể
đạt được với số phép lặp cực tiểu
( )n n
, thì
( )
k
k = 1
( ) = Q = Q
n
n
Q n
ở đây
k
Q
là số phép toán cần thiết trong phép lặp thứ
k
. Do vậy vấn đề cực
tiểu
( )Q
qui về vấn đề cực tiểu
( )n
và số
k
Q
phụ thuộc vào
k
B
.
+ Nếu
=
k
B E
thì lược đồ lặp (1.27) được gọi là lược đồ lặp hiển
1
1
= , = 0,1,2,...k k
k
k
y y
Ay f k
(1.33)
Trong trường hợp
=
k
const
là hằng số, lược đồ (1.33) còn được gọi
là lược đồ lặp đơn giản.
+ Nếu
k
B E
thì lược đồ lặp (1.27) được gọi là lược đồ ẩn.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
24
Lược đồ dừng, định lý cơ bản về sự hội tụ của phép lặp
Lược đồ lặp (1.27) với toán tử
=
k
B B
, tham số
1
=
k
không đổi
( = 0,1,2,...)k
còn được gọi là lược đồ lặp dừ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,1i
, 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,1i
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
0k
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
0k
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
0k
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,1d
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,1k 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 tính toán ta phải đầu tư
vào mỗi bước tính toán một khối lượng gấp đôi các trường hợp khác. Tuy
nhiên trong trường hợp này, tại mỗi bước tính toán các giá trị trên biên có thể
thực hiện bởi thủ tục lấy trung bình hoá trên biên.
Thuật toán mới có thể được định nghĩa như sau: Cho trước các giá trị
Miuki ,...,1, xác định với mỗi Mi ,..,1
,),()1()( ij
k
j
k
i
av
i xuu
trong đó
là tham số lấy trung bình và
ij
là phần biên của
i
phân chia
i
và
j
, rõ ràng
)( ki
av
i u
trên
i
. Tiến hành giải M bài toán kiểu
.,...,2,1,,)(
,,
)2/1
2/1
Mixu
xfLu
i
av
i
k
i
i
k
i
và tính các giá trị
)( 2/1 kiu
từ đó xác định các giá trị trung bình
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
45
,),()1()( 2/12/1 ij
k
j
k
i
av
i xuu
trong đó
là tham số lấy trung bình, đặt
i
k
i
av
i xu ),(
2/1
, Tiếp
theo giải M bài toán con thuộc loại
.,...,2,1,,)(
,,
)1
1
Mixu
xfLu
i
av
i
k
i
i
k
i
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
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 phức tạp trong các mô hình thực tế, trong phần này luận văn 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. Các kết quả đã được công bố
trong các công trình [6, 7].
Xét bài toán biên:
4,2
4,2
, ,
, ,( 1.. ),
, \ ,,( 1.. ).
i
i
u f x
u
x i n
n
u x i n
(3.4)
41
42
43
4,2 1l
4,2 l
4,2 1l
4,2 1n
1
1
2
2
3
3
…
.
2 1l
2 1l
2 l
2l
2 1l
2 1l
….
2 1n
2n
Hình 4
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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
46
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:
3.2.1. Hướng tiếp cận hiệu chỉnh đạo hàm
Chia 2n 1
i
i 1
bởi các biên phân chia
i( i 1..2n )
, (Hình 4).
Ký hiệu
2 1 2
2 2
2 1 2
2 2
, ,( 1,2,... )
i i
i i
i i
i i
u u
g g i n
n n
. Việc giải bài toán
(3.4) đượ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ẻ
( )
1 1
( )
( )1
1 1
1
( )
1 1 1
, ,
, ,
, \ ,
k
k
k
k
u f x
u
g x
n
u x
(3.5)
( )
2 1 2 1
( )
2 1 2 1 2 1 2
( )
( )2 1
2 2 2 2
2 1
( )
( )2 1
2 1 2 1
2 1
, ,
, \ ,
, ,
, ,
k
l l
k
l l l l
k
kl
l l
l
k
kl
l l
l
u f x
u x
u
g x
n
u
g x
n
3,...,n
(3.6)
( )
2 1 2 1
( )
( )2 1
2 2
2 1
( )
2 1 2 1 2
, ,
, ,
, \ ,
k
n n
k
kn
n n
n
k
n n n
u f x
u
g x
n
u x
(3.7)
Bƣớc 3: Tiến hành giải song song các bài toán trong các miền chẵn
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
47
( )
2 2
( ) ( )
2 2 1 2 1
( )
2
4,2
2
( ) ( )
2 2 1 2 1
( )
2 2 4,2 2 2 1
, ,
, ,
, ,
, ,
, \ .
k
l l
k k
l l l
k
l
l
l
k k
l l l
k
l l l l l
u f x
u u x
u
x
n
u u x
u x
1,2,...,n
(3.8)
Bƣớc 4: Hiệu chỉnh
( )
( 1) ( ) 2
2 1 2 1 2 1
2
( )
( 1) ( ) 2
2 2 2
2
(1 ) , ,
(1 ) , .
k
k k l
l l l
l
k
k k l
l l l
l
u
g g x
n
u
g g x
n
1,2,...,n
(3.9)
Nhận xét: Trong mô hình tính toán, 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 được thực hiện theo nguyên tắc tính
toán song song. Khi thu được kết quả của các bài toán trong miền lẻ, việc giải
các bài toán trong miền chẵn cũng sẽ được thực hiện bằng 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ơ đồ (3.9).
Xuất phát từ các kết quả lý thuyết trong [2, 3, 4] có thể chứng minh các sơ đồ
hội tụ.
3.2.2. Hướng tiếp cận hiệu chỉnh hàm
Ký hiệu
1,2,...,2
ii i
g u i n
. Việc giải bài toán (3.4) được thực hiện
bởi sơ đồ lặp sau đây.
Bƣớc 1: Xuất phát
(0) 0, 1,2,...,2
i
g i n
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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
48
( )
2 2
( ) ( )
2 2 1 2 1
( )
2
4,2
2
( ) ( )
2 2 1 2 1
( )
2 2 4,2 2 2 1
, ,
, ,
, ,
, ,
, \ .
k
l l
k k
l l l
k
l
l
l
k k
l l l
k
l l l l l
u f x
u g x
u
x
n
u g x
u x
1,2,...,l n
(3.10)
Bƣớc 3: Tiến hành giải song song các bài toán trên các miền lẻ
( )
1 1
( ) ( )
1 2
1
1 2
( )
1 1 1
, ,
, ,
, \ ,
k
k k
k
u f x
u u
x
n n
u x
(3.11)
( )
2 1 2 1
( )
2 1 2 1 2 1 2
( ) ( )
2 1 2 2
2 2
2 1 2 2
( ) ( )
2 1 2
2 1
2 1 2
, ,
, \ ,
, ,
, ,
k
l l
k
l l l l
k k
l l
l
l l
k k
l l
l
l l
u f x
u x
u u
x
n n
u u
x
n n
(3.12)
( )
2 1 2 1
( ) ( )
2 1 2
2
2 1 2
( )
2 1 2 1 2
, ,
, ,
, \ ,
k
n n
k k
n n
n
n n
k
n n n
u f x
u u
x
n n
u x
(3.13)
Bƣớc 4: Hiệu chỉnh
( 1) ( ) ( )
2 1 2 1 2 1 2 1
( 1) ( ) ( )
2 2 2 1 2
(1 ) , ,
(1 ) ,
k k k
k k k
g g u x
g g u x
1,2,...,n
(3.14)
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 (3.14), xuất phát từ các kết quả lý thuyết trong [22, 23] cũng có thể
chứng minh sự hội tụ của sơ đồ lặp (3.14).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
49
Như vậy, hai mô hình tính toán song song (3.5)-(3.9) và (3.10)-(3.14)
cùng giải quyết bài toán (3.4). Đâ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.3. Các kết quả thực nghiệm
Để 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
[5]. 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)
axm 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.
Bảng 1:
1
1 2 2 2 1
( , ) log( 5) sin( )log( 6)xu x x e x x x
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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
50
B¶ng 2:
1 23 3
1 2 1 2 2 1
( , ) x xu 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 2
( , ) sinx sinxu x 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
Nhận xét
Hai mô hình tính toán song song 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 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
0,5
opt
. 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
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
51
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 các bài toán phức tạp hơn nữa.
3.4. Ứng dụng mô hình song song giải bài toán cơ học
Trên cơ sở mô hình tính toán song song đã đề xuất, trong phần này
chúng ta xét một mô hình mô tả các quá trình trong các thiết bị bán dẫn sử
dụng các mô hình thủy động lực học, mô hình này được các tác giả
A.M.Blokhin, A.C. Ibragrimova, N.I. Crasnhicova đưa ra. Về mặt toán học,
đây chính là mô hình xác định hàm thế năng trong trường hợp Transitor bán
dẫn kiểu điện tử đối với các điều kiện ràng buộc rất phức tạp thỏa mãn
phương trình Poisson đối với hàm thế năng. Mô hình toán học như sau:
Xét bài toán
1 2
( , )u f x x
(3.15)
với các điều kiện biên
2 1
2
1 2
1
2 1
2 1
2 1
2 1 1
2
0, 0,0 6 ,
0, 0, 6 , 0 2 ,
0, 2 ,0 ,
, 2 ,2 4 ,
, 2 ,5 6 ,
0, 2 , 2 4 5 .
u
x x a
x
u
x a x a
x
u x a x a
u g const x a a x a
u b const x a a x a
u
x a a x a và a x a
x
(3.16)
trong đó
1 2
,x x
là các biến không gian,
1 2
( , )f x x
là hàm vế phải đã biết.
0a
là hằng số. Không giảm tổng quát chúng ta cho rằng
/ 6a
. (Hình 5)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
52
Đây là một mô hình bài toán vật lý thực tế với hệ điều kiện biên hỗn
hợp mạnh. Bằng phương pháp tìm nghiệm dưới dạng tổng của các hàm mẫu,
các tác giả đã đưa ra phương pháp xác định nghiệm xấp xỉ của bài toán trên và
đồng thời chứng minh tính đúng đắn của phương pháp đã đưa ra. Tuy nhiên
trong trường hợp khi điều kiện biên là tùy ý thì việc xác định dạng của các
hàm mẫu sẽ gặp khó khăn. Theo chúng tôi bài toán trên trong trường hợp tổng
quát có thể giải quyết được dựa trên phương pháp thiết kế thuật toán song
song dựa trên tư tưởng chia miền.
Trên cơ sở của phương pháp chia miền đã đề xuất cùng các mô hình
tính toán song song, đối với mô hình bài toán vật lý bán dẫn trên, chúng tôi sẽ
đề xuất các phương pháp giải bài toán bằng việc đưa ra thuật toán song song
trên tư tưởng chia miền đối với bài toán trong trường hợp tổng quát sau:
Xét bài toán tổng quát
,u f x
. (3.17)
với các điều kiện biên
H×nh 5
u=0
uy=0
u=g
uy=0
u=b
ux=0 ux=0
uy=0
a
2a
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
53
2 1
2
1 2
1
2 1
2 1
2 1
2 1 1
2
, 0,0 6 ,
, 0, 6 , 0 2 ,
, 2 ,0 ,
, 2 ,2 4 ,
, 2 ,5 6 ,
, 2 , 2 4 5 .
u
x x a
x
u
x a x a
x
u g x a x a
u g const x a a x a
u g const x a a x a
u
x a a x a và a x a
x
(3.18)
trong đó
, , g
là các hàm số cho trước (Hình 6).
3.4.1 Sơ đồ song song theo hƣớng hiệu chỉnh đạo hàm
Sử dụng phương pháp chia miền
1 2 3 4 5
bằng các biên
1 2 3 4, , ,
, kí hiệu
( 1..5),
ii
u u i
1 2 3 4
3 3 51
1 2 3 4
1 1 1 1
, , , .
u u uu
x x x x
Việc tìm nghiệm của bài toán được thực hiện bằng thuật toán song
song như sau:
Xuất phát từ
(0) (0) (0) (0)
1 2 3 4
, với mọi k=0,1,2 thực hiện thuật toán
Bƣớc 1: Giải song song các bài toán trong các miền
1 3 5, ,
H×nh 6
0 a
b
Ω1 Ω2 Ω3 Ω4 Ω5
Г1 Г2 Г3 Г4
Г6 Г7 Г8 Г9 Г10
Г11 Г12 Г13 Г14 Г15
Г5 Г0
x2
x1
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
54
( )
1 1
( )
1
1 2
1
( )
( )1
1 1 2
1
( )
1
1 2
2
( )
1 1 2
, ,
, 0,0 ,
, ,0 ,
, 0 , 0,
, 0 , ,
k
k
k
k
k
k
u f x
u
x x b
x
u
x a x b
x
u
x a x
x
u g x a x b
(3.19)
( )
3 3
( )
( )3
2 1 2
1
( )
( )3
3 1 2
1
( )
3
1 2
2
( )
3 1 2
, ,
, 2 ,0 ,
, 4 ,0 ,
, 2 4 , 0,
, 2 4 , ,
k
k
k
k
k
k
k
u f x
u
x a x b
x
u
x a x b
x
u
a x a x
x
u g a x a x b
(3.20)
( )
5 5
( )
( )5
4 1 2
1
( )
5
1 2
1
( )
5
1 2
2
( )
5 1 2
, ,
, 5 ,0 ,
, 6 ,0 ,
, 5 6 , 0,
, 5 6 , ,
k
k
k
k
k
k
u f x
u
x a x b
x
u
x a x b
x
u
a x a x
x
u g a x a x b
(3.21)
Bƣớc 2: Giải song song các bài toán trong các miền
2 4,
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
55
( )
2 2
( ) ( )
2 1 1 2
( ) ( )
2 3 1 2
( )
2
1 2
2
( )
2
1 2
2
, ,
, ,0 ,
, 2 ,0 ,
, 2 , 0,
, 2 , ,
k
k k
k k
k
k
u f x
u u x a x b
u u x a x b
u
a x a x
x
u
a x a x b
x
(3.22)
( )
4 4
( ) ( )
4 3 1 2
( ) ( )
4 5 1 2
( )
4
1 2
2
( )
4
1 2
2
, ,
, 4 ,0 ,
, 5 ,0 ,
, 4 5 , 0,
, 4 5 , ,
k
k k
k k
k
k
u f x
u u x a x b
u u x a x b
u
a x a x
x
u
a x a x b
x
(3.23)
Bƣớc 3: Hiệu chỉnh các giá trị đạo hàm trên biên chung
( )
( 1) ( ) 2
1 1 1 2 1
1
( )
( 1) ( ) 2
2 2 1 2 2
1
( )
( 1) ( ) 4
3 3 1 2 3
1
( )
( 1) ( ) 4
4 4 1 2 4
1
(1 ) , ( , ) ,
(1 ) , ( , ) ,
(1 ) , ( , ) ,
(1 ) , ( , ) ,
k
k k
k
k k
k
k k
k
k k
u
x x
x
u
x x
x
u
x x
x
u
x x
x
(3.24)
trong đó
là tham số lặp cần lựa chọn. Sự hội tụ của phương pháp song song
trên tư tưởng chia miền hoàn toàn phụ thuộc vào sự hội tụ của sơ đồ lặp (3.24)
Nghiên cứu sự hội tụ: các dãy lặp (3.24) được viết thành
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
56
)(
1
4
1
4
1
2
1
2
)(
4
3
2
1
)1(
4
3
2
1
4
3
2
1
)1(
k
kk
x
u
x
u
x
u
x
u
(3.25)
Kí hiệu
1
2
3
4
là vectơ các giá trị đạo hàm trên biên phân chia.
Đưa vào toán tử
B
xác định như sau:
4
3
2
1
1
4
1
4
1
2
1
2
x
u
x
u
x
u
x
u
B
(3.26)
Trong đó
2 4
,u u
được xác định từ các bài toán
1 1 2 1
1 1 2 6
1
1 2 0
1
1
1 2 11
2
1
1 1 2 1
2
0, ( , ) ,
0, ( , ) ,
0, ( , ) ,
0, ( , ) ,
, ( , ) .
u x x
u x x
u
x x
x
u
x x
x
u
x x
x
3 1 2 2
3 1 2 8
3
1 2 13
2
3
2 1 2 2
1
3
3 1 2 3
1
0, ( , ) ,
0 ( , ) ,
0, ( , ) ,
, ( , ) ,
, ( , ) .
u x x
u x x
u
x x
x
u
x x
x
u
x x
x
(3.27)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
57
5 1 2 5
5 1 2 10
5
4 1 2 4
1
5
1 2 5
1
1
1 2 15
2
0, ( , ) ,
0, ( , ) ,
, ( , ) ,
0, ( , ) ,
0, ( , ) .
u x x
u x x
u
x x
x
u
x x
x
u
x x
x
(3.28)
2 1 2 2
2 1 1 2 1
2 3 1 2 2
2
1 2 7 12
2
0, ( , ) ,
, ( , ) ,
, ( , ) ,
0, ( , ) ,
u x x
u u x x
u u x x
u
x x
x
4 1 2 4
4 3 1 2 3
4 5 1 2 4
4
1 2 9 14
2
0, ( , ) ,
, ( , ) ,
, ( , ) ,
0, ( , ) ,
u x x
u u x x
u u x x
u
x x
x
(3.29)
Khi đó sơ đồ lặp (3.25) được viết dưới dạng sơ đồ lặp
( 1) ( )
( )
k k
kI B F
(3.30)
Sử dụng lý thuyết toán tử trên các không gian hàm thích hợp, có thể
chứng minh rằng
B
là toán tử tuyến tính, đối xứng xác định dương. Khi đó
theo lý thuyết tổng quát của các sơ đồ lặp khẳng định sơ đồ lặp (3.30) hội tụ,
điều đó chứng tỏ thuật toán song song dựa trên tư tưởng chia miền đề xuất
giải bài toán trên là hội tụ.
3.4.2 Sơ đồ song song theo hƣớng hiệu chỉnh hàm
Sử dụng phương pháp chia miền
1 2 3 4 5
bằng các
biên
1 2 3 4, , ,
, kí hiệu
( 1..5),
ii
u u i 1 2 3 41 2 2 2 3 4 4 4, , , .u u u u
Việc tìm nghiệm của bài toán được thực hiện bằng thuật toán song
song như sau:
Xuất phát từ
(0) (0) (0) (0)
1 2 3 4
, với mọi k=0,1,2 thực hiện thuật toán
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
58
Bƣớc 1: Giải song song các bài toán trong các miền
2 4,
( )
2 2
( ) ( )
2 1 1 2
( ) ( )
2 2 1 2
( )
2
1 2
2
( )
2
1 2
2
, ,
, ,0 ,
, 2 ,0 ,
, 2 , 0,
, 2 , ,
k
k k
k k
k
k
u f x
u x a x b
u x a x b
u
a x a x
x
u
a x a x b
x
(3.31)
( )
4 4
( ) ( )
4 3 1 2
( ) ( )
4 4 1 2
( )
4
1 2
2
( )
4
1 2
2
, ,
, 4 ,0 ,
, 5 ,0 ,
, 4 5 , 0,
, 4 5 , ,
k
k k
k k
k
k
u f x
u x a x b
u x a x b
u
a x a x
x
u
a x a x b
x
(3.32)
Bƣớc 2: Giải song song các bài toán trong các miền
1 3 5, ,
( )
1 1
( )
1
1 2
1
( ) ( )
1 2
1 2
1 1
( )
1
1 2
2
( )
1 1 2
, ,
, 0,0 ,
, ,0 ,
, 0 , 0,
, 0 , ,
k
k
k k
k
k
u f x
u
x x b
x
u u
x a x b
x x
u
x a x
x
u g x a x b
(3.33)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
59
( )
3 3
( ) ( )
3 2
1 2
1 1
( ) ( )
3 4
1 2
1 1
( )
3
1 2
2
( )
3 1 2
, ,
, 2 ,0 ,
, 4 ,0 ,
, 2 4 , 0,
, 2 4 , ,
k
k k
k k
k
k
u f x
u u
x a x b
x x
u u
x a x b
x x
u
a x a x
x
u g a x a x b
(3.34)
( )
5 5
( ) ( )
5 4
1 2
1 1
( )
5
1 2
1
( )
5
1 2
2
( )
5 1 2
, ,
, 5 ,0 ,
, 6 ,0 ,
, 5 6 , 0,
, 5 6 , ,
k
k k
k
k
k
u f x
u u
x a x b
x x
u
x a x b
x
u
a x a x
x
u g a x a x b
(3.35)
Bƣớc 3: Hiệu chỉnh các giá trị đạo hàm trên biên chung
( 1) ( ) ( )
1 1 1 1 2 1
( 1) ( ) ( )
2 2 3 1 2 2
( 1) ( ) ( )
3 3 3 1 2 3
( 1) ( ) ( )
4 4 5 1 2 4
(1 ) , ( , ) ,
(1 ) , ( , ) ,
(1 ) , ( , ) ,
(1 ) , ( , ) ,
k k k
k k k
k k k
k k k
u x x
u x x
u x x
u x x
(3.36)
trong đó
là tham số lặp cần lựa chọn. Sự hội tụ của phương pháp song song
trên tư tưởng chia miền hoàn toàn phụ thuộc vào sự hội tụ của sơ đồ lặp
(3.36).
Xuất phát từ lý thuyết toán tử và kết quả chứng minh sự hội tụ của sơ
đồ lặp chia miền theo hướng hiệu chỉnh hàm của Saito-Fujita, chúng ta cũng
có thể chứng minh các sơ đồ lặp trên là hội tụ.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
60
3.4.3 Các kết quả thực nghiệm
Để kiểm tra sự hội tụ của thuật toán, chúng tôi cho trước nghiệm đúng
*u
của bài toán và từ đó xác định các giá trị điều kiên biên Dirichlet hoặc
Neumann biên trên tất cả các đoạn biên của bài toán đang xét. Sai số
*
ij ijerr=max( u )u
lấy trên mọi điểm lưới trong đó
iju
là nghiệm xấp xỉ,
*
iju
là
nghiệm đúng tại các điểm lưới
( , )i j
. Trong các kết quả thực nghiệm sau đây,
chúng tôi sẽ đưa ra các số liệu thực nghiệm trong việc lựa chọn tham số lặp,
số bước lặp và sai số tương ứng trong trường hợp cho trước nghiệm đúng của
bài toán. Các kết quả được lập trình đối với thuật toán song song theo hướng
hiệu chỉnh đạo hàm, việc lập trình đối với thuật toán song song theo hướng
hiệu chỉnh hàm là hoàn toàn tương tự.
Tham số
lặp
Số bước
lặp
Sai số
0.1
0.2
0.3
0.4
0.5
0.6
0.7
40
27
17
12
9
16
40
5.10
-4
9.10
-5
9.10
-5
9.10
-5
8.10
-5
8.10
-5
2.10
-4
Bảng 4. Số liệu thực nghiệm và đồ thị đối với hàm nghiệm đúng
*
1 2 1 2( , ) sinx sinx , / 6, / 3.u x x a b
Tham số
lặp
Số bước
lặp
Sai số
0.1
0.2
0.3
0.4
0.5
0.6
0.7
40
40
22
16
12
30
40
0.05
6.10
-4
6.10
-4
6.10
-4
6.10
-4
8.10
-4
0.05
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
61
Bảng 5. Số liệu thực nghiệm và đồ thị đối với hàm nghiệm đúng
1 2* 3 3
1 2 1 2 2 1( , ) x x , / 6, / 3.
x xu x x x e x e a b
Tham số
lặp
Số bước
lặp
Sai số
0.1
0.2
0.3
0.4
0.5
0.6
0.7
40
30
18
14
10
17
40
0.05
0.002
0.001
0.002
0.002
0.002
0.002
Bảng 6. Số liệu thực nghiệm và đồ thị đối với hàm nghiệm đúng
1*
1 2 1 2 1( , ) log(x 5) sinx log( 6), / 6, / 3.
x
u x x e x a b
Tham số
lặp
Số bước
lặp
Sai số
0.1
0.2
0.3
0.4
0.5
0.6
0.7
40
34
22
15
12
20
40
0.0047
9.10
-5
6.10
-5
8.10
-5
4.10
-5
7.10
-5
0.0025
Bảng 7. Số liệu thực nghiệm và đồ thị đối với hàm nghiệm đúng
* 2 2
1 2 1( , ) x x , / 6, / 3.u x x a b
Nhận xét: Thuật toán trên luôn luôn hội tụ với vế phải của phương
trình và điều kiện biên trên các đoạn biên được chọn một cách tùy ý, thuật
toán sẽ dừng khi dãy lặp thỏa mãn điều kiện dừng lặp là sai số giữa 2 bước
lặp liên tiếp nhỏ hơn epsilon cho trước. Trong trường hợp vế phải và điều
kiện biên được chọn tùy ý theo các công thức:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
62
1
2
1
2 2 1
4 4
1 2
-10
sin( )
os(x )
log( 5) sin( ) log( 6)
epxilon=10
x
x
c
g e x x x
f x x
Khi thực hiện thuật toán trên, sau 31 lần lặp ta thu được nghiệm xấp xỉ mô
tả bởi đồ thị trong hình 7.
Hình 7: Đồ thị nghiệm xấp xỉ - số buớc lặp count=31
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
63
NHẬN XÉT KẾT LUẬN
Nội dung của luận văn đã trình bày các kết quả nghiên cứu về mô hình
tính toán song song trên cơ sở của phương pháp chia miền, một lĩnh vực đang
được thế giới quan tâm và phát triển.
Kết quả chính của luận văn gồm có:
1. Nghiên cứu lý thuyết chung về cơ sở toán học của phương pháp
chia miền, các sơ đồ lặp cơ sở và một số thuật toán chia miền của các tác giả
trên thế giới và trong nước.
2. Đề xuất các mô hình tính toán song song trên hai hướng hiệu chỉnh
hàm và đạo hàm giải mô hình bài toán biên gián đoạn mạnh cực kì phức tạp,
tiến hành cài đặt thử nghiệm mô hình tính toán trên máy tính điện tử.
3. Áp dụng mô hình tính toán song song giải quyết một bài toán mô
phỏng quá trình hoạt động của một hệ vật lý bán dẫn trong thực tế. Tiến hành
cài đặt thử nghiệm trên máy tính điện tử. Các kết quả thực nghiệm tính toán
đã chứng tỏ mô hình tính toán song song đề xuất là đúng đắn.
Các kết quả của đề tài đã khẳng định tính ưu việt của phương pháp
chia miền khi giải quyết các lớp bài toán elliptic cấp hai khi miền hình học là
rất phức tạp và điều kiện biên phức tạp. Đề tài mở ra một số hướng nghiên
cứu về phương pháp chia miền đối với các lớp phương trình bậc cao, các lớp
phương trình parabolic và hyperbolic, ứng dụng phương pháp chia miền khảo
sát các bài toán cơ học và vật lý với điều kiện và môi trường rất phức tạp.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
64
DANH MỤC CÔNG TRÌNH ĐÃ CÔNG BỐ
LIÊN QUAN ĐẾN LUẬN VĂN
[1] Vũ Vinh Quang, Trương Hà Hải, Cao Thị Anh Thư, 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 và Công nghệ Đại học Thái Nguyên, T.2(50):52-57, 2009.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
65
TÀI LIỆU THAM KHẢO
Tiếng Việt
[1] Đặng Quang á, Vũ Vinh Quang (2006), “Nghiên cứu thực nghiệm một
phương pháp chia miền giải các bài toán với điều kiện biên hỗn hợp trong
miền hình học phức tạp”, Tạp chí Tin học và điều khiển học, T.21, tr.216-229.
[2] Đặ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, tr.307-
318.
[3] Đặng Quang á, Vũ Vinh Quang (2006), “Một số kết quả nghiên cứu về
phương pháp chia miền giải phương trình elliptic và phương trình song điều
hòa”, Hội nghị khoa học Kỷ niệm 30 năm ngày thành lập Viện Công nghệ
Thông tin.
[4] Vũ Vinh Quang (2007), Phương pháp chia miền giải phương trình
elliptic cấp hai và phương trình song điều hòa trong miền hình học phức tạp,
Luận án Tiến sĩ Toán học, Viện Công nghệ thông tin, Hà Nội.
[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 tính toán giải các bài toá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, tr.247-256.
[6] Đặng Quang Á, Vũ Vinh Quang, Phương pháp song song giải một bài
toán biên hỗn hợp dựa trên chia miền, Hội thảo Quốc gia về Công nghệ
Thông tin và truyền thông, Huế 6/2008, 329-340, 2008.
[7] Vũ Vinh Quang, Trương Hà Hải, Cao Thị Anh Thư, 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 và Công nghệ Đại học Thái Nguyên, T.2(50):52-57, 2009.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
66
Tiếng Anh
[8] Arad M., Yosibash Z., Ben-Dor G. and Yakhot A. (2005), “Computing
Flux Intensity Factors by a Boundary Method for Elliptic Equation with
Singularities,” Preprint submitted to Elsevier Science, 14 October.
[9] Adams R. (1975), Shape Sobolev Spaces, Acad. Press, New York-
Sanfrancisco-London.
[10] Cioranescu D. and Donato P. (1999), An Introduction to
Homogennization, Lectures series in Mathematics and its Applications, V.17,
Oxford Univesity Press, Oxford.
[11] Diaz M.A., Herrera I. (2003), Indirect Method of Collocation for the
Biharmonic Equation, Fourtenth International Conference on Domain
Decomposition Methods, Editors: Ismael Herrera, David E. Keyes, Olof B.
Widlund, Robert Yates.
[12] Dang Quang A, Vu Vinh Quang, “A domaindecompositionmethod for
solving an elliptic boundary value problem”, Methods of Complex and
Clifford Analysis (Proceedings of 2004 International Conference on Applied
Mathematics), SAS Iternational Publication, Delhi, pp.309-319.
[13] Elliotis M., Georgiou G., Xenophontos C.(2005), Solution of the stick-
slip problem with the singular function boundary integral method, $5^{th}$
GRACM International Congress Computational Mechanics Limassol.
[14] Funaro D., Quarteroni A., Zanolli P.(1998), “An iterative procedure
with interface relaxation for domain decomposition method”, SIAM J.
Numer. Anal. 25(6), pp.1213-1236.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
67
[15] Gevarsio P. (2005), “Homogeneous and heterogeneous domain
decomposition methods for plate bending problem”, Comput. Methods Appl.
Mech. Engrg. 194, pp. 4321-4343.
[16] Marchuk G.I. (1982), Methods of Numerical Mathematics, Springer,
New York.
[17] Marchuk G.I. and Kuznetsov Yu, Matsokin (1986), “Fictitous domains
and domain decomposition method”, Soviet J. of Num. Anal. and Math.
Modelling, V. 1, No 1, pp.5-41.
[18] Poullikkas A., Karageorghis A., Georgiou G. (1998), “Methods of
fundamental solutions for harmonic and biharmonic boundary value
problems”, Computational Mechanics, (21), pp.416-423.
[19] Quarteroni A. and Valli A. (1999), Domain Decomposition Methods
for Partial Differential Equations, Clarendon Press. Oxford.
[20] Samarskij A.(2001), The theory of diffence schemes, New York:
Marcel Dekker.
[21] Samarskij A. and Nikolaev E. (1989), Numerical Methods for Grid
Equations, Vol. 2, Birkhauser, Basel.
[22] Saito N. and Fujita H. (2001), Operator Theoretical Analysis to
Domain Decomposition Methods, 12
th
Int. Conf. on Domain Decomposition
Methods, 63-70, .
[23] Saito N. and Fujita H. (2000), Remarks on Trace of H1-functions
defined in a Domain with corners, J. Math, Sci. Unv. Tokyo, (7), pp.325-345.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
68
PHẦN PHỤ LỤC
% Chuong trinh Quang_Thu_1 giai bai toan co hoc bang mo hinh tinh toan
% song song
% Truong hop mien hinh hoc phuc tap-chia SM mien
% Truong hop biet truoc nghiem dung
% phi la ham ve phai
% b1,b2,b3,b4: la cac gia tri tren bien trai,phai,duoi,tren
% u la nghiem bai toan
% Ngay lap 18/09/2008
clear all
clc
teta=0.5;
a=1;b=1;cc=0;
SM=21;%So mien chia
count=0;
epxilon=3*10^(-4);saiso=10;
n=6;
N=2^n;
M=N;
q1=1;q2=N+1;h1=a/M;h2=b/N;l1=a;l2=b;x10=0;x20=0;
%buoc lap - Gia tri ban dau eta=0;
for k=1:SM-1;
for j=0:N;
etak(k,j+1)=0;
end;
end;
for i=0:SM*M;
for j=0:N;
ud(i+1,j+1)=u(x10+i*h1,x20+j*h2);
w(i+1,j+1)=0;
end;
end;
thoigian=cputime;
while and(countepxilon);
count=count+1;
%Giai cac bai toan tren mien le
for k=1:2:SM;
p1=(k-1)*M+1;p2=k*M+1;
x10=(k-1)*a;x20=0;
% Gia tri ve phai
for i=0:M;
for j=0:N;
x1=x10+i*h1;
x2=x20+j*h2;
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
69
phi(i+1,j+1)=vp1(x1,x2,cc); % Ham ve phai
end;
end;
% Dieu kien tren canh trai va phai
for j=0:N;
x2=x20+j*h2;
if k==1
b1(j+1)=u(x10,x2);
else
b1(j+1)=etak(k-1,j+1);
end;
if k==SM
b2(j+1)=u(x10+l1,x2);
else
b2(j+1)=etak(k,j+1);
end;
end;
% Dieu kien tren canh duoi va tren
for i=0:M;
x1=x10+i*h1;
b3(i+1)=u(x1,x20);
b4(i+1)=u(x1,x20+l2);
end;
if k==1;
uu=u0100(phi,b1,b2,b3,b4,l1,l2,cc,x10,x20,M,N,n,p1,p2,q1,q2);
w(p1:p2,q1:q2)=uu(p1:p2,q1:q2);
else
if k==SM;
uu=u1000(phi,b1,b2,b3,b4,l1,l2,cc,x10,x20,M,N,n,p1,p2,q1,q2);
w(p1:p2,q1:q2)=uu(p1:p2,q1:q2);
else
uu=u1100(phi,b1,b2,b3,b4,l1,l2,cc,x10,x20,M,N,n,p1,p2,q1,q2);
w(p1:p2,q1:q2)=uu(p1:p2,q1:q2);
end;
end;
end;%Het vong lap mien le
%Giai cac bai toan tren mien chan
for k=2:2:SM-1;
p1=(k-1)*M+1;p2=k*M+1;
x10=(k-1)*a;x20=0;
% Gia tri ve phai
for i=0:M;
for j=0:N;
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
70
x1=x10+i*h1;
x2=x20+j*h2;
phi(i+1,j+1)=vp1(x1,x2,cc); % Ham ve phai
end;
end;
% Dieu kien tren canh trai va phai
for j=0:N;
b1(j+1)=w(p1,j+1);
b2(j+1)=w(p2,j+1);
end;
% Dieu kien tren canh duoi va tren
for i=0:M;
x1=x10+i*h1;
b3(i+1)=u(x1,x20);
b4(i+1)=dhy(x1,x20+l2);
end;
uu=u0001(phi,b1,b2,b3,b4,l1,l2,cc,x10,x20,M,N,n,p1,p2,q1,q2);
w(p1:p2,q1:q2)=uu(p1:p2,q1:q2);
end;%Het vong lap mien chan
% Hieu chinh gia tri etak(j) tren bien
for k=2:2:SM-1;
p1=(k-1)*M+1;p2=k*M+1;
x10=(k-1)*a;x20=0;
for j=0:N;
x2=x20+j*h2;
ph0(k-1,j+1)=vp1(x10,x2,cc);
ph0(k,j+1)=vp1(x10+l1,x2,cc);
end;
for j=1:N-1;
du1=1/h1*(w(p1+1,q1+j)-w(p1,q1+j))+h1/(2*h2*h2)*(w(p1,q1+j-1)-
2*w(p1,q1+j)+w(p1,q1+j+1))+h1/2*ph0(k-1,j+1);
du2=1/h1*(w(p2-1,q1+j)-w(p2,q1+j))+h1/(2*h2*h2)*(w(p2,q1+j-1)-
2*w(p2,q1+j)+w(p2,q1+j+1))+h1/2*ph0(k,j+1);
etak(k-1,j+1)=(1-teta)*etak(k-1,j+1)+teta*du1;
etak(k,j+1)=(1-teta)*etak(k,j+1)-teta*du2;
end;
end;%Het vong lap hieu chinh
saiso=0;
for i=0:SM*M;
for j=0:N;
if abs(w(i+1,j+1))>10^(-7);
if abs((w(i+1,j+1)-ud(i+1,j+1))/w(i+1,j+1))>saiso;
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
71
saiso=abs((w(i+1,j+1)-ud(i+1,j+1))/w(i+1,j+1));
end;
end;
end;
end;
%for i=0:SM*M;
% for j=0:N;
% if abs(w(i+1,j+1)-ud(i+1,j+1))>saiso;
% saiso=abs(w(i+1,j+1)-ud(i+1,j+1));
% end;
% end;
%end;
saiso
end;%Het vong lap while
thoigian=cputime-thoigian
count
% Chuong trinh Quang_Thu_3 giai bai toan co hoc bang mo hinh tinh toan
% song song - so do hieu chinh ham saito-fujita
% Truong hop mien hinh hoc phuc tap-chia SM mien
% Truong hop biet truoc nghiem dung
% phi la ham ve phai
% b1,b2,b3,b4: la cac gia tri tren bien trai,phai,duoi,tren
% u la nghiem bai toan
% Ngay lap 18/09/2008
clear all
clc
teta=0.9;
a=1;b=1;cc=0;
SM=21;%So mien chia
count=0;
epxilon=1*10^(-4);saiso=10;
n=6;
N=2^n;
M=N;
q1=1;q2=N+1;h1=a/M;h2=b/N;l1=a;l2=b;x10=0;x20=0;
%buoc lap - Gia tri ban dau eta=0;
for k=1:SM;
for j=0:N;
etak(k,j+1)=0;
du1(k,j+1)=0;
du2(k,j+1)=0;
end;
end;
for i=0:SM*M;
for j=0:N;
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
72
ud(i+1,j+1)=u(x10+i*h1,x20+j*h2);
w(i+1,j+1)=0;
end;
end;
thoigian=cputime;
while and(countepxilon);
count=count+1;
%Giai cac bai toan tren mien chan
for k=2:2:SM-1;
p1=(k-1)*M+1;p2=k*M+1;
x10=(k-1)*a;x20=0;
% Gia tri ve phai
for i=0:M;
for j=0:N;
x1=x10+i*h1;
x2=x20+j*h2;
phi(i+1,j+1)=vp1(x1,x2,cc); % Ham ve phai
end;
end;
% Dieu kien tren canh trai va phai
for j=0:N;
x2=x20+j*h2;
b1(j+1)=etak(k-1,j+1);
b2(j+1)=etak(k,j+1);
end;
% Dieu kien tren canh duoi va tren
for i=0:M;
x1=x10+i*h1;
b3(i+1)=u(x1,x20);
b4(i+1)=dhy(x1,x20+l2);
end;
uu=u0001(phi,b1,b2,b3,b4,l1,l2,cc,x10,x20,M,N,n,p1,p2,q1,q2);
w(p1:p2,q1:q2)=uu(p1:p2,q1:q2);
for k=2:2:SM-1;%xac dinh gia tri dao ham
p1=(k-1)*M+1;p2=k*M+1;
x10=(k-1)*a;x20=0;
for j=0:N;
x2=x20+j*h2;
ph0(k-1,j+1)=vp1(x10,x2,cc);
ph0(k,j+1)=vp1(x10+l1,x2,cc);
end;
for j=1:N-1;
du1(k-1,j+1)=1/h1*(w(p1+1,q1+j)-w(p1,q1+j))+h1/(2*h2*h2)*(w(p1,q1+j-1)-
2*w(p1,q1+j)+w(p1,q1+j+1))+h1/2*ph0(k-1,j+1);
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
73
du2(k,j+1)=1/h1*(w(p2-1,q1+j)-w(p2,q1+j))+h1/(2*h2*h2)*(w(p2,q1+j-1)-
2*w(p2,q1+j)+w(p2,q1+j+1))+h1/2*ph0(k,j+1);
end;
du1(k-1,1)=dhx(x10,x20);du1(k-1,N+1)=dhx(x10,x20+l2);
du2(k,1)=-dhx(x10+l1,x20);du2(k,N+1)=-dhx(x10+l1,x20+l2);
end;
end;%Het vong lap mien chan
%Giai cac bai toan tren mien le
for k=1:2:SM;
p1=(k-1)*M+1;p2=k*M+1;
x10=(k-1)*a;x20=0;
% Gia tri ve phai
for i=0:M;
for j=0:N;
x1=x10+i*h1;
x2=x20+j*h2;
phi(i+1,j+1)=vp1(x1,x2,cc); % Ham ve phai
end;
end;
% Dieu kien tren canh trai va phai
for j=0:N;
x2=x20+j*h2;
if k==1
b1(j+1)=u(x10,x2);
else
b1(j+1)=-du2(k-1,j+1);
end;
if k==SM
b2(j+1)=u(x10+l1,x2);
else
b2(j+1)=du1(k,j+1);
end;
end;
% Dieu kien tren canh duoi va tren
for i=0:M;
x1=x10+i*h1;
b3(i+1)=u(x1,x20);
b4(i+1)=u(x1,x20+l2);
end;
if k==1;
uu=u0100(phi,b1,b2,b3,b4,l1,l2,cc,x10,x20,M,N,n,p1,p2,q1,q2);
w(p1:p2,q1:q2)=uu(p1:p2,q1:q2);
else
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
74
if k==SM;
uu=u1000(phi,b1,b2,b3,b4,l1,l2,cc,x10,x20,M,N,n,p1,p2,q1,q2);
w(p1:p2,q1:q2)=uu(p1:p2,q1:q2);
else
uu=u1100(phi,b1,b2,b3,b4,l1,l2,cc,x10,x20,M,N,n,p1,p2,q1,q2);
w(p1:p2,q1:q2)=uu(p1:p2,q1:q2);
end;
end;
end;%Het vong lap mien le
% Hieu chinh gia tri etak(j) tren bien
for k=2:2:SM-1;
p1=(k-1)*M+1;p2=k*M+1;
for j=0:N;
etak(k-1,j+1)=(1-teta)*etak(k-1,j+1)+teta*w(p1,j+1);
etak(k,j+1)=(1-teta)*etak(k,j+1)+teta*w(p2,j+1);
end;
end;%Het vong lap hieu chinh
saiso=0;
for i=0:SM*M;
for j=0:N;
if abs(w(i+1,j+1))>10^(-7);
if abs((w(i+1,j+1)-ud(i+1,j+1))/w(i+1,j+1))>saiso;
saiso=abs((w(i+1,j+1)-ud(i+1,j+1))/w(i+1,j+1));
end;
end;
end;
end;
saiso
end;%Het vong lap while
thoigian=cputime-thoigian
count
Các file đính kèm theo tài liệu này:
- 12LV09_CNTT_KHMTCaoThiAnhThu.pdf