ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
------ ------
NGUYỄN THU THỦY
MỘT SỐ PHƯƠNG PHÁP SONG SONG
DẠNG RUNGE - KUTTA
GIẢI BÀI TOÁN KHÔNG CƯƠNG
LUẬN ÁN TIẾN SĨ TOÁN HỌC
HÀ NỘI - 2014
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
------ ------
NGUYỄN THU THỦY
MỘT SỐ PHƯƠNG PHÁP SONG SONG
DẠNG RUNGE - KUTTA
GIẢI BÀI TOÁN KHÔNG CƯƠNG
Chuyên ngành:
Toán học tính toán
Mã số:
62 46 30 01
LUẬN ÁN TIẾN SĨ TOÁN HỌC
Người hướng dẫn khoa học: GS.TSKH. Nguyễn Hữu Công
HÀ NỘI - 2014
LỜI CAM ĐOAN
Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các kết
quả nêu trong luận án là trung thực và chưa từng được ai công bố trong
bất kỳ công trình nào khác.
Tác giả
Nguyễn Thu Thủy
LỜI CẢM ƠN
Luận án được hoàn thành dưới sự hướng dẫn của GS. TSKH. Nguyễn
Hữu Công. Thầy đã dẫn dắt tác giả làm quen với nghiên cứu khoa học
từ khi tác giả đang là học viên cao học. Ngoài những chỉ dẫn về mặt
khoa học, sự động viên và lòng tin tưởng của thầy dành cho tác giả luôn
là động lực lớn giúp tác giả tự tin và say mê trong nghiên cứu. Qua đây
tác giả xin bày tỏ sự biết ơn sâu sắc và lòng quý mến đối với thầy.
Tác giả cũng xin được bày tỏ lòng biết ơn đến các thày cô và các bạn
đồng nghiệp trong xemina Bộ môn Toán học tính toán, trường Đại học
Khoa học Tự nhiên-Đại học Quốc Gia Hà Nội đã tạo môi trường học
tập và nghiên cứu thuận lợi giúp tác giả hoành thành luận án này. Tại
đây tác giả đã nhận được nhiều chỉ dẫn, góp ý cũng như một môi trường
nghiên cứu sôi nổi và thân thiện, điều không thể thiếu trong quá trình
nghiên cứu, hoàn thành luận án của tác giả.
Tác giả xin gửi lời cám ơn tới các thày cô trong khoa Toán-Cơ-Tin
học, Phòng Sau đại học, Trường Đại học Khoa học Tự nhiên- Đại học
Quốc Gia Hà Nội, nơi tác giả đã học tập và nghiên cứu.
Tác giả xin được bày tỏ lòng biết ơn đến Ban Giám hiệu, Ban chủ
nhiệm khoa Toán-Tin và Bộ môn Toán ứng dụng trường Đại học Sư
phạm Hà Nội đã tạo những điều kiện thuận lợi trong quá trình tác giả
học tập, công tác và hoàn thành luận án này.
Trong quá trình học tập và hoàn thành luận án, tác giả đã nhận được
sự quan tâm giúp đỡ và góp ý của GS.TSKH Phạm Kỳ Anh, PGS.TSKH
Vũ Hoàng Linh,... Tác giả xin chân thành cảm ơn các Giáo sư về sự giúp
đỡ quý báu này.
Cuối cùng, tác giả xin được bày tỏ lòng biết ơn đến ông bà, bố mẹ,
anh chị em hai bên nội ngoại, cùng chồng và bạn bè đã góp ý và động
viên tác giả trong quá trình học tập và hoàn thành luận án.
Tác giả
1
MỤC LỤC
MỤC LỤC . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
. . . . . . . . . . . . . . . . . . .
4
DANH MỤC CÁC TỪ VIẾT TẮT . . . . . . . . . . . . . . . .
5
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
MỘT SỐ KÍ HIỆU CHUNG
MỞ ĐẦU
Chương 1. MỘT SỐ KIẾN THỨC CƠ SỞ
1.1
11
Phương pháp Runge-Kutta . . . . . . . . . . . . . . . . .
12
1.1.1
Cấp chính xác của phương pháp Runge-Kutta . .
14
1.1.2
Tính ổn định của phương pháp Runge-Kutta . . .
15
1.2
Các phương pháp Runge-Kutta hiển . . . . . . . . . . .
16
1.3
Các phương pháp Runge-Kutta ẩn . . . . . . . . . . . .
18
1.4
Phương pháp Runge-Kutta lặp song song (PIRK) . . . .
21
1.4.1
Nội dung phương pháp PIRK . . . . . . . . . . .
23
1.4.2
Cấp chính xác của phương pháp PIRK . . . . . .
24
1.5
1.4.3
Sự ổn định của phương pháp PIRK
. . . . . . .
24
1.4.4
Sự hội tụ của quá trình lặp . . . . . . . . . . . .
26
Một số mã tính toán tuần tự . . . . . . . . . . . . . . . .
26
1.5.1
Phương pháp kẹp thêm có cấp chính xác 5 - mã
DOPRI5 . . . . . . . . . . . . . . . . . . . . . . . .
1.5.2
Phương pháp kẹp thêm có cấp chính xác 8- mã
DOPRI853 . . . . . . . . . . . . . . . . . . . . . .
28
Phương pháp ngoại suy- mã ODEX . . . . . . . . .
31
Ba bài toán thử . . . . . . . . . . . . . . . . . . . . . . .
37
1.5.3
1.6
27
Chương 2. PHƯƠNG PHÁP LẶP SONG SONG DẠNG RUNGEKUTTA HAI BƯỚC MỘT DỰA TRÊN CÁC ĐIỂM TRÙNG KHỚP
2
GAUSS-LEGENDRE
2.1
2.2
40
Phương pháp dạng Runge-Kutta hai bước một dựa trên
các điểm trùng khớp Gauss-Legendre . . . . . . . . . . .
41
2.1.1
Ổn định tuyến tính . . . . . . . . . . . . . . . . .
44
2.1.2
Thử nghiệm số . . . . . . . . . . . . . . . . . . .
49
Phương pháp lặp song song dạng Runge-Kutta hai bước
một dựa trên các điểm trùng khớp Gauss-Legendre . . .
50
2.2.1
Điều kiện bậc . . . . . . . . . . . . . . . . . . . .
52
2.2.2
Sự hội tụ của quá trình lặp . . . . . . . . . . . .
54
2.2.3
Miền ổn định . . . . . . . . . . . . . . . . . . . .
55
2.2.4
Thử nghiệm số . . . . . . . . . . . . . . . . . . .
57
2.2.5
So sánh với các phương pháp song song . . . . . .
59
2.2.6
So sánh với các mã tuần tự . . . . . . . . . . . .
62
Chương 3. PHƯƠNG PHÁP LẶP SONG SONG GIẢ RUNGE-KUTTA
HAI BƯỚC VỚI CHIẾN LƯỢC ĐIỀU KHIỂN BƯỚC LƯỚI
3.1
3.2
3.3
65
Phương pháp giả Runge-Kutta hai bước kẹp thêm với
bước lưới thay đổi . . . . . . . . . . . . . . . . . . . . . .
66
3.1.1
Điều kiện bậc . . . . . . . . . . . . . . . . . . . .
68
3.1.2
Công thức kẹp thêm . . . . . . . . . . . . . . . .
72
Phương pháp PIPTRK với chiến lược điều khiển bước lưới 73
3.2.1
Điều kiện bậc cho công thức dự báo . . . . . . . .
75
3.2.2
Sự hội tụ của quá trình lặp . . . . . . . . . . . .
77
3.2.3
Điều khiển bước lưới . . . . . . . . . . . . . . . .
77
Thử nghiệm số . . . . . . . . . . . . . . . . . . . . . . .
79
3.3.1
Xác lập phương pháp PIPTRKSC . . . . . . . . .
79
3.3.2
So sánh với các mã song song . . . . . . . . . . .
81
3.3.3
So sánh với các mã tuần tự . . . . . . . . . . . .
83
3.3.4
Tính hiệu quả của chiến lược điều khiển bước lưới
85
3
Chương 4. PHƯƠNG PHÁP GIẢ RUNGE-KUTTA BA BƯỚC
4.1
4.2
89
Phương pháp giả Runge-Kutta ba bước (EPThRK) . . .
90
4.1.1
Điều kiện bậc . . . . . . . . . . . . . . . . . . . .
92
4.1.2
Tính ổn định . . . . . . . . . . . . . . . . . . . .
97
Các thử nghiệm số . . . . . . . . . . . . . . . . . . . . .
98
4.2.1
Chọn phương pháp EPThRK . . . . . . . . . . .
98
4.2.2
So sánh với các mã song song . . . . . . . . . . . 100
4.2.3
So sánh với các mã tuần tự . . . . . . . . . . . . 102
4.2.4
So sánh phương pháp EPThRK với phương pháp
TBTPIRKG và PIPTRKSC . . . . . . . . . . . . 104
KẾT LUẬN . . . . . . . . . . . . . . . . . . . . . . . . . . . .
KIẾN NGHỊ MỘT SỐ HƯỚNG NGHIÊN CỨU TIẾP THEO
108
. 109
DANH MỤC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ LIÊN
QUAN ĐẾN LUẬN ÁN . . . . . . . . . . . . . . . . . . .
110
TÀI LIỆU THAM KHẢO . . . . . . . . . . . . . . . . . . . . .
111
4
MỘT SỐ KÍ HIỆU CHUNG
1. Một số kí hiệu thông thường.
• Rd − không gian các véc tơ thực d− chiều.
• C− tập số phức.
• C− − tập số phức với phần thực không dương.
• Với số phức z ∈ C, Re(z), Im(z) lần lượt là phần thực và phần
ảo của số phức z.
• σ(A) là phổ của ma trận A.
• ρ(A) là bán kính phổ của ma trận A.
2. Lũy thừa của một véc tơ. Giả sử c = (c1 , c2 , . . . , cs )T , khi đó
ck = (ck1 , ck2 , . . . , cks )T
3. Toán tử exp(
d
)
dx
d
d
d2
dn
exp( ) = 1 +
+
+ ··· +
+ ...
dx
dx 2!dx
n!dxn
4. Kí hiệu véc tơ e. Véc tơ e luôn hiểu là véc tơ có tất cả các thành
phần bằng 1.
5. Véc tơ hàm. Giả sử f (x, y) là hàm thực của hai biến x, y. Nếu
thay x và y tương ứng bởi hai véc tơ v = (v1 , v2 , . . . , vs )T và w =
(w1 , w2 , . . . , ws )T thì ta được véc tơ hàm với s thành phần:
f (v, w) = [f (v1 , w1 ), f (v2 , w2 ), . . . , f (vs , ws )]T .
Nếu x ∈ R, còn y thay bởi w = (w1 , w2 , . . . , ws )T thì ta có:
f (x, w) = [f (x, w1 ), f (x, w2 ), . . . , f (x, ws )]T .
5
DANH MỤC CÁC TỪ VIẾT TẮT
EPThRK
Explicit pseudo three-step Runge-Kutta method
Phương pháp giả Runge-Kutta ba bước
ERK
Explicit Runge-Kutta
Runge-Kutta hiển
IRK
Implicit Runge-Kutta
Rungge-Kutta ẩn
PC
Predictor-Corrector
Dự báo-Hiệu chỉnh
PIPTRK
parallel-iterated pseudo two-step Runge- Kutta methods
Phương pháp lặp song song giả Runge-Kutta hai bước
PIPTRKSC Parallel-iterated pseudo two-step Runge-Kutta method with
step size control
Phương pháp lặp song song giả Runge-Kutta hai bước với
chiến lược điều khiển bước lưới.
PTRK
Pseudo two-step RK methods
Phương pháp giả Runge-Kutta hai bước
TBTIRKG
Two-step-by-two-step IRK methods based on Gauss-Legendre
collocations points
Phương pháp dạng Runge-Kutta ẩn hai bước một dựa trên
các điểm trùng khớp Gauss-Legendre
TBTRKG
Two-step-by-two-step Runge-Kutta-type corrector methods
based on Gauss-Legendre collocation points
Phương pháp hiệu chỉnh dạng Runge-Kutta hai bước một
dựa trên điểm trùng khớp Gauss-Legendre
TBTPIRKG two-step-by-two-step parallel-iterated Runge-Kutta-type PC
methods based on Gauss-Legendre collocation points
6
Phương pháp lặp song song dạng Runge-Kutta hai bước một
dựa trên các điểm trùng khớp Gauss-Legendre
7
MỞ ĐẦU
1. Lịch sử vấn đề và lí do chọn đề tài
Trong các lĩnh vực khoa học và kỹ thuật có rất nhiều bài toán qui
về việc tìm nghiệm của hệ phương trình vi phân thường thỏa mãn một
số điều kiện nào đó (điều kiện ban đầu, điều kiện biên,...). Đa số các
hệ phương trình vi phân mô tả các hệ cơ học, vật lý, hóa học, sinh
học,... đều rất phức tạp và rất khó tìm được nghiệm đúng của bài toán
mà thông thường ta phải giải gần đúng nghiệm của bài toán. Phương
pháp giải gần đúng hiệu quả nhất là phương pháp số. Việc nghiên cứu
các phương pháp số để giải gần đúng phương trình vi phân thường đã
được nghiên cứu trong nhiều năm qua. Phương pháp số phổ biến nhất
là phương pháp tuyến tính đa bước và phương pháp Runge-Kutta, có
nguồn gốc từ thế kỷ trước, đặc biệt nó có sự đột phá mạnh kể từ khi
máy tính điện tử ra đời vào những năm 1950. Kể từ đó, nhiều phương
pháp hiệu quả đã được xây dựng và đã có một số mã tính toán (code
tính toán) hiệu quả và đáng tin cậy cho việc giải số phương trình vi phân
thường.
Do nhiều thuật toán số được thiết kế cho máy tính tuần tự, các
phương pháp hiện có không phải là tốt nhất. Điều này đặc biệt đúng
cho các phương pháp số giải bài toán thời gian thực của phương trình vi
phân thường có kích thước lớn. Do đó, với mong muốn xem xét các thuật
toán và thay thế các thuật toán cũ một cách phù hợp hơn, chúng tôi đưa
ra mục tiêu chính của luận án là: xây dựng và phân tích các thuật toán
mới để giải hiệu quả hơn bài toán giá trị ban đầu không cương của hệ
phương trình vi phân thường. Bài toán giá trị ban đầu không cương của
hệ phương trình vi phân có dạng:
y0 (t) = f (t, y(t)),
y(t0 ) = y0 ,
t0 ≤ t ≤ T.
8
hoặc ở dạng autonom:
y0 (t) = f (y(t)),
y(t0 ) = y0 ,
t0 ≤ t ≤ T.
Với sự phát triển không ngừng của khoa học kỹ thuật, sự xuất hiện
của máy tính song song đã mang lại một sự phát triển mạnh mẽ của các
phương pháp số. Các thuật toán đã được nghiên cứu cần tận dụng lợi
thế của "siêu máy tính".
2. Mục đích, đối tượng và phạm vi nghiên cứu
Mục đích của luận án là nghiên cứu và xây dựng các phương pháp
song song mới dạng Runge-Kutta để giải một cách hiệu quả bài toán giá
trị ban đầu không cương trên siêu máy tính (máy tính song song).
3. Phương pháp nghiên cứu
Trong luận án này, việc nghiên cứu và xây dựng các phương pháp
song song mới dạng Runge-Kutta được bắt đầu bằng việc đề xuất cấu
trúc của phương pháp. Tiếp theo, kỹ thuật trùng khớp kết hợp với kỹ
thuật khai triển Taylor được sử dụng để xác định hệ số của phương pháp
theo điều kiện cấp chính xác. Việc nghiên cứu cấp chính xác và miền
ổn định của các phương pháp được dùng để chứng tỏ tính ưu việt của
các phương pháp mới được nghiên cứu trên phương diện lý thuyết. Cuối
cùng các phương pháp mới được sử dụng để giải một số bài toán thử
kinh điển. Kết quả tính toán được so sánh với các kết quả khi giải cùng
bài toán thử của các phương pháp thuộc loại tốt và tin cậy hiện hành để
khẳng định tính ưu việt của các phương pháp mới về phương diện thực
hành.
4. Cấu trúc và các kết quả của luận án
Ngoài phần mở đầu và kết luận, luận án gồm 4 chương:
- Chương 1 giới thiệu bài toán giá trị ban đầu và một số kiến thức
cơ bản về phương pháp Runge-Kutta. Trong chương này, chúng tôi cũng
9
giới thiệu một số phương pháp song song và mã tính toán (code) hiệu
quả có sẵn. Đây là những phương pháp và mã tính toán mà chúng tôi
sẽ sử dụng để so sánh với các phương pháp mà chúng tôi đưa ra.
- Chương 2 đề xuất và nghiên cứu các phương pháp dự báo hiệu
chỉnh lặp song song dạng Runge-Kutta (RK) hai bước một dựa trên các
điểm trùng khớp (collocation) Gauss-Legendre. Phương pháp dự báo có
công thức dạng Adams. Phương pháp hiệu chỉnh được xây dựng trên cơ
sở bộ hệ số của phương pháp RK Gauss-Legendre s nấc với vectơ trùng
khớp c1 , . . . , cs và phương pháp RK trùng khớp 2s nấc với vectơ trùng
khớp c1 , . . . , cs , 1 + c1 , . . . , 1 + cs . Tại bước lấy tích phân thứ n, các giá
trị xấp xỉ nấc của phương pháp RK trùng khớp 2s nấc được tính tại
tn + (1 + c1 )h, . . . , tn + (1 + cs )h có thể sử dụng thay cho các giá trị xấp
xỉ nấc của phương pháp RK Gauss-Legendre tại bước lấy tích phân thứ
(n+2). Bằng cách này, chúng tôi có phương pháp hiệu chỉnh có quá trình
lấy tích phân hai bước một. Vì vậy, phương pháp dự báo hiệu chỉnh lặp
song song thu được cũng có quá trình tích phân hai bước một và cho ta
quá trình tích phân nhanh hơn. Các thử nghiệm số chứng tỏ các phương
pháp dự báo hiệu chỉnh lặp song song dạng RK hai bước một dựa trên
các điểm trùng khớp Gauss-Legendre (Phương pháp TBTPIRKG) hiệu
quả hơn một số đại diện của phương pháp song song và các mã tuần tự
hiện có (phương pháp PIRK, mã ODEX, DOPRI5 và DOP853).
- Trong Chương 3, chúng tôi trình bày phương pháp lặp song song
giả Runge-Kutta hai bước với chiến lược điều khiển bước lưới. Trong
chương này, hai công thức với cấp chính xác s và s − 1 xây dựng kèm
được dùng để đánh giá sai số địa phương phục vụ cho việc chọn bước
lưới tự động. Các thử nghiệm số cho thấy phương pháp mới của chúng
tôi hiệu quả hơn so với các mã có từ trước đó. Chiến lược điều khiển
bước lưới cũng cho kết quả tốt hơn so với phương pháp với bước lưới cố
định.
- Trong Chương 4, chúng tôi trình bày một lớp phương pháp song
10
song giả Runge-Kutta ba bước. Bằng cách sử dụng kỹ thuật trùng khớp
và các chọn các điểm trùng khớp phù hợp chúng ta có thể thu được một
phương pháp s nấc ổn định giả Runge-Kutta ba bước (phương pháp
EPThRK) có cấp chính xác p = 2s mà khi tính trên máy tính với s bộ
xử lý song song đòi hỏi chỉ một lần tính toán hàm vế phải f trên mỗi bộ
xử lý. Bằng việc giải số một vài bài toán thử thông dụng, chúng tôi chỉ
ra rằng các phương pháp mới EPThRK được đưa ra trong chương này
hiệu quả hơn các mã song song PIRK và các mã tuần tự ODEX, DOPRI5
và DOP853 đã biết.
5. Ý nghĩa của các kết quả của luận án
Các kết quả của luận án góp phần nghiên cứu và xây dựng các phương
pháp song song dạng Runge-Kutta để giải số bài toán giá trị ban đầu
không cương, nhằm góp phần vào lĩnh vực nghiên cứu thời sự này. Một
số ý tưởng và phương pháp được dùng trong luận án có thể dùng để
nghiên cứu giải các bài toán trong phương trình vi phân ngẫu nhiên và
phương trình vi phân có trễ.
Nội dung chính của luận án này đã được công bố trên các công trình
được liệt kê ở mục Danh mục công trình của tác giả (trang 110), và
được báo cáo tại:
- Xemina Toán học tính toán, trường Đại học Khoa học Tự NhiênĐH Quốc Gia Hà Nội.
- Hội nghị Tối ưu và Tính toán khoa học, Ba Vì - 2011, 2014.
- Hội nghị - Đại hội Toán học Toàn quốc, Nha Trang - 2013.
- Hội nghị khoa học Khoa Toán -Tin, Trường Đại học Sư phạm Hà
Nội - 2011, 2012, 2014.
11
Chương 1
MỘT SỐ KIẾN THỨC CƠ SỞ
Mục đích chính của luận án là nghiên cứu và đưa ra các thuật toán
để giải số bài toán giá trị ban đầu không cương (IVPs) cho hệ phương
trình vi phân cấp một (xem Mục 2.2 trong [7]):
y0 (t) = f (t, y(t)),
y(t0 ) = y0 ,
t0 6 t 6 T,
(1.1)
hoặc dạng autonom:
y0 (t) = f (y(t)),
y(t0 ) = y0 ,
t0 6 t 6 T,
(1.2)
trong đó y, f ∈ Rd .
Bài toán (1.1) có thể không có nghiệm hoặc có nghiệm nhưng không
duy nhất. Định lý sau đây đưa ra điều kiện đủ để bài toán (1.1) có
nghiệm duy nhất ([58, tr. 5]).
Định lý về sự tồn tại nghiệm Cho hàm số f : R × Rd → Rd xác định
liên tục trên miền D = {(t, y) : t0 6 t 6 T, y ∈ Rd } với t0 , T hữu hạn.
Giả sử tồn tại một hằng số L sao cho:
||f (t, y) − f (t, y∗ )|| 6 L||y − y∗ || với mọi (t, y) , (t, y∗ ) ∈ D
Khi đó với mọi y0 ∈ Rd luôn tồn tại duy nhất nghiệm của bài toán giá
trị ban đầu (1.1) sao cho y(t) liên tục, khả vi với mọi t ∈ [t0 , T ].
Trong luận án này, chúng tôi sẽ giả định rằng bài toán (1.1) luôn thỏa
mãn các giả thiết của định lý trên. Ngoài ra, ta giả thiết thêm nghiệm
y của bài toán là đủ trơn.
Trong chương này, chúng tôi trình bày một số kiến thức cơ bản về
phương pháp Runge-Kutta, một số phương pháp song song và mã tuần
12
tự tiêu biểu đã có mà sẽ được sử dụng để so sánh với các phương pháp
mới được đề xuất ở các chương sau. Phần cuối chương này nêu một số
bài toán thử nghiệm kinh điển, được dùng để so sánh tính hiệu quả của
các phương pháp được nghiên cứu trong luận án.
1.1
Phương pháp Runge-Kutta
Phương pháp số đơn giản nhất để giải số bài toán (1.1) là phương
pháp Euler. Tuy nhiên, phương pháp Euler có độ chính xác thấp và cấp
chính xác bằng 1. Năm 1895, Runge đã mở rộng phương pháp Euler bằng
cách thêm một bước Euler vào điểm giữa của đoạn lấy tích phân. Năm
1901 Kutta đã xây dựng một phương pháp có cấp chính xác 3 và 4. Đến
đầu những năm 1960, Butcher đề xuất phương pháp Runge-Kutta hiển
s nấc. Sau đó, đến năm 1963, 1964, Butcher đã có những nghiên cứu sâu
sắc về phương pháp Runge-Kutta (xem [10, 11, 12, 13, 14, 15, 16, 17]).
Phương pháp Runge-Kutta là phương pháp có nhiều tính chất ưu việt
như cấp chính xác cao, tính ổn định tốt. Trong mục này chúng tôi giới
thiệu một số kiến thức về phương pháp Runge-Kutta.
Phương pháp Runge-Kutta s nấc tổng quát được cho bởi công thức:
Yn,i = yn + h
yn+1 = yn + h
s
X
j=1
s
X
aij f (tn + cj h, Yn,j ),
i = 1, ..., s,
bj f (tn + cj h, Yn,j ).
(1.3a)
(1.3b)
j=1
trong đó A = (aij )s×s và các vectơ s chiều c = (c1 , ..., cs )T , b = (b1 , ..., bs )T
là ma trận và vectơ tham số của phương pháp.
Yn,i là vectơ nấc biểu diễn nghiệm xấp xỉ của nghiệm chính xác
tại các điểm nấc tn + ci h, tức là Yn,i ≈ y(tn + ci h); i = 1, ..., s; yn ≈
y(tn ); yn+1 ≈ y(tn+1 ); h = tn+1 − tn là độ dài bước lưới.
13
Ta giả sử điều kiện:
ci =
s
X
i = 1, s và điều kiện
aij ,
s
X
bi = 1
(1.4)
i=1
j=1
luôn được thỏa mãn.
Để thuận tiện cho việc trình bày ta ghi các hệ số xuất hiện trong các
công thức (1.3) vào một bảng gọi là bảng Butcher:
c1
a11
a12
...
a1s
c2
a21
a22
...
a2s
... ...
...
...
...
as1
as2
...
ass
b1
b2
...
cs
hay
c
A
bT
bs
Đặt Yn = [Yn,1 , . . . , Yn,s ]T , e = [1, . . . , 1]T ∈ Rs là các vectơ s chiều.
Khi (1.1) là bài toán vô hướng (d = 1) thì phương pháp RK (1.3) có
dạng đơn giản sau:
Yn = eyn + hAf (tn e + ch, Yn ),
(1.5a)
yn+1 = yn + hbT f (tn e + ch, Yn ).
(1.5b)
T
trong đó f (tn e + ch) = f (tn + c1 h), ..., f (tn + cs h) .
Phân loại
• Nếu aij = 0, với mọi j ≥ i, i = 1, s hay A là ma trận tam giác
dưới chặt thì phương pháp Runge-Kutta (1.3) gọi là phương pháp
Runge-Kutta hiển (hay phương pháp Runge-Kutta cổ điển).
• Nếu aij = 0, với mọi j > i, i = 1, s hay A là ma trận tam giác
dưới thì phương pháp Runge-Kutta (1.3) được gọi là phương pháp
Runge-Kutta nửa ẩn (hay phương pháp đường chéo ẩn).
• Trong các trường hợp còn lại thì phương pháp Runge-Kutta (1.3)
được gọi là phương pháp Runge-Kutta ẩn.
14
1.1.1
Cấp chính xác của phương pháp Runge-Kutta
Cấp chính xác của một phương pháp phản ánh sai số địa phương của
phương pháp. Việc xây dựng một phương pháp số có cấp chính xác cao
và giảm thiểu khối lượng tính toán là cần thiết. Trong mục này, chúng
tôi trình bày về cấp chính xác của phương pháp Runge-Kutta s nấc tổng
quát (1.3).
Định nghĩa 1.1.1 Với giả thiết yn = y(tn ), sai số chặt cụt địa phương
của phương pháp RK (1.3) tại tn+1 được xác định bởi công thức:
Tn+1 := y(tn+1 ) − yn+1 .
Định nghĩa 1.1.2 Cấp chính xác của phương pháp Runge-Kutta (1.3)
là số nguyên p lớn nhất sao cho:
Tn+1 = O(hp+1 ).
Ta có, mọi phương pháp Runge-Kutta (1.3) đều có cấp chính xác p ≥ 1
(xem [17, 40, 41, 42]).
Định nghĩa 1.1.3 Phương pháp Runge-Kutta (1.3) được gọi là có cấp
chính xác nấc q nếu:
y(tn + ci h) − Yn,i = O(hq+1 ),
với mọi i = 1, 2, ..., s. Cấp chính xác nấc địa phương là q + 1.
Đặt
B(w) :
C(w) :
1
bT cp−1 = ,
p
cp
Acp−1 = ,
p
p = 1, ..., w.
p = 1, ..., w.
Cấp chính xác p và cấp chính xác nấc q của một phương pháp có vai
trò rất quan trọng khi chúng ta giải các bài toán cương. Các định lý sau
15
đây chỉ ra điều kiện để phương pháp Runge-Kutta có cấp chính xác p
và cấp chính xác nấc lớn nhất của phương pháp Runge-Kutta s-nấc ([7,
tr. 80]).
Định lí 1.1.1 Phương pháp Runge-Kutta (1.3) có cấp chính xác w nếu
các điều kiện C(w), B(w) thỏa mãn.
Định lí 1.1.2 Cấp chính xác nấc lớn nhất của phương pháp RungeKutta s nấc là s.
1.1.2
Tính ổn định của phương pháp Runge-Kutta
Để nghiên cứu tính ổn định của phương pháp Runge-Kutta (1.3),
chúng ta dựa vào phương trình thử: y 0 = λy, λ ∈ C, Re(λ) < 0. Áp
dụng phương pháp Runge-Kutta (1.3) vào phương trình thử và giả sử
(I − zA)−1 tồn tại, ta thu được hàm ổn định của phương pháp RungeKutta (1.3) là:
R(z) = 1 + zbT (I − zA)−1 e.
(1.7)
Định nghĩa 1.1.4 Miền ổn định của phương pháp Runge-Kutta (1.3)
là:
Sstab := {z ∈ C− : |R (z) | ≤ 1}.
Định nghĩa 1.1.5
• Phương pháp Runge-Kutta (1.3) được gọi là ổn định tuyệt đối
(A-ổn định) nếu C− ⊆ Sstab ([11, 17, 40, 41, 42]).
• Phương pháp Runge-Kutta (1.3) được gọi là L-ổn định nếu nó là
A-ổn định và R(z) = 0 khi z = −∞ (hay R(−∞) = 0) ([17, 42]).
• Phương pháp Runge-Kutta (1.3) được gọi là A-ổn định mạnh nếu
nó là A-ổn định và R(−∞) < 1.
16
Định lí 1.1.3 ([58, tr.199]) Hàm ổn định R(z) của phương pháp RungeKutta (1.3) thỏa mãn:
det I − zA + zebT
.
R(z) =
det I − zA
Nhận xét:
• Nếu phương pháp Runge-Kutta (1.3) là phương pháp hiển (ERK)
thì det(I − zA) = 1 nên hàm ổn định của nó là một đa thức. Do
đó phương pháp ERK không ổn định tuyệt đối.
• Nếu phương pháp Runge-Kutta (1.3) là phương pháp ẩn (IRK)
Pk (z)
,
thì hàm ổn định của nó là một hàm phân thức R(z) =
Qm (z)
trong đó Pk , Qm là các đa thức bậc k, m tương ứng (k, m ≤ s). Vì
vậy, miền ổn định có thể là vô hạn. Từ đó suy ra điều kiện cần để
phương pháp RK ổn định tuyệt đối là phương pháp RK đó phải là
phương pháp RK ẩn. Nếu cấp chính xác của xấp xỉ này so với ez là
k + m, thì ta gọi là (k, m) cặp xấp xỉ. Ehle (1969) đã chứng minh
được rằng phương pháp RK với cặp xấp xỉ (s − 1, s) và (s − 2, s)
là L- ổn định và phỏng đoán rằng phương pháp RK có cặp xấp xỉ
(k, s) là A-ổn định khi và chỉ khi s − 2 ≤ k ≤ s. Điều này đã được
Wanner chứng minh vào năm 1978 [7, tr. 87].
1.2
Các phương pháp Runge-Kutta hiển
Trong những năm 60 của thế kỷ XX, khi công cụ tính toán chưa phát
triển thì người ta chủ yếu nghiên cứu lớp các phương pháp Runge-Kutta
hiển (ERK). Các phương pháp hiển không ổn định tuyệt đối nhưng vẫn
là các phương pháp số hiệu quả khi giải bài toán không cương (1.1). Việc
nghiên cứu xây dựng các phương pháp ERK có cấp chính xác cao là quá
trình xử lý hoàn toàn khác với các phương pháp IRK. Butcher là người
- Xem thêm -