Luận án: Một số phương pháp song song dạng Runge-Kutta giải bài toán không cương - Nguyễn Thu Thủy

ĐẠ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 TIEU LUAN MOI download : skknchat@gmail.com ĐẠ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. Nguyễn Hữu Công HÀ NỘI - 2014 TIEU LUAN MOI download : skknchat@gmail.com 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 TIEU LUAN MOI download : skknchat@gmail.com LỜI CẢM ƠN Luận án được hoàn thành dưới sự hướng dẫn của GS.

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ả TIEU LUAN MOI download : skknchat@gmail.com 1 MỤC LỤC MỤC LỤC.

1 MỘT SỐ KÍ HIỆU CHUNG. 4 DANH MỤC CÁC TỪ VIẾT TẮT. MỘT SỐ KIẾN THỨC CƠ SỞ 11 1.1 Phương pháp Runge-Kutta .1 Cấp chính xác của phương pháp Runge-Kutta .2 Tính ổn định của phương pháp Runge-Kutta .2 Các phương pháp Runge-Kutta hiển .3 Các phương pháp Runge-Kutta ẩn .4 Phương pháp Runge-Kutta lặp song song (PIRK) .1 Nội dung phương pháp PIRK .2 Cấp chính xác của phương pháp PIRK .3 Sự ổn định của phương pháp PIRK .4 Sự hội tụ của quá trình lặp .5 Một số mã tính toán tuần tự .1 Phương pháp kẹp thêm có cấp chính xác 5 - mã DOPRI5 .2 Phương pháp kẹp thêm có cấp chính xác 8- mã DOPRI853 .3 Phương pháp ngoại suy- mã ODEX .6 Ba bài toán thử. 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 TIEU LUAN MOI download : skknchat@gmail.com 2 GAUSS-LEGENDRE 40 2.1 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 .1 Ổn định tuyến tính .2 Thử nghiệm số .2 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 .1 Điều kiện bậc .2 Sự hội tụ của quá trình lặp .3 Miền ổn định .4 Thử nghiệm số .5 So sánh với các phương pháp song song .6 So sánh với các mã tuần tự.

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 65 3.1 Phương pháp giả Runge-Kutta hai bước kẹp thêm với bước lưới thay đổi .1 Điều kiện bậc .2 Công thức kẹp thêm .2 Phương pháp PIPTRK với chiến lược điều khiển bước lưới 73 3.1 Điều kiện bậc cho công thức dự báo .2 Sự hội tụ của quá trình lặp .3 Điều khiển bước lưới .3 Thử nghiệm số .1 Xác lập phương pháp PIPTRKSC .2 So sánh với các mã song song .3 So sánh với các mã tuần tự .4 Tính hiệu quả của chiến lược điều khiển bước lưới 85 TIEU LUAN MOI download : skknchat@gmail.com 3 Chương 4. PHƯƠNG PHÁP GIẢ RUNGE-KUTTA BA BƯỚC 89 4.1 Phương pháp giả Runge-Kutta ba bước (EPThRK) .1 Điều kiện bậc .2 Tính ổn định .2 Các thử nghiệm số .1 Chọn phương pháp EPThRK .2 So sánh với các mã song song .3 So sánh với các mã tuần tự .4 So sánh phương pháp EPThRK với phương pháp TBTPIRKG và PIPTRKSC. 108 KIẾN NGHỊ MỘT SỐ HƯỚNG NGHIÊN CỨU TIẾP THEO. 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 TIEU LUAN MOI download : skknchat@gmail.com 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. Lũy thừa của một véc tơ. , cs )T , khi đó ck = (ck1 , ck2 ,. Toán tử exp( ) dx d d d2 dn exp( ) = 1 + + + ··· + +.

dx dx 2!dx n!dxn 4. 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. 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 ,.

, 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 ),. 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 ),. TIEU LUAN MOI download : skknchat@gmail.com 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 TIEU LUAN MOI download : skknchat@gmail.com 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 TIEU LUAN MOI download : skknchat@gmail.com 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.

TIEU LUAN MOI download : skknchat@gmail.com 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". 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).

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.