ĐẠ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
- Xem thêm -