Tài liệu Luận văn phương pháp runge kutta và thuật toán tính số mũ luyapunov của hệ động lực

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN QUANG HUY PHƯƠNG PHÁP RUNGE-KUTTA VÀ THUẬT TOÁN TÍNH SỐ MŨ LYAPUNOV CỦA HỆ ĐỘNG LỰC LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH THÁI NGUYÊN, 2017 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG PHƯƠNG PHÁP RUNGE-KUTTA VÀ THUẬT TOÁN TÍNH SỐ MŨ LYAPUNOV CỦA HỆ ĐỘNG LỰC Chuyên ngành: Khoa học máy tính Mã số: 60 48 01 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. TRƯƠNG HÀ HẢI Học viên thực hiện: Nguyễn Quang Huy THÁI NGUYÊN, 2017 1 LỜI CAM ĐOAN Tôi xin cam đoan: Luận văn thạc sỹ chuyên ngành Khoa học máy tính, tên đề tài “Phương pháp Runge-Kutta và thuật toán tính số mũ Lyapunov của hệ động lực” là công trình nghiên cứu, tìm hiểu và trình bày do tôi thực hiện dưới sự hướng dẫn khoa học của TS. Trương Hà Hải, Trường Đại học Công nghệ Thông tin và Truyền thông - Đại học Thái Nguyên. Kết quả tìm hiểu, nghiên cứu trong luận văn là hoàn toàn trung thực, không vi phạm bất cứ điều gì trong luật sở hữu trí tuệ và pháp luật Việt Nam. Nếu sai, tôi hoàn toàn chịu trách nhiệm trước pháp luật. Tất cả các tài liệu, bài báo, khóa luận, công cụ phần mềm của các tác giả khác được sử dụng lại trong luận văn này đều được chỉ dẫn tường minh về tác giả và đều có trong danh mục tài liệu tham khảo. Thái Nguyên, ngày 18 tháng 5 năm 2017 Tác giả luận văn Nguyễn Quang Huy i LỜI CẢM ƠN Tác giả xin chân thành cảm ơn TS Trương Hà Hải, trường Đại học Công nghệ thông tin và truyền thông - Đại học Thái Nguyên, là giáo viên hướng dẫn khoa học đã hướng dẫn tác giả hoàn thành luận văn này, xin được cảm ơn các thầy, cô giáo trường Đại học công nghệ thông tin và truyền thông nơi tác giả theo học và hoàn thành chương trình cao học đã nhiệt tình giảng dạy và giúp đỡ. Xin cảm ơn trường Cao đẳng Kinh tế - Tài chính Thái Nguyên nơi tác giả công tác đã tạo mọi điều kiện thuận lợi để tác giả hoàn thành chương trình học tập. Và cuối cùng xin cảm ơn gia đình, bạn bè, đồng nghiệp đã động viên, giúp đỡ tác giả trong suốt thời gian học tập, nghiên cứu và hoàn thành luận văn này. Xin chân thành cảm ơn. Thái Nguyên, ngày 18 tháng 5 năm 2017 Tác giả luận văn Nguyễn Quang Huy ii DANH SÁCH HÌNH VẼ 1.1 Vùng hút Lorenz . . . . . . . . . . . . . . . . . . . . . . . . 8 1.2 Vùng hút Rossler . . . . . . . . . . . . . . . . . . . . . . . 11 1.3 Vùng hút Rabinovich-Fabrikant . . . . . . . . . . . . . . . . 12 1.4 Vùng hút Mạch Chua . . . . . . . . . . . . . . . . . . . . . 13 1.5 Mô tả về sự phân tách quỹ đạo . . . . . . . . . . . . . . . . 15 1.6 Mô tả về sự thay đổi của hình cầu điều kiện ban đầu qua ánh xạ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.7 Vùng ổn định của phương pháp RK4 . . . . . . . . . . . . . 18 1.8 Biểu đồ hội tụ của phương pháp Euler và phương pháp RK4. 21 2.1 Mô tả quá trình phân tách quỹ đạo khi có nhiễu nhỏ ban đầu 32 3.1 Không gian pha của hệ Rabinovich - Fabrikant với a = 0.1, b = 0.98 và giá trị ban đầu [0.1, 0.1, 0.1]. Hệ là hỗn loạn. 41 3.2 Không gian pha của hệ Rabinovich - Fabrikant với a = 0.1, b = 0.2715 và giá trị ban đầu [0.1, 0.1, 0.1]. Hệ không là hỗn loạn. . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.3 Không gian pha của hệ Rabinovich - Fabrikant với a = 0.1, b = 0.5 và giá trị ban đầu [0.1, 0.1, 0.1]. Hệ không là hỗn loạn. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.4 Không gian pha của hệ Rabinovich - Fabrikant với a = −1, b = −0.1 và giá trị ban đầu [0.1, 0.1, 0.1]. Hệ là hỗn loạn. 42 iii DANH SÁCH BẢNG 1.1 Tỷ số khó trung bình của các hệ nghiên cứu trong luận văn 2.1 Bảng Butcher dạng tổng quát. . . . . . . . . . . . . . . . . 23 2.2 Bảng butcher của phương pháp Euler. . . . . . . . . . . . . 23 2.3 Bảng Butcher của phương pháp RK4 2.4 Bảng Butcher của phương pháp RK ẩn hai giai đoạn . . . . 25 2.5 Bảng Butcher của phương pháp IRK8 . . . . . . . . . . . . 27 2.6 Các hệ số trong bảng Butcher của IRK8. . . . . . . . . . . 27 3.1 Số mũ Lyapunov của các hệ theo các tài liệu đã công bố . . 38 3.2 Tính toán số mũ Lyapunov của hệ Lorenz . . . . . . . . . . 38 3.3 Tính toán số mũ Lyapunov của hệ Rossler . . . . . . . . . . 40 3.4 Tính toán số mũ Lyapunov của hệ RF . . . . . . . . . . . . 40 3.5 Tính toán số mũ Lyapunov lớn nhất của mạch Chua . . . . 42 iv 19 . . . . . . . . . . . . 24 DANH MỤC KÝ HIỆU, TỪ VIẾT TẮT R Tập hợp số thực. Z Tập hợp số nguyên. C Tập hợp số phức. Rn Không gian Euclide n chiều. C k ||.|| ẋ Không gian các hàm có đạo hàm cấp k liên tục. Chuẩn Euclide. Đạo hàm cấp 1 của hàm x theo biến độc lập (t). J Ma trận Jacobi của hàm véc tơ . O(ε) Vô cùng bé bậc cao hơn ε khi ε → 0. RF Hệ Rabinovich-Fabrikant Odinary Difference Equations: Hệ ODEs phương trình vi phân thường 4th order Runge -Kutta method: RK4 Phương pháp Runge Kutta bậc 4. 8th order Implicit Runge - Kutta IRK8 method: Phương pháp RK ẩn bậc 8. OS Orbit separation: Phân tách quỹ đạo Continuos Gram-Schmidt Orthonor- CGSO mation: Trực chuẩn Schmidt liên tục. v hóa Gram MỤC LỤC Lời cam đoan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i Lời cảm ơn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Danh sách hình vẽ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Danh sách bảng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii Danh mục ký hiệu, từ viết tắt . . . . . . . . . . . . . . . . . . . v Mở đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Chương 1. MỘT SỐ KIẾN THỨC CHUẨN BỊ . . . . . . . . . . . . . 6 1.1. Hỗn loạn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2. Các hệ động lực sử dụng . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.3. Số mũ Lyapunov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.4. Một số tính chất của phương pháp giải số . . . . . . . . . . 16 Chương 2. PHƯƠNG PHÁP RUNGE-KUTTA VÀ THUẬT TOÁN TÍNH SỐ MŨ LYAPUNOV . . . . . . . . . . . . . . . . . . . . 22 2.1. Phương pháp Runge-Kutta . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.2. Các thuật toán tính số mũ Lyapunov . . . . . . . . . . . . . . . 30 Chương 3. CÀI ĐẶT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.1. Kết quả tính toán với hệ Lorenz. . . . . . . . . . . . . . . . . . . . 37 3.2. Kết quả tính toán với hệ Rossler . . . . . . . . . . . . . . . . . . . 39 3.3. Tính toán số mũ Lyapunov của hệ RK . . . . . . . . . . . . . 40 3.4. Kết quả tính toán số mũ Lyapunov của mạch Chua . 41 Kết luận chung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 vi Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 PHỤ LỤC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 vii MỞ ĐẦU Với sự hỗ trợ của máy tính, rất nhiều các bài toán trong lĩnh vực khoa học kĩ thuật đã được nghiên cứu giải quyết, đưa ra lời giải số trong thời gian phù hợp và độ chính xác cao. Nói riêng với hệ phương trình vi phân thường, việc nghiên cứu tìm nghiệm số lại càng trở nên quan trọng. Điều này bắt nguồn từ hai lý do: Thứ nhất, từ khi được phát minh bởi nhà toán học Newton, phép tính vi tích phân nói chung và phương trình vi phân nói riêng là công cụ chủ yếu để mô hình hóa toán học các bài toán thực tế. Không chỉ giải quyết các bài toán cơ học Newton như giai đoạn đầu, ngày nay các bài toán vật lý về quá trình khuyếch tán, truyền nhiệt đến các bài toán dự báo thời tiết, kinh tế, sinh học,.., đều cần đến phương trình vi phân. Nói một cách ngắn gọn, mọi quá trình biến đổi liên tục theo thời gian của đối tượng nghiên cứu đều cần đến phương trình vi phân để mô hình hóa toán học. Thứ hai, việc tìm nghiệm giải tích của phương trình vi phân không hề đơn giản. Chỉ một số ít các phương trình vi phân có dạng đặc biệt mới có thể tìm nghiệm rõ với các phương pháp, kỹ thuật dành riêng cho dạng đó. Trong khi đó các bài toán xuất phát từ nhu cầu thực tế, sau quá trình áp dụng các định luật, mô hình hóa, nhận được hệ phương trình vi phân mô tả bài toán thường rất phức tạp. Các kết quả giải tích về hệ nhận được có thể là tính tồn tại, duy nhất nghiệm, sự ổn định của nghiệm,v.v.. nhưng muốn có nghiệm ta phải bắt tay vào giải số. Vì các lý do đó, nghiên cứu giải số hệ phương trình vi phân đã sớm được quan tâm bởi rất nhiều nhà toán học và còn tiếp tục phát triển. Một số thuật toán hiệu quả, 1 có độ chính xác cao, được áp dụng rộng rãi như: Phương pháp Newton, phương pháp Euler, phương pháp Runge Kutta. Gần đây khoa học về hỗn loạn (Chaos theory) đã thu hút được sự quan tâm lớn của các nhà nghiên cứu. Sự tồn tại một hành vi kỳ lạ của hệ tất định ngoài các hành vi quen thuộc như ổn định, tuần hoàn, tựa tuần hoàn với số chu kỳ lớn, thực ra đã thu hút sự chú ý của những nhà toán học lớn, có tư duy vượt thời đại như Henry Poincare từ đầu thế kỷ 20. Khi nghiên cứu bài toán ba vật thể nổi tiếng, ông đã nhận thấy những dấu hiệu của hỗn loạn. Nhưng phải đến năm 1963 hỗn loạn mới thực sự trở thành đối tượng nghiên cứu được quan tâm. Edwat Lorenz, nhà toán học và khí tượng học nổi tiếng của MIT, đã phát hiện hệ 12 phương trình vi phân dùng để mô tả, dự báo khí tượng của ông có một hành vi kỳ lạ. Một sự thay đổi vô cùng nhỏ của điều kiện ban đầu đã dẫn đến sự phân tách vô cùng lớn của nghiệm. Ngày nay chúng ta đã biết đó là sự phụ thuộc nhạy cảm vào điều kiện ban đầu, hiện tượng ông phát hiện được gọi là hiệu ứng cánh bướm. Lý thuyết hỗn loạn đã có nhiều ứng dụng trong việc mô tả chính xác tự nhiên cũng như các lĩnh vực khoa học. Mặc dù có nhiều định nghĩa khác nhau về hỗn loạn song tất cả các định nghĩa đó đều có chung một điểm là tồn tại sự phụ thuộc nhạy cảm vào điều kiện ban đầu của nghiệm. Số mũ Lyapunov là một khái niệm để “đo” sự phụ thuộc nhạy cảm này. Một hệ động lực nếu tồn tại số mũ Lyapunov dương chứng tỏ sự phân tách theo thời gian hàm mũ của quỹ đạo nghiệm với những thay đổi rất nhỏ của điều kiện ban đầu, hay tồn tại sự phụ thuộc nhạy cảm vào điều kiện ban đầu. Nó là dấu hiệu cho thấy hệ hỗn loạn. Với ý nghĩa quan trọng đó của số mũ Lyapunov, việc nghiên cứu tính toán số mũ Lyapunov rất được quan tâm. Các thuật toán nổi tiếng như tính số mũ Lyapunov chuỗi thời gian 2 của Gencay hay tính số mũ Lyapunov khi biết hệ phương trình vi phân mô tả hệ động lực của Wolf. Với hai vấn đề nêu ở trên, luận văn này sẽ nghiên cứu thuật toán Runge-Kutta giải số hệ phương trình vi phân để từ đó ứng dụng tính số mũ Lyapunov của hệ động lực được mô tả bởi hệ phương trình vi phân. Hai thuật toán tính số mũ Lyapunov sẽ được nghiên cứu cài đặt trên cơ sở sử dụng phương pháp Runge – Kutta là: Phương pháp phân tách quỹ đạo dùng để tính số mũ Lyapunov lớn nhất; Phương pháp trực chuẩn hóa liên tục Gram – Schmidt tính tất cả số mũ Lyapunov của hệ. Việc nghiên cứu thành công luận văn, xây dựng được chương trình tính số mũ Lyapunov đã giúp cho tác giả được bổ sung thêm kiến thức cơ sở toán học cho chuyên ngành khoa học máy tính và nâng cao kiến thức cho bản thân, đóng góp thêm một công cụ hữu ích trong quá trình khảo sát hành vi hệ động lực, một đối tượng rất được quan tâm nghiên cứu hiện nay. Nội dung của luận văn gồm 3 chương: Chương 1. Một số kiến thức chuẩn bị. Chương này trình bày các kiến thức chuẩn bị cho việc nghiên cứu. Đó là các khái niệm liên quan đến hỗn loạn như phụ thuộc nhạy cảm vào điều kiện ban đầu, số mũ lyapunov; Các kiến thức mang tính chất giới thiệu về các hệ động lực được sử dụng trong luận văn như hệ Lorenz, hệ Chua, hệ Rossler, hệ Ranbikovich-Fabrikant; Các tính chất của phương pháp giải số như tính ổn định, độ phức tạp, độ khó, độ chính xác của phương pháp. Các nội dung này được trình bày trong các phần sau: 1.1 Hỗn loạn. 1.2 Các hệ động lực sử dụng. 1.3 Số mũ Lyapunov. 3 1.4 Một số tính chất của phương pháp giải số. Chương 2. Phương pháp Runge-Kutta và thuật toán tính số mũ Lyapunov. Nội dung chương 2 tập trung vào hai vấn đề sau: Phương pháp Runge – Kutta giải hệ phương trình vi phân thường và hai thuật toán tính số mũ lyapunov. Cụ thể như sau: 2.1 Phương pháp Runge-Kutta. 2.2 Các thuật toán tính số mũ Lyapunov. Chương 3. Cài đặt và đánh giá kết quả. Sau khi nắm rõ các nội dung trong chương 2, chương 3 trình bày kết quả cài đặt thử nghiệm tính số mũ Lyapunov cho bốn hệ động lực đã nêu. Kết quả sẽ được phân tích, đánh giá, so sánh theo một số tiêu chí. Ngoài ra việc ứng dụng của hệ hỗn loạn trong mã hóa ảnh số cũng được nêu ra và phân tích trong chương này. 3.1 Hệ Lorenz 3.2 Hệ Rossler 3.3 Hệ Ranbinovich-Fabrikant 3.4 Mạch Chua. Kết quả thực hiện cài đặt thuật toán đã thể hiện đúng hành vi của các hệ đã cho như các nghiên cứu trước đây. Các kết quả phân tích so sánh cũng cho thấy sự hiệu quả của phương pháp. Sự liên quan của Số mũ Lyapunov và hành vi của nghiệm đến tham số của hệ và số các giá trị ban đầu cho trước cũng sẽ được chỉ ra. Phần mô tả ứng dụng cũng có một số phân tích cho thấy hiệu quả mã hóa bảo mật thông tin ảnh của hệ hỗn loạn. 4 Phần kết luận: Trình bày kết quả mà luận văn đạt được và hướng phát triển. Ngoài ra, các hàm và chương trình lập trình sử dụng ngôn ngữ Matlab sẽ được trình bày trong phần phụ lục. 5 CHƯƠNG 1 MỘT SỐ KIẾN THỨC CHUẨN BỊ Trình bày kiến thức chuẩn bị, các khái niệm liên quan đến hỗn loạn như phụ thuộc nhạy cảm vào điều kiện ban đầu, số mũ Lyapunov; Các kiến thức mang tính chất giới thiệu về các hệ động lực được sử dụng trong luận văn như hệ Lorenz, hệ Chua, hệ Rossler, hệ RabinovichFabrikant; Các tính chất của phương pháp giải số như tính ổn định, độ phức tạp, độ khó, độ chính xác của phương pháp. 1.1. Hỗn loạn Lý thuyết hỗn loạn là một nhánh của toán học, được biết đến rộng rãi hiện nay nhờ sự khó dự đoán của mô hình dự báo thời tiết [6] và mô hình tăng trưởng của quần thể sinh học [13]. Một tính chất quan trọng của hệ hỗn loạn là nhạy cảm với các điều kiện ban đầu. Định nghĩa 1.1.1. Sự phụ thuộc nhạy cảm vào điều kiện ban đầu: Sự thay đổi rất nhỏ trong điều kiện ban đầu của hệ sẽ dẫn tới sự thay đổi to lớn trong nghiệm. Khái niệm này có nghĩa là những lỗi rất nhỏ sẽ tăng theo thời gian và cuối cùng làm nghiệm sai lệch hoàn toàn, vô giá trị. Những lỗi vô cùng nhỏ không thể tránh khỏi khi dùng dấu phẩy động thay thế cho đầu vào chính xác, sẽ phát triển theo thời gian và làm mô hình mô phỏng không còn chính xác nữa. Không có định nghĩa phổ quát được chấp nhận cho sự hỗn loạn, mặc dù hầu hết các định nghĩa đều nhắc đến sự phụ thuộc nhạy cảm vào điều kiện ban đầu. Một số tác giả chỉ yêu cầu điều kiện nhạy cảm với đk ban đầu [5], trong khi một số khác lại yêu cầu một số điều kiện khác nữa [12], [27], [4]. Luận văn này tìm hiểu về số mũ Lyapunov của hệ, 6 dùng để đo sự phân tách của nghiệm dựa trên sự thay đổi nhỏ của điều kiện ban đầu. Số mũ Lyapunov là một phương pháp để nghiên cứu sự nhạy cảm với điều kiện ban đầu. Tính toán số mũ Lyapunov cho phép chúng ta xác định được hệ là hỗn loạn dựa trên định nghĩa của Alligood [5]. Trước khi thảo luận về số mũ Lyapunov và các phương pháp để tính toán nó, một số kiến thức liên quan được trình bày. Một Hệ động lực là một hệ phương trình mô tả sự biến đổi theo thời gian. Nó có thể là hệ các phương trình sai phân rời rạc hoặc các phương trình vi phân liên tục. Hệ động lực có thể mô tả các hiện tượng thực tế như mô hình thời tiết hay sự tăng trưởng của các quần thể theo thời gian [23], [28], [2]. Các phương trình sai phân mô tả sự biến đổi trạng thái theo thời gian còn được gọi là các ánh xạ (map) và các phương trình vi phân gọi là các luồng (flow). Quỹ đạo hay đường đi mô tả sự phát triển theo thời gian của trạng thái (nghiệm) của hệ động lực. Một quỹ đạo với véc tơ ban đầu v0 của hệ động lực F có nghiệm số ft (vi ) tại thời gian ti , t0 ≤ ti ≤ tF inal , là: OF = {ft (v0 ) : t ∈ [t0 , tF inal ]} (1.1.1) Mọi hệ động lực chúng ta xét sẽ là các hệ phi tuyến, chỉ những hệ phi tuyến mới có thể xuất hiện hiện tượng hỗn loạn. Theo tiến trình thời gian, quỹ đạo có thể tiệm cận đến một giá trị hữu hạn, bị giữ trong một vùng cụ thể hay dần tới vô cùng. Ví dụ, với phương trình sai phân (1.1.2), xn+1 = xn 2 (1.1.2) Quỹ đạo xuất phát với x0 = 2 sẽ tăng, không bị chặn; Nhưng với điều kiện ban đầu x0 = 0.5, quỹ đạo tương ứng sẽ hội tụ về 0, bị giữ trong vùng giữa 0 và 0.5 với mọi thời gian. Một điểm xi được gọi là điểm 7