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.1) hoặc dạng autonom: y0 (t) = f (y(t)), y(t0 ) = y0 , t0 6 t 6 T, (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. Đị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.
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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 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: s X Yn,i = yn + h aij f (tn + cj h, Yn,j ), i = 1, .3a) j=1 Xs yn+1 = yn + h bj f (tn + cj h, Yn,j ).3b) j=1 trong đó A = (aij )s×s và các vectơ s chiều c = (c1 , ., 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. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 13 Ta giả sử điều kiện: s X s X ci = aij , i = 1, s và điều kiện bi = 1 (1.4) j=1 i=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. hay bT cs as1 as2.
bs Đặt Yn = [Yn,1 ,. , 1]T ∈ Rs là các vectơ s chiều.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 ). 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. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.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.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 .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]).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,. Cấp chính xác nấc địa phương là q + 1. Đặt 1 B(w) : bT cp−1 = , p = 1,. p 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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.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.2 Cấp chính xác nấc lớn nhất của phương pháp Runge- Kutta s nấc là s.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 Runge- Kutta (1.4 Miền ổn định của phương pháp Runge-Kutta (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.
LUAN VAN CHAT LUONG download : add luanvanchat@agmail.199]) Hàm ổn định R(z) của phương pháp Runge- Kutta (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.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. 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 17 đầu tiên cố gắng xây dựng các phương pháp ERK có cấp chính xác cao và đã thu được một số kết quả sau (xem [13, 14, 15],[7, tr.1 Không tồn tại phương pháp Runge-Kutta hiển s nấc có cấp chính xác p = s với p ≥ 5.2 Không tồn tại phương pháp Runge-Kutta hiển s nấc có cấp chính xác p mà p + δ = s (δ = 1 hoặc δ = 2) với p ≥ 6 + δ.
Phương pháp ERK 6 nấc có cấp chính xác 5 và phương pháp ERK 7 nấc có cấp chính xác 6 được đưa ra bởi Butcher (1964) (xem [12]). Phương pháp ERK 11 nấc có cấp chính xác 8 được đưa ra bởi Curtis (1970), Cooper và Verner(1972) ([17, tr. Trong mỗi trường hợp các hoành độ dựa trên công thức cầu phương Lobatto với 3 điểm. Các phương pháp có cấp chính xác bằng 9 đã không thu hút được nhiều sự quan tâm và không biết trên thực tế cần bao nhiêu nấc để có được cấp chính xác này.
Phương pháp có cấp chính xác 10 với 18 nấc đã được đưa ra bởi Curtis năm 1975 [36]. Tuy nhiên, với sự kết hợp khéo léo các giả định đơn giản khác nhau, Hairer (1978) đã đưa ra được phương pháp có cấp chính xác 10 với 17 nấc (xem [39]). Và hiện tại, vẫn chưa có phương pháp nào được đưa ra với số nấc ít hơn.1 dưới đây cho ta mối quan hệ giữa cấp chính xác p, số nấc lý thuyết và số nấc thực tế nhận được.1: Cấp chính xác của các phương pháp ERK Cấp chính xác p 1 2 3 4 5 6 7 8 9 10 s lý thuyết 1 2 3 4 6 7 9 11 ≥ 12 ≥ 13 s thực tế 1 2 3 4 6 7 9 11 - 17 Các phương pháp ERK thường được xây dựng dưới dạng phương pháp kẹp thêm (embeded methods) để thuận lợi trong việc đánh giá sai số địa phương khi áp dụng chúng với bước lưới thay đổi tự động. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.