MỘT SỐ PHƯƠNG PHÁP SONG SONG DẠNG RUNGE-KUTTA GIẢI BÀI TOÁN KHÔNG CƯƠNG

  • Số trang: 121 |
  • Loại file: PDF |
  • Lượt xem: 44 |
  • Lượt tải: 0
nhattuvisu

Đã đăng 26946 tài liệu

Mô tả:

ĐẠ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 -