TRƯỜNG ĐẠI HỌC CẦN THƠ Khoa Khoa Học Tự Nhiên Nguyễn Hồng Thơng GIẢI SỐ PHƯƠNG TRÌNH VI PHÂN VỚI CÁC PHƯƠNG PHÁP EULER VÀ RUNGE-KUTTA y 0.5 1.0 1.5 2.0 LUẬN VĂN TỐT NGHIỆP Người hướng dẫn: Lê Phương Quân 2010 2.5 t Lời nói đầu Trước tiên, xin gởi lời cám ơn chân thành sâu sắc đến Thầy Lê Phương Quân (Khoa Khoa Học Tự Nhiên) Lịng nhiệt tình động viên Thầy giúp em vượt qua khó khăn để hoàn thành Luận Văn Đặc biệt, em xin cám ơn Thầy hỗ trợ nhiệt tình cho em việc soạn thảo văn báo cáo LATEX Xin gởi lời cám ơn chân thành đến Cô cố vấn học tập Dương Thị Tuyền, người khuyến khích em làm Luận Văn thay đăng ký học Học Phần thay Xin chân thành cám ơn Thầy Cô bạn bè cho lời nhận xét quý báu để em hồn thiện thêm nội dung cịn thiếu sót Luận Văn mở hướng nghiên cứu tương lai sau trường Xin chân thành cám ơn Thầy Cô tất bạn bè Trường Đại Học Cần Thơ, người giảng dạy, hướng dẫn giúp đỡ em suốt bốn năm học vừa qua Chúc Thầy Cô bạn bè dồi sức khỏe hoàn thành tốt nhiệm vụ Cuối cùng, xin bày tỏ nơi lịng biết ơn vơ hạn em đến người thân gia đình, người ln có mặt bên em thời khắc! Cần Thơ, ngày 09 tháng 02 năm 2010, Nguyễn Hồng Thơng (Lớp Tốn Thống Kê K32 ) Lời nói đầu Giới thiệu Phương pháp Runge-Kutta biết từ lâu, lần đầu tiên, ý tưởng phương pháp Runge đề xuất vào năm 1895! Nhưng đến gần đây, am hiểu có tính chất lý thuyết chúng làm rõ hơn, chủ yếu qua cơng trình John Butcher (xem [2]) Như thường thấy tiến khoa học tính tốn, lý thuyết nâng cao đưa đến thuật toán tốt hơn, đến lượt chúng lại đưa đến thấu hiểu cấu trúc lý thuyết tiềm ẩn tiếp tục Các phương pháp số để giải phương trình hay hệ phương trình vi phân nói chung, thường gọi tắt giải số phương trình vi phân, có mối liên hệ chất với phép cầu phương, thực chất phép xấp xỉ tích phân (xem [1]) Mối liên hệ tự nhiên tồn toán giá trị ban đầu phương trình vi phân tương đương với phương trình tích phân Với quan điểm tồn cục vậy, phương pháp Runge-Kutta trình bày cách tự nhiên dạng lược đồ xấp xỉ tích phân Trong đó, phương pháp Runge-Kutta dạng hiện, xuất trước trình bày thể phép cầu phương đơn giản thuận tiện mặt tính tốn Nghiệm số yn , xấp xỉ giá trị nghiệm y(tn ), mức độ xác thường gọi có bậc p ta có ước lượng y(tn + h) − yn+1 ≤ Khp+1 , h cỡ bước K phụ thuộc vào kiện toán Về mặt kỹ thuật, lược đồ Runge-Kutta dạng áp dụng để tính giá trị yn+1 nghiệm số toán y = f (t, y), y(t0 ) = y0 , (1) biết yn Khi đó, yn+1 xác định sau ν-chặng η = yn , η = yn + ha21 f (tn , η ), η = yn + ha31 f (tn , η ) + ha32 f (tn + c2 h, η ), (2) ν−1 η ν = yn + h aνi f (tn + ci h, η i ), i=1 ν yn+1 = yn + h bj f (tn + cj h, η j ) (3) j=1 Về mặt lý thuyết, ta chứng minh rằng: với ν ≤ 4, lược đồ ν-chặng cung cấp nghiệm xấp xỉ có bậc ν Đối với bậc cao hơn, số chặng cần thiết để lược đồ đạt Giới thiệu bậc tương ứng phải lớn số bậc, lại không theo quy luật định Chẳng hạn, lược đồ cần đến 6-chặng để có bậc 7-chặng để có bậc Năm 1965, Butcher chứng minh rằng: với p ≥ 7, không tồn phương pháp Runge-Kutta dạng bậc p có ν = p + 1-chặng Đến 20 năm sau, 1985, Butcher chứng minh kết quả: với p ≥ 8, không tồn phương pháp Runge-Kutta dạng bậc p với ν = p + 2-chặng! Lược đồ dạng Kutta tổng quát hóa lần vào năm 1901, 60 năm sau (1964), Butcher vén lên nhung để người ta thấy vẻ đẹp phương pháp Runge-Kutta Đặc biệt, Kutta giá trị thỏa điều kiện bậc với 4-chặng, c1 = 0, a43 = 1, c2 = c3 = 1/2, a21 = a32 = 1/2, c4 = 1, b1 = 1/6, b2 = b3 = 1/3, b4 = 1/6, a31 = a41 = a42 = (4) Với giá trị cho (4), lược đồ (2) (3) (với ν = 4) viết thành: k = f t n , yn h, yn 2 hk2 k2 = f tn + h, yn + hk1 k = f tn + + (5) k4 = f tn + h, yn + hk3 yn+1 = yn + h (k1 + 2k2 + 2k3 + k4 ) (6) Ngày nay, (5) (6) gọi chung công thức RK4 hình thức này, “thuật toán” vừa đẹp, vừa đơn giản, vừa thuận tiện cho ngơn ngữ lập trình tính tốn nào; nữa, có đến bậc 4, cơng thức Euler có bậc 1! Có thể có nhiều cách chọn khác để có cơng thức bậc với 4-chặng, cách chọn Kutta xem “hồn hảo” Đối với tốn (1) có tính ổn định, cơng thức RK4 gần lựa chọn khơng có địi hỏi q khắt khe độ xác nghiệm số Trong tài liệu có phương pháp giải số phương trình vi phân, kể sách chuyên khảo đề tài John Butcher, việc “chứng minh cơng thức xấp xỉ nghiệm RK4 có bậc 4” khơng trình bày Hầu hết nói phức tạp tính tốn, dù khơng q khó, để trình bày chi tiết đầy đủ khuôn khổ trang vốn dành để nói nhiều khía cạnh khác phương pháp Runge-Kutta Trong [1], Arieh Iserles, chuyên gia hàng đầu giải số phương trình vi phân nói: “Việc nhận cơng thức bậc không vượt khả khai triển thành chuỗi Taylor, dù điều cần đến kiên trì tính cẩn trọng.” Những nhận xét điểm xuất phát cho Luận Văn Sự háo hức tìm lại đường đưa đến cơng thức tiếng RK4 cảm xúc ban đầu người thực Luận Văn thầy hướng dẫn đặt vấn đề cần giải Và trình thực hiểu rõ lý người ta nói q trình tính tốn để nhận cơng thức đẹp đẽ Ngồi mục tiêu chứng minh cơng thức RK4 có bậc 4, Luận Văn cịn tập trung chứng minh làm rõ số vấn đề khác có liên quan đến bước xây dựng phép cầu phương có bậc cao Các phép cầu phương thiết lập lược đồ Runge-Kutta dạng ẩn, dạng đặc biệt hiệu cho tốn dạng (1) khơng có tính ổn định Những vấn đề yêu cầu làm rõ (a) Dùng Định lý Nhân Peano để chứng minh cơng thức cầu phương có bậc p Giới thiệu (b) Chứng minh Định lý 2.3, kết bậc cụ thể dạng cầu phương có liên quan đến khơng điểm đa thức trực giao (c) Phân tích khái niệm luồng tài liệu [3] để mô tả chi tiết ni dung ca B AlekseevGrăobner v ỏnh giỏ sai số tồn cục, sở quan trọng để chứng minh Định lý 3.2 Mặc dù chương trình tính tốn nghiệm số theo cơng thức RK4 viết ngơn ngữ Maple q trình thực Luận Văn này, việc tính tốn cho lược đồ có bậc cao mục tiêu đáng để theo đuổi Đặc biệt, việc xây dựng thuật toán cụ thể cho lược đồ bậc 5, bậc bậc chương trình tính tốn tương ứng hiển nhiên cơng việc không đơn giản, không phần hấp dẫn Hơn nữa, việc tính tốn đạo hàm cấp cao lại liên quan đến lý thuyết đồ thị rõ [1], [2] [5] Sự liên kết thú vị dường tất nhiên chắn vấn đề nên tìm hiểu thấu đáo Trong Luận Văn có sử dụng số thuật ngữ dịch từ tiếng Anh Ngoài tham khảo cách dùng từ phổ biến, việc chọn từ lưu ý đến nội dung kiến thức liên quan nên chắn mang tính chủ quan Vì vậy, Danh sách thuật ngữ cung cấp Luận Văn mong muốn góp ý cách dùng từ sát hợp chuẩn mực Giới thiệu Danh sách thuật ngữ ν-stage: abscissa: candidate solution: collocation method: collocation parameter: defect: error: explicit Runge-Kutta scheme: flow map, flow: implicit Runge-Kutta scheme: linear functional: maximal integral curve: monic polynomial: multistep method: naăve rendition: order: orthogonal polynomial: Peano kernel: polygonal curve: quadrature: quadrature weight: quadrature node: Runge-Kutta tableau: scalar autonomous equation: simple zero: step size: the fundamental Theorem of Algebra: truncated power function: variation-of-constants formula: weight function: ν-chặng hoành độ nghiệm ứng viên phương pháp đặt tham số định vị độ lệch sai số lược đồ RK dạng ánh xạ luồng, luồng lược đồ RK dạng ẩn phiếm hàm tuyến tính đường cong tích phân tối đại đa thức đơn phương pháp đa bước khai triển thô bậc đa thức trực giao nhân Peano đường gấp khúc phép cầu phương trọng số cầu phương điểm nút cầu phương bảng RK phương trình vơ hướng tự điều chỉnh cực điểm đơn cỡ bước Định lý Đại số hàm lũy thừa chặt cụt công thức biến thiên số trọng hàm 10 Danh sách thuật ngữ 44 Chương Phương pháp Runge-Kutta Ta cần đến kết bổ trợ khác sau Bổ đề 3.2 Cho U V ma trận  a  UV = c vuông cấp cho  b a b d  , det c d 0 = Khi đó, ta có V e3 = U T e3 = 0, với e3 = (0, 0, 1)T Chứng minh Thật vậy, det U = U V e3 = nên V e3 = Nếu det U = tồn x = (x1 , x2 , x3 )T = cho U T x = Từ đó, suy V T U T x = hay (U V )T x = 0, nghĩa    a c x1  b d   x2  = 0 0 x3 Do kết tương đương với x1 = x2 = nên x bội e3 Bổ đề 3.3 Các phương trình (3.15) (3.9) suy (3.16) Chứng minh Đặt d2 = b3 a32 + b4 a42 − b2 (1 − c2 ), d3 = b4 a43 − b3 (1 − c3 ), d4 = −b4 (1 − c4 ) ta cần phải chứng minh d2 = d3 = d4 = Xét ma trận     b2 b3 b4 c2 c22 −c22 /2  a32 c2 − c23 /2 U =  b2 c2 b3 c3 b4 c4  , V =  c3 c23 2 c4 c4 a42 c2 + a43 c3 − c4 /2 d2 d3 d4 Khi đó, theo phương trình (3.15),  1/2 1/3 U V =  1/3 1/4 0 ta có  0 , 1/2 1/3 1/3 1/4 det = Do c2 = (theo (3.15h)) nên V e3 = vậy, theo Bổ đề 3.2, ta phải có U T e3 = 0, nghĩa d2 = d3 = d4 = Từ Bổ đề 3.1 Bổ đề 3.2, ta đến kết sau Định lý 3.1 Với giả thiết (3.9), phương trình hệ (3.15) tương đương với b1 + b2 + b3 + b4 = (3.17a) b2 c2 + b3 c3 + b4 c4 = 1/2 (3.17b) b2 c22 + b3 c23 + b4 c24 = 1/3 (3.17c) = 1/4 (3.17d) b3 c3 a32 c2 + b4 c4 (a42 c2 + a43 c3 ) = 1/8 (3.17e) b2 c32 + b3 c33 + b4 c34 b3 a32 + b4 a42 = b2 (1 − c2 ) (3.17f) b4 a43 = b3 (1 − c3 ) (3.17g) = b4 (1 − c4 ) (3.17h) 45 3.2 Phương pháp 4-chặng RK-h bậc bốn Từ (3.17g) (3.15h), ta suy b3 b4 c2 (1 − c3 ) = (3.18) Đặc biệt, từ điều kiện này, ta có c4 = 1, theo (3.17h) Ta biết c1 = c2 , c3 , b1 , b2 , b3 b4 chọn Kutta (1901) sau: c2 = c3 = , b1 = , b2 = b3 = , b4 = Khi bi ci chọn ta nhận a43 = từ (3.17g) Các phương trình (3.17e), (3.17f) lập thành hệ phương trình tuyến tính theo a32 , a42 có nghiệm a32 = 1/2 a42 = có định thức b3 b4 det = b3 b4 c2 (c4 − c3 ) = b3 c3 c2 b4 c4 c2 Cuối cùng, ta nhận a21 = 1/2, a31 = a41 = từ điều kiện (3.9) Khi đó, ta có bảng RK phương pháp 4-chặng RK-h bậc 4: 2 1 0 1 3 Vậy, đặt k1 := f (tn , yn ) từ lược đồ (3.6), cơng thức RK4 viết dạng: k1 = f tn , yn h, yn 2 hk2 k2 = f tn + h, yn + hk1 k3 = f tn + + (3.19) k4 = f tn + h, yn + hk3 yn+1 = yn + h (k1 + 2k2 + 2k3 + k4 ) (3.20) Thực chất, cơng thức thuật tốn viết cách dễ dàng thành chương trình tính tốn nghiệm số tốn dạng (2.1) Khi viết ngơn ngữ lập trình tính tốn hình thức phổ biến Maple hay Mathematica, cấu trúc thuật toán khơng có thay đổi phần chương trình Cơng thức RK4 có lẽ ln ưu tiên chọn lựa cho việc giải số tốn giá trị ban đầu hai đặc điểm bật: tính đơn giản thuật tốn độ xác cao Việc xác định nghiệm số thực việc tính giá trị hàm f cho số điểm khác mà thôi! Dưới đây, ta minh họa việc áp dụng công thức RK4 để giải số toán giá trị ban đầu phương trình vi phân cấp một, hệ phương trình vi phân cấp phương trình vi phân tuyến tính cấp cao Trước tiên, xét tốn giá trị ban đầu phương trình vi phân cấp một: y = y−3 − 2x2 + 5x, x y(1) = Đồ thị nghiệm số cho đường gấp khúc Hình 3.1 Vì cơng thức RK4 46 Chương Phương pháp Runge-Kutta y Đường gấp khúc Euler (h = 0.25) Đường gấp khúc Runge-Kutta (h = 0.25), đường cong nghiệm xác 2 x −1 Hình 3.1: Các đường gấp khúc Euler, RK4 đường cong nghiệm xác có độ xác cao nên điểm đường gấp khúc RK4 dường nằm đường cong nghiệm xác Xét hệ phương trình phi tuyến với ẩn hàm y1 = y1 (t) y2 = y2 (t), t ∈ [π/2, 5π/6]: y1 = y1 y2 , y2 = y1 y2 − y1 (π/2) = 1, y2 (π/2) = y22 , Với y := (y1 , y2 )T , f (t, y) := (y1 y2 , y1 y2 − y22 )T y0 := (1, 1)T , toán viết thành: y = f (t, y), y(π/2) = y0 Với h = 0, 02 N = 50, giá trị nghiệm xác y(t) = (y1 (t), y2 (t)), nghiệm xấp xỉ Y(t) = (Y1 (t), Y2 (t)) theo công thức RK4 sai số y − Y cho bảng sau: n ··· 46 47 48 49 50 y1 1.020202701 1.040821881 1.061874808 1.083379661 1.105355591 ··· 2.963918589 3.064758909 3.171975897 3.286217739 3.408223450 y2 1.000200033 1.000800534 1.001802704 1.003208556 1.005020918 ··· 1.650654883 1.695524422 1.743618399 1.795259466 1.850815718 Y1 1.020202700 1.040821880 1.061874807 1.083379659 1.105355589 ··· 2.963918531 3.064758843 3.171975821 3.286217652 3.408223349 Y2 1.000200033 1.000800533 1.001802703 1.003208555 1.005020918 ··· 1.650654862 1.695524397 1.743618371 1.795259433 1.850815679 y−Y 0.1000000000 × 10−8 0.1414213562 × 10−8 0.1414213562 × 10−8 0.2236067978 × 10−8 0.2000000000 × 10−8 ··· 0.6168468205 × 10−7 0.7057619995 × 10−7 0.8099382693 × 10−7 0.9304837452 × 10−7 0.1082681855 × 10−6 Xét toán giá trị ban đầu với ẩn hàm y = y(t), t ∈ [1, 2]: t2 y − 2ty + 2y = t3 ln t, y(1) = 1, y (1) = Đặt y1 = y, y2 = y tốn trở thành: y = f (t, y), y(1) = y0 , với f := y2 , (2/t)y2 − T (2/t2 )y1 + t ln t , y0 := (1, 0)T Với h = 0, 05 N = 20, giá trị nghiệm xác y(t), nghiệm xấp xỉ y(t) theo công thức RK4 sai số |y − y| cho bảng đây: 47 3.3 Lược đồ dạng ẩn phương pháp Runge-Kutta n 3 ··· 16 17 18 19 20 3.3 y 1.000000000 0.997521607 0.990178925 0.978123972 0.961525825 0.940569874 ··· 0.489985915 0.436343636 0.381987902 0.327279410 0.272588722 y 1.0000000000 0.9975215819 0.9901788755 0.9781238996 0.9615257300 0.9405697573 ··· 0.4899855823 0.4363432854 0.3819875340 0.3272790230 0.2725883180 |y − y| 0.000000000 0.2510 × 10−7 0.4950 × 10−7 0.7240 × 10−7 0.9500 × 10−7 0.1167 × 10−7 ··· 0.3327 × 10−6 0.3506 × 10−6 0.3680 × 10−6 0.3870 × 10−6 0.4040 × 10−6 Lược đồ dạng ẩn phương pháp Runge-Kutta Ý tưởng phương pháp Runge-Kutta dạng ẩn (RK-a) cho hàm vector η , η , , η ν phụ thuộc lẫn hệ tổng quát (3.1), đây: ν η j = yn + h aji f (tn + ci h, η i ), j = 1, 2, , ν, i=1 ν yn+1 = yn + h (3.21) bj f (tn + cj h, η j ) j=1 Lưu ý A = (aji )ν×ν ma trận tùy ý, trong (3.1) lại ma trận tam giác Các thuật ngữ điểm nút RK, trọng số RK giữ nguyên ý nghĩa Ta đặt thêm quy ước ν aji = cj , j = 1, 2, , ν, (3.22) i=1 điều kiện làm đơn giản điều kiện bậc phương pháp Thật vậy, từ lược đồ (3.21), ta viết: ν η j = yn + h aji f + O(h2 ), i=1 ν yn+1 = yn + h ν bj f + cj hft + h j=1 ν = yn + h aji fy f + O(h3 ) i=1 ν bj f + h ν bj cj ft + h 2 j=1 j=1 ν bj j=1 aji fy f + O(h3 ), (3.23) i=1 đó, f = f (tn , yn ), fy = fy (tn , yn ), ft = ft (tn , yn ) Nếu (3.22) thỏa (3.23) trở thành ν yn+1 = yn + h ν bj f + h2 j=1 bj cj j=1 ft + fy f + O(h3 ) 48 Chương Phương pháp Runge-Kutta Mặt khác, y = y(t) nghiệm xác (2.1), với điều kiện y(tn ) = yn , ta có khai triển Taylor quanh tn yn+1 = y(tn + h) = yn + hf + h2 ft + fy f + O(h3 ) Từ đó, ta nhận điều kiện để phương pháp (3.21) có bậc p ≥ đơn giản nhiều so với điều kiện tương ứng (3.22) không thỏa Mặc dù việc tính tốn cho (3.21) thử thách khác so với (3.1) phương pháp RK-h, lược đồ RK-a có thuận lợi quan trọng; đặc biệt, chúng có tính chất ổn định cao Hơn nữa, thấy phần sau, ν ≥ 1, tồn phương pháp RK-a có bậc 2ν, mở rộng tự nhiên công thức cầu phương Gauss Định lý 2.2 Để minh họa, ta thử xét phương pháp 2-chặng RK-a Xét lược đồ: η = yn + h f (tn , η ) − f tn + h, η , η = yn + h 3f (tn , η ) + 5f tn + h, η , 12 yn+1 = yn + h f (tn , η ) + 3f tn + h, η (3.24) Bảng RK tương ứng với (3.23) 4 − 14 12 Để khảo sát bậc (3.24), lần nữa, ta giả thiết phương trình vi phân xét vô hướng tự điều chỉnh Ngoài ra, trước, ta quy ước đại lượng tính yn Đặt k1 = f (η1 ) k2 = f (η2 ) theo (3.24), ta có η1 = y + 14 h(k1 − k2 ) + O(h2 ) η2 = y + 12 h(3k1 + 5k2 ) + O(h2 ) Từ đó, ta có 1 h(k1 − k2 ) + O(h2 ) , k1 = f (η1 ) = f + hfy (k1 − k2 ) + fyy 4 1 k2 = f (η2 ) = f + hfy (3k1 + 5k2 ) + fyy h(3k1 + 5k2 ) + O(h2 ) , 12 12 (3.25) vậy, k1 = f + O(h), k2 = f + O(h) Thay kết vào lại vế phải (3.25), ta viết k1 = f + O(h2 ), k2 = f + 32 hfy f + O(h2 ) Sau cùng, lại thay vào vế phải (3.25), ta nhận k1 = f − h2 fy2 f + O(h3 ), 2 k2 = f + hfy f + h2 fy f + fyy f + O(h3 ) 18 Vậy, thay vào phương trình cuối (3.24), ta có 1 yn+1 = yn + h(b1 k1 + b2 k2 ) = y + hf + h2 fy f + h3 fy2 f + fyy f + O(h4 ) Mặt khác, tn , ta có y = f , y = fy f , y tn (3.26) = fy2 f + fyy f khai triển nghiệm xác quanh 1 yn+1 = y(tn + h) = y + hf + h2 fy f + h3 fy2 f + fyy f + O(h4 ), 49 3.4 Sự xếp theo thứ tự phương pháp RK-a kết trùng với (3.26) Vậy, ta kết luận rằng: phương pháp (3.24) có bậc p ≥ (trên thực tế, bậc xác p = ta kiểm chứng điều xét lược đồ (3.24) cho phương trình y = y) Ta nhận cách hệ thống phương pháp RK-a có bậc cao cách vận dụng lý thuyết đồ thị (xem [1], [2] [4]) Nhưng ta không đề cập đến lý thuyết Tuy nhiên, tập quan trọng lược đồ RK-a xây dựng cách dễ dàng theo hướng tiếp cận khác mà không cần phải dùng khai triển cồng kềnh, phức tạp Đó chủ đề đoạn 3.4 Sự xếp theo thứ tự phương pháp RK-a Ta tạm thời bỏ qua phương pháp Runge-Kutta để xét hướng tiếp cận để xác định nghiệm số toán (2.1) Cũng phương pháp xét, ta giả sử tích phân xấp xỉ bước thứ n để có cặp xấp xỉ tương ứng cho nghiệm (tn , yn ) ta tìm cách xấp xỉ nghiệm đến bước (tn+1 , yn+1 ), với tn+1 = tn + h Với mục đích vậy, ta chọn ν tham số định vị phân biệt c1 , c2 , , cν (thường lấy [0, 1]) tìm đa thức u có bậc ν, với hệ số vector, cho u(tn ) = yn , u (tn + cj h) = f (tn + cj h, u(tn + cj h)), j = 1, 2, , ν (3.27) Theo đó, u thỏa điều kiện ban đầu nghiệm phương trình vi phân (2.1) ν điểm phân biệt Một phương pháp đặt việc tìm hàm u vậy, xác định yn+1 = u(tn+1 ) Phương pháp nghe hợp lý Vậy mà, ta khơng phải tìm thêm phương pháp có ý nghĩa khác với phương pháp xét Lý phương pháp đặt khơng khác phương pháp RK-a trá hình! Bổ đề cho ta lời giải thích Bổ đề 3.4 Đặt ν qk (t) := (t − ci ), k = 1, 2, , ν, i=1 i=k ˆ aji := cj ˆ bj := qi (t) dt, qi (ci ) qj (t) dt, qj (cj ) j, i = 1, 2, , ν, (3.28) j = 1, 2, , ν (3.29) Khi đó, phương pháp đặt (3.27) trùng với phương pháp RK-a có bảng RK tương ứng c A bT 50 Chương Phương pháp Runge-Kutta Chứng minh Trước hết, ta thấy đa thức ν q(t) := j=1 qj (t − tn )/h wj qj (cj ) thỏa q(tn + cj h) = wj , j = 1, 2, , ν Ta chọn wj = u (tn + cj h), j = 1, 2, , ν Do q u đa thức có bậc (ν − 1) trùng ν điểm nên ta phải có q ≡ u Vậy, áp dụng (3.27), ta có ν u (t) = i=1 qi (t − tn )/h u (tn + ci h) = qi (ci ) ν i=1 qi (t − tn )/h f (tn + ci h, u(tn + ci h)) qi (ci ) (3.30) Lấy tích phân (3.30) từ tn đến t ý u(tn ) = yn , ta nhận được: ˆ ν u(t) = yn + h f (tn + ci h, u(tn + ci h)) i=1 (t−tn )/h qi (τ ) dτ qi (ci ) (3.31) Bây giờ, đặt η j := u(tn + cj h), j = 1, 2, , ν, cho t = tn + cj h (3.31), để ý đến (3.28), ta đến: ν η j = yn + h aji f (tn + ci h, η i ), j = 1, 2, , ν i=1 Cuối cùng, cho t = tn+1 (3.31) (3.29), ta có ν yn+1 = u(tn+1 ) = yn + h bj f (tn + cj h, η j ) j=1 Vậy, ta nhận lại lược đồ (3.21) chứng tỏ (3.27) phương pháp RK-a Chú ý Không phải phương pháp Runge-Kutta bắt nguồn từ phương pháp đặt Thật vậy, với ν = c1 = 0, c2 = 2/3, theo Bổ đề 3.4, ta lập đa thức q1 (t) = t − (2/3), q2 (t) = t dễ thấy (3.28), (3.29) sinh phương pháp RK-a với bảng RK tương ứng 0 3 3 Tuy nhiên, khơng phải phương pháp RK-a (3.24) xét với giá trị ν = 2, c1 = c2 = 2/3! Các phương pháp đặt trường hợp RK-a đặc biệt mà chúng dành cho mục đích ý định dường thích hợp với phương pháp RK-a (3.21), chừng mà cịn phải thực việc tính tốn thực tế Một thuận lợi (3.27) đặc biệt thích hợp cho việc phân tích hạn chế khai triển phức tạp, cồng kềnh Theo nghĩa đó, phương pháp đặt người thừa kế đích thực cơng thức cầu phương Trước hiểu rõ lợi ích từ lược đồ (3.27), ta cần phải giới thiệu kết quan trọng ước lượng sai số nghiệm số Đây trường hợp mà ta có nghiệm ứng viên đủ trơn, chẳng hạn v, cho tốn (2.1) Thơng thường, nghiệm sinh lô kỹ thuật xấp xỉ cách mở rộng (chẳng hạn phép nội suy) 51 3.4 Sự xếp theo thứ tự phương pháp RK-a nghiệm số từ lưới toàn khoảng xét hay cách thiết lập phương pháp số “liên tục”, mà phép đặt (3.27) trường hợp Với v nghiệm vậy, ta tính độ lệch: d(t, v) := v (t) − f (t, v(t)) Hiển nhiên tồn mối liên hệ độ lớn độ lệch sai số v(t) − y(t): d(t, y) ≡ nên ta mong đợi giá trị nhỏ d(t, v) để suy sai số nhỏ Mối liên hệ quan trọng vì, khơng giống sai số, ta tính độ lệch mà khơng cần biết nghiệm xác y Đối với phương trình tuyến tính vấn đề trở nên đơn giản Thật vậy, giả sử y = Ay, y(t0 ) = y0 , (3.32) với A ma trận Nếu d(t) := v − Av ta có tốn phương trình vi phân tuyến tính khơng nhất: v = Av + d(t), t ≥ t0 , v(t0 ) = v0 cho Khi đó, hiển nhiên nghiệm tốn cho cơng thức, thường gọi công thức biến thiên số : ˆ t A(t−t0 ) eA(t−τ ) d(τ )dτ, t ≥ t0 , v(t) = e v0 + t0 nghiệm (3.32) rõ ràng y(t) = eA(t−t0 ) y0 , Từ đó, suy ra: t ≥ t0 ˆ v(t) − y(t) = eA(t−t0 ) (v0 − y0 ) + t eA(t−τ ) d(τ )dτ, t ≥ t0 t0 Vậy, sai số biểu diễn hồn toàn theo số hạng “biết được” v0 − y0 d Bởi nghiệm xác phương trình tuyến tính (3.32) xác định nên ta dễ dàng thiết lập mối liên hệ sai số độ lệch Trong trường hợp phi tuyến, cơng thức biến thiên số thit lp nh B Alekseev-Grăobner, cho dự mt dạng yếu so với trường hợp tuyến tính Theo ý nghĩa ký hiệu dùng so sánh với ký hiệu Bổ đề 1.1, ta viết ˆ t ˆ t τ v(t) − y(t) = DΦt (v(τ ))d(τ, v)dτ = DΦ(t, τ, v(τ ))d(τ, v), t ≥ t0 (3.33) t0 t0 Nói chung, ma trận DΦ chưa biết ước lượng cách hiệu kiểm sốt sai số thực tế Nhưng ta khơng xét vấn đề may mắn ta không cần biết DΦ vấn đề quan tâm Định lý 3.2 Giả sử ta có ˆ q(τ )τ j dτ = 0, j = 0, 1, , m − 1, (3.34) với m ∈ {0, 1, , ν} q(t) = ν + m ν i=1 (t − ci ) Khi đó, phương pháp đặt (3.27) có bậc 52 Chương Phương pháp Runge-Kutta Chứng minh Với t0 , t thay tn tn+1 , nghiệm đặt u thay cho v (lưu ý u(tn ) = yn ) gọi y nghiệm y = f (t, y), y(tn ) = yn , điều kiện Bổ đề 1.1 thỏa Vậy, theo công thức Alekseev-Grăobner (3.33), ta cú yn+1 y(tn+1 ) = u(tn+1 ) − y(tn+1 ) = ˆ =h tn+1 DΦ(tn+1 , τ, u(τ ))d(τ, u)dτ tn DΦ(tn+1 , tn + hτ, u(tn + hτ ))d(tn + hτ, u)dτ Bây ta thay tích phân cuối cơng thức cầu phương trọng hàm ω(t) ≡ 1, ≤ t ≤ với điểm nút cầu phương c1 , c2 , , cν Như vậy, ta viết ν yn+1 − y(tn+1 ) = h bj DΦ(tn+1 , tn + cj h, u(tn + cj h))d(tn + cj h, u) + hecp , (3.35) j=1 ecp sai số phép cầu phương Mặt khác, theo định nghĩa phép đặt (3.27), ta lại có d(tn + cj h, u) = u (tn + cj h) − f (tn + cj h, u(tn + cj h)) = 0, j = 1, 2, , ν Do điều kiện (3.34), với trọng hàm ω ≡ 1, viết dạng q, pˆ = 0, với pˆ ∈ Pm−1 , nên theo Định lý 2.3, phép cầu phương phải có bậc ν + m, nghĩa ecp = O(hν+m ) Từ suy yn+1 − y(tn+1 ) = hecp = O(hν+m+1 ), điều phải chứng minh Hệ 3.1 Cho c1 , c2 , , cν không điểm đa thức Pν ∈ Pν , trực giao trọng hàm ω(t) ≡ 1, ≤ t ≤ Khi đó, phương pháp đặt (3.27) có bậc 2ν Hệ 3.1 kết suy trực tiếp từ Định lý 3.2 từ định nghĩa tính trực giao, ta suy điều kiện (3.34) thỏa với m = ν Các phương pháp có ν-chặng bậc 2ν Hệ 3.1 gọi phương pháp Gauss-Legendre (Runge-Kutta) Theo Bổ đề 2.2, c1 , c2 , , cν thuộc khoảng (0, 1) phân biệt Ta nhận trực tiếp đa thức Pν cách dùng phép biến đổi tuyến tính đa thức Legendre quen thuộc Pν , trực giao trọng hàm ω(t) ≡ 1, −1 < t < Khi đó, đa thức đơn nhận ν (ν!)2 Pν (t) = (−1)ν−k Ckν Ckν+k tk , (2ν)! k=0 Cnm = m!/(n!(m − n)!) Với ν = ta nhận P1 (t) = t − (1/2), suy c1 = 1/2 theo (3.28), (3.29), ta có a11 = 1/2, b1 = √ √ Với ν = 2, P2 (t) = t2 − t + (1/6) có nghiệm c1 = (1/2) − 3/6, c2 = (1/2) + 3/6 theo công thức (3.28), (3.29), ta nhận ma trận A = (aji )2×2 giá trị b1 , b2 Vậy, bảng RK phương pháp đặt hay phương pháp RK-a có 2-chặng có bậc cho bởi: 2 − + √ √6 4√ + − √ Việc tính tốn hệ đại số phi tuyến sinh từ lược đồ RK-a với giá trị lớn ν nhiều cơng sức, bù lại, ta có bậc cao Trên thực tế, ta dự kiến 53 3.4 Sự xếp theo thứ tự phương pháp RK-a quy tắc cứng nhắc, dấu hiệu xác mà theo việc đầu tư cơng sức tính tốn rõ ràng khơng có lợi khiến ta phải chọn phương pháp có bậc thấp hơn, thay đổi từ phương trình sang phương trình khác Tuy nhiên, lưu ý phương pháp Gauss-Legendre 3-chặng phương pháp có bậc lớn phù hợp với cơng sức tính tốn Dưới bảng kết RK nhận từ phương pháp này, với P3 (t) = t3 − (3/2)t2 + (3/5)t − (1/20): 2 − √ 15 10 2√ + 15 10 36 36 36√ + + 18 15 √24 15 30 9 − √ 15 15 9√ + 15 15 36 36 + − 36 18 √ 15 √30 15 24 54 Chương Phương pháp Runge-Kutta Tài liệu tham khảo [1] Arieh Iserles, A First Course in the Numerical Analysis of Differential Equations, Cambridge University Press, 1996, ISBN 0-521-55376-8 [2] Butcher J C., Numerical Methods for Ordinary Differential Equations, Second Edition, John Wiley & Sons, 2008, ISBN 978-0-470-72335-7 [3] David Betounes, Differential Equations: Theory and Applications, Second Edition, Springer, 2010, ISBN 978-1-4419-1162-9 [4] George M Phillips, Interpolation and Approximation by Polynomials, Springer, 2003, ISBN 0-387-00215-4 [5] Hairer E., Norsett S P & Wanner G., Solving Ordinary Differential Equations I: Nonstiff Problems, Second Revised Edition, Springer, 1993, ISBN 978-3-540-56670-0 55 56 Tài liệu tham khảo Chỉ mục B bậc, 31 bt ng thc Hă older, 23 B Alekseev-Gră obner, 28, 51 Butcher, 5–6 C công thức biến thiên số, 51 công thức RK4, 40 điều kiện đơn giản hóa, 40 Đ đa thức trực giao, 34 đơn nhất, 34 cổ điển, 34 Chebyshev, 34 Hermite, 34 Jacobi, 34 Laguerre, 34 Legendre, 34 định thức Vandermonde, 35 độ lệch, 51 đường cong tích phân tối đại, 25 H hàm lũy thừa chặt cụt, 16 K khoảng cực đại, 25 Kutta, 6–45 L Luồng, 26 M Maple, 45 Mathematica, 45 N Newton-Cotes, 33 nghiệm ứng viên, 50 nghiệm số, 29 cỡ bước, 29 P Peano, 16 nhân Peano, 17 phép cầu phương, 32 điểm nút, 32 bậc, 32 trọng hàm, 32 trọng số, 32 phương pháp cầu phương Gauss, 36 phương pháp Euler, 29 đường gấp khúc Euler, 30 phương pháp Gauss-Legendre, 52 phương pháp Runge-Kutta, 37 ν-chặng, 38 điểm nút RK, 38 bảng RK, 38 dạng ẩn, 47 dạng hiện, 37 lược đồ Nystrom, 40 ma trận RK, 37 phương pháp RK cổ điển, 40 trọng số RK, 38 phương pháp đặt, 49 tham số định vị, 49 phương pháp xấp xỉ, 31 hội tụ, 30 phương trình vơ hướng tự điều chỉnh, 39 phiếm hàm tuyến tính, 16 hoành độ, 18 Q quỹ đạo, 24 R Runge-Kutta, T tích vơ hướng, 34 57 58 tính chất nửa nhóm, 26 đóng, 27 trường vector đầy đủ, 26 Chỉ mục ... tiềm ẩn tiếp tục Các phương pháp số để giải phương trình hay hệ phương trình vi phân nói chung, thường gọi tắt giải số phương trình vi phân, có mối liên hệ chất với phép cầu phương, thực chất... tích phân (xem [1]) Mối liên hệ tự nhiên tồn toán giá trị ban đầu phương trình vi phân tương đương với phương trình tích phân Với quan điểm toàn cục vậy, phương pháp Runge- Kutta trình bày cách... hàm f cho số điểm khác mà thôi! Dưới đây, ta minh họa vi? ??c áp dụng công thức RK4 để giải số toán giá trị ban đầu phương trình vi phân cấp một, hệ phương trình vi phân cấp phương trình vi phân tuyến