Phương pháp Runge-Kutta

Trong giải tích số, các phương pháp Runge-Kutta là một họ của các phương pháp lặp ẩn (implicit) và hiện (explicit), trong đó bao gồm thường trình nổi tiếng được gọi là các phương pháp Euler, được sử dụng trong việc rời rạc hóa thời gian để tìm lời giải gần đúng cho các phương trình vi phân thường. Những phương pháp này được phát triển vào khoảng năm 1900 bởi hai nhà toán học người Đức C. Runge và M. W. Kutta.
Xem bài viết về các phương pháp số áp dụng cho việc tìm lời giải của các phương trình vi phân thường để hiểu hơn về nền tảng cơ sở và các phương pháp số khác. Xem thêm Danh sách các phương pháp Runge-Kutta.
Phương pháp Runge-Kutta.
Thành viên được biết đến rộng rãi nhất của họ Runge-Kutta là "RK4", "phương pháp Runge-Kutta cổ điển" hoặc đơn giản là "phương pháp Runge-Kutta".
Cho một bài toán giá trị ban đầu được chỉ rõ như sau:
Ở đây "y" là một hàm chưa biết (vô hướng hoặc vector) của thời gian "t", mà chúng ta muốn tìm lời giải gần đúng; chúng ta biết rằng formula_2, tốc độ thay đổi của "y", là một hàm của "t" và "y." Tại thời điểm ban đầu formula_3 giá trị "y" tương ứng là formula_4. Hàm "f" và các dữ liệu formula_3, formula_4 được cho trước.
Bây giờ chọn một bước kích thước "h&gt; 0" và định nghĩa
với "n" = 0, 1, 2, 3..., sử dụng
Ở đây formula_9 là giá trị gần đúng (xấp xỉ) RK4 của formula_10, và giá trị tiếp theo (formula_9) được xác định bằng giá trị hiện tại (formula_12) cộng với trung bình trọng lượng của bốn số gia, trong đó mỗi số gia là sản phẩm của kích cỡ của khoảng thời gian, "h," và một độ dốc ước tính được chỉ rõ bởi hàm "f" ở phía bên tay phải của phương trình vi phân.
Trong việc trung bình của bốn số gia, trọng lượng lớn hơn được trao cho các số gia tại điểm giữa. Nếu formula_21 độc lập với formula_22, để các phương trình vi phân tương đương với một tích phân đơn giản, thì RK4 là quy tắc Simpson.
Phương pháp RK4 là một phương pháp bậc 4, có nghĩa rằng sai số cắt cụt cục bộ bậc formula_23, trong khi tổng lỗi tích lũy là bậc formula_24.
Các phương pháp Runge-Kutta hiện.
Họ các phương pháp Runge-Kutta hiện (explicit) là một sự tổng quát hóa của phương pháp RK4 đã đề cập bên trên. Nó được cho bởi công thức:
trong đó 
Để chỉ rõ một phương pháp cụ thể, cần cung cấp số nguyên "s" (số giai đoạn), và các hệ số "aij" (đối với 1 ≤ "j" &lt; "i" ≤ "s"), "bi" (đối với "i" = 1, 2..., "s") và "ci" (đối với "i" = 2, 3..., "s"). Ma trận ["aij"] được gọi là "ma trận Runge–Kutta", trong khi "bi" và "ci" được biết đến như là các trọng lượng và các điểm nút. Những dữ liệu này thường được sắp xếp trong một thiết bị ghi nhớ, được biết đến như là một "hoạt cảnh (tableau)" "Butcher" (đặt theo tên của John C. Butcher):
Phương pháp Runge-Kutta là nhất quán nếu
Ngoài ra còn có các yêu cầu kèm theo nếu yêu cầu phương pháp phải có bậc "p" nào đó, có nghĩa rằng sai số cắt cụt cục bộ là O("hp"+1). Những điều này có thể được rút ra từ định nghĩa của chính sai số cắt cụt. Cho ví dụ, một phương pháp hai giai đoạn có bậc 2 nếu "b"1 + "b"2 = 1, "b"2"c"2 = 1/2, và "a"21 = "c"2.
Nhìn chung, nếu một phương pháp Runge-Kutta hiện formula_28-giai đoạn có formula_29, và nếu formula_30, thì formula_31. formula_28 nhỏ nhất cần thiết cho một phương pháp Runge-Kutta hiện formula_28-giai đoạn để có bậc formula_34 là một vấn đề mở. Một số giá trị đã biết:
Ví dụ.
Phương pháp RK4 trong khuôn khổ này. Hoạt cảnh của nó là 
Một sự thay đổi đôi chút của phương pháp Runge-Kutta cũng là do Kutta tạo ra năm 1901 và được gọi là quy tắc-3/8. Ưu điểm chính phương pháp này là hầu như tất cả các hệ số lỗi là nhỏ hơn so với phương pháp thông thường, nhưng nó đòi hỏi nhiều FLOPS hơn đôi chút (các thao tác điểm-nổi) cho mỗi bước thời gian. Hoạt cảnh Butcher của nó là:
Tuy nhiên, phương pháp Runge-Kutta đơn giản nhất là phương pháp Euler (tiếp tới = forward), được cho bởi công thức formula_36. Đây là phương pháp Runge-Kutte hiện nhất quán duy nhất với một giai đoạn. Hoạt cảnh tương ứng là
Các phương pháp bậc-hai với hai giai đoạn.
Một ví dụ của một phương pháp bậc hai với hai giai đoạn là phương pháp điểm giữa:
Hoạt cảnh tương ứng là
Phương pháp điểm giữa không phải là phương pháp Runge-Kutta bậc-hai duy nhất với hai giai đoạn; có một họ những phương pháp như vậy, được tham số hóa bởi α và cho bởi công thức
Hoạt cảnh Butcher của nó là
Trong họ này, formula_39 đối với phương pháp điểm giữa, và formula_40 đối với phương pháp Heun.
Ứng dụng.
Như một ví dụ, xem xét phương pháp Runge-Kutta bậc-hai hai-giai đoạn với α = 2/3, cũng được biết như là phương pháp Ralston. Nó được cho bởi hoạt cảnh
với các phương trình tương ứng
Phương pháp này được sử dụng để giải các bài toán giá trị-ban đầu
với kích cỡ bước "h = 0.025", vì vậy phương pháp này cần phải thực hiện bốn bước
Phương pháp được tiến hành như sau:
Lời giải số tương ứng với giá trị được gạch chân.
Các phương pháp Runge-Kutta thích ứng.
Các phương pháp thích ứng được thiết kế để tạo ra ước tính của sai số cắt cụt cục bộ của một bước Runge-Kutta đơn nhất. Điều này được thực hiện bằng cách dùng hai phương pháp trong hoạt cảnh, một với bậc formula_34 và một với bậc formula_44.
Bước bậc-thấp hơn được cho bởi
trong đó formula_46 là giống hệt như đối với phương pháp bậc-cao hơn. Và lỗi là
với bậc formula_48.
Hoạt cảnh Butcher cho loại phương pháp này được mở rộng để cho ra các giá trị của formula_49:
Phương pháp Runge-Kutta-Fehlberg có hai phương pháp bậc 5 và 4. Hoạt cảnh Butcher mở rộng của nó là:
Tuy nhiên, phương pháp Runge-Kutta thích ứng đơn giản nhất liên quan đến việc kết hợp phương pháp Heun (có bậc 2), với phương pháp Euler (có bậc 1). Hoạt cảnh Butcher mở rộng là:
Ước tính lỗi được sử dụng để kiểm soát kích thước bước.
Các phương pháp Runge-Kutta thích ứng khác là phương pháp Bogacki-Shampine (bậc 3 và bậc 2), phương pháp Cash-Karp và phương pháp Dormand-Prince (cả hai đều có bậc 5 và 4).
Các phương pháp Runge-Kutta phi hợp lưu.
Một phương pháp Runge-Kutta được gọi là "phi hợp lưu" nếu tất cả formula_50 đều khác nhau.
Các phương pháp Runge-Kutta ẩn.
Tất cả các phương pháp Runge-Kutta đã đề cập cho đến bây giờ đều là các phương pháp hiện (explicit). Các phương pháp Runge-Kutta hiện nói chung không phù hợp cho việc tìm lời giải của các phương trình cứng vì vùng ổn định tuyệt đối của chúng rất nhỏ; cụ thể là, bị bao bọc.
Vấn đề này đặc biệt quan trọng trong việc tìm lời giải cho các phương trình vi phân từng phần.
Sự bất ổn định của phương pháp Runge-Kutta hiện thúc đẩy sự phát triển của các phương pháp ẩn (implicit). Một phương pháp Runge-Kutta ẩn có dạng
trong đó
Sự khác nhau so với phương pháp hiện là trong một phương pháp hiện, phép tính tổng đối với chỉ số "j" chỉ lên đến "i" − 1. Điều này cũng thấy rõ trong các hoạt cảnh Butcher: ma trận hệ số formula_53 của một phương pháp hiện là ma trận tam giác dưới Trong một phương pháp ẩn, phép tổng đối với "j" tính đến "s" và ma trận hệ số không phải là ma trận tam giác, cho kết quả là bảng Butcher có dạng
Kết quả của sự khác biệt này là tại mỗi bước, một hệ các phương trình đại số phải được giải. Điều này làm tăng chi phí tính toán một cách đáng kể. Nếu một phương pháp với "s" giai đoạn được sử dụng để giải một phương trình vi phân với "m" thành phần, thì hệ các phương trình đại số có "ms" thành phần. Điều này có thể tương phản với các phương pháp đa bước tuyến tính ẩn (một họ lớn khác của các phương pháp sử dụng cho việc tìm lời giải của các phương trình vi phân thường ODEs): một phương pháp đa bước tuyến tính "s"-bước ẩn cần giải một hệ các phương trình đại số với chỉ "m" thành phần, vì vậy kích thước của hệ không tăng khi số lượng các bước tăng lên.
Ví dụ.
Ví dụ đơn giản của một phương pháp Runge-Kutta implicit là phương pháp Euler lùi (backward):
Hoạt cảnh Butcher chỉ đơn giản là:
Hoạt cảnh Butcher này tương ứng với các công thức
có thể được sắp xếp lại để có được công thức cho phương pháp Euler lùi được liệt kê ở trên.
Một ví dụ nữa của phương pháp Runge-Kutta ẩn là quy tắc hình thang. Hoạt cảnh Butcher của nó là:
Quy tắc hình thang là một phương pháp sắp đặt theo thứ tự (collocation) (như thảo luận trong bài viết về phương pháp này). Tất cả các phương pháp sắp đặt theo thứ tự đều là các phương pháp Runge-Kutta ẩn, nhưng không phải tất cả các phương pháp Runge-Kutta ẩn là các phương pháp sắp đặt theo thứ tự.
Các phương pháp Gauss-Legendre tạo thành một họ của các phương pháp sắp đặt theo thứ tự dựa trên phép cầu phương Gauss quadrature. Một phương pháp Gauss-Legendre với "s" giai đoạn s có bậc 2"s" (như vậy, các phương pháp với bậc cao tùy ý có thể được xây dựng). Phương pháp với hai giai đoạn (và do đó có bậc bốn) có hoạt cảnh Butcher:
Độ ổn định.
Ưu điểm của các phương pháp Runge-Kutta ẩn so với các phương pháp hiện là độ ổn định của chúng lớn hơn, đặc biệt khi áp dụng cho các phương trình cứng. Xét phương trình thử nghiệm tuyến tính "y"' = λ"y". Một phương pháp Runge-Kutta được áp dụng cho phương trình này, để có phép lặp formula_60, với "r" được cho bởi
trong đó "e" là viết tắt của vector với các thành phần đều bằng một. Hàm "r" được gọi là "hàm tính ổn định". Từ công thức, ta có "r" là thương số của hai đa thức bậc "s" nếu phương pháp có "s" giai đoạn. Các phương pháp hiện có ma trận A là ma trận tam giác thấp với các thành phần bằng không dọc đường chéo, tức là det("I" − "zA") = 1 và rằng hàm tính ổn định là một đa thức.
Lời giải số cho phương trình thử nghiệm tuyến tính phân rã về không nếu | "r"("z") | &lt; 1 với "z" = "h"λ. Tập hợp của các "z đó" được gọi là "miền ổn định tuyệt đối". Đặc biệt, phương pháp được gọi là ổn định-A nếu tất cả "z" với Re("z") &lt; 0 đều nằm trong miền ổn định tuyệt đối. Hàm ổn định của một phương pháp Runge-Kutta hiện là một đa thức, vì vậy các phương pháp Runge-Kutta hiện có thể không bao giờ là ổn định-A.
Nếu phương pháp có bậc p, thì hàm tính ổn định thỏa mãn formula_62 khi formula_63. Vì vậy, quan tâm nghiên cứu các thương số của các đa thức với bậc cho trước gần giống so với hàm mũ nhất. Chúng được gọi là các Padé approximants. Một Padé approximant với tử số bậc "m" và mẫu số bậc "n" là ổn định-A khi và chỉ khi "m ≤ n ≤ m" + 2.
Phương pháp Gauss-Legendre với "s" giai đoạn có bậc 2"s", vì vậy hàm tính ổn định của nó là Padé approximant với "m" = "n" = "s". Do đó phương pháp này là ổn định-A. Điều này cho thấy rằng Runge-Kutta ổn định-A có thể có bậc cao tùy ý. Ngược lại, bậc của các phương pháp đa bước tuyến tính ổn định-A không thể vượt quá hai.
Độ ổn định-B.
Khái niệm "độ ổn định-A" cho lời giải của các phương trình vi phân, có liên quan đến phương trình tự trị tuyến tính formula_64. Dahlquist đã đề xuất việc nghiên cứu độ ổn định của các lược đồ số (numerical schemes) khi áp dụng cho các hệ phi tuyến thỏa mãn một điều kiện đơn điệu. Các khái niệm tương ứng được xác định như là "độ ổn định-G" đối với các phương pháp đa bước (và các phương pháp một-chân liên quan) và "độ ổn định-B" (Butcher, 1975) cho các phương pháp Runge-Kutta. Một phương pháp Runge-Kutta được áp dụng cho hệ phi tuyến tính formula_65, với formula_66, được gọi là "ổn định-B", nếu điều kiện này dẫn đến formula_67.
Cho formula_68, formula_69 và formula_70 là ba ma trận formula_71 được xác định bởi
Một phương pháp Runge-Kutta được gọi là ổn định về mặt đại số nếu các ma trận formula_68 and formula_69 đều xác định không âm. Điều kiện đủ cho "độ ổn định"-B là: B and Q là xác định không âm.
Nguồn gốc của phương pháp Runge-Kutta bậc bốn.
Nói chung một phương pháp Runge-Kutta bậc 4 có thể được viết như sau:
trong đó:
là các số gia đạt được đánh giá các đạo hàm của formula_77 tại bậc thứ formula_78.
Chúng ta rút ra phương pháp Runge-Kutta bậc bốn bằng cách áp dụng công thức tổng quát với trường hợp formula_79, như đã giải thích ở trên, tại điểm khởi đầu, điểm giữa và điểm cuối của bất kỳ khoảng formula_80, do đó chúng ta chọn:
và mặt khác formula_82. Chúng ta bắt đầu bằng cách định nghĩa các đại lượng sau đây:
trong đó formula_84 và formula_85
Nếu chúng ta định nghĩa:
và với các mối quan hệ trước đó chúng ta có thể thấy rằng các đẳng thức sau đúng đến bậc formula_87:
trong đó:
là đạo hàm toàn phần của formula_21 theo thời gian.
Nếu bây giờ chúng ta biểu diễn công thức tổng quát bằng những gì chúng ta vừa rút ra, chúng ta có được:
và so sánh với chuỗi Taylor của formula_92 xung quanh formula_77:
chúng ta có được một hệ phương trình của các hệ số:
giải hệ trên ta có formula_96 như đã nói trên.