Phương pháp Runge-Kutta

Bách khoa toàn thư mở Wikipedia
Buớc tưới chuyển hướng Bước tới tìm kiếm

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.[1] 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[sửa | sửa mã nguồn]

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 , tốc độ thay đổi của y, là một hàm của ty. Tại thời điểm ban đầu giá trị y tương ứng là . Hàm f và các dữ liệu , được cho trước.

Bây giờ chọn một bước kích thước h> 0 và định nghĩa

với n = 0, 1, 2, 3,..., sử dụng[1]

(Lưu ý: các phương trình trên có những định nghĩa khác nhau nhưng tương đương trong các văn bản khác nhau).[2]

Ở đây là giá trị gần đúng (xấp xỉ) RK4 của , và giá trị tiếp theo () được xác định bằng giá trị hiện tại () 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.

  • là số gia dựa trên độ dốc tại điểm bắt đầu của khoảng thời gian, sử dụng (phương pháp Euler);
  • là số gia dựa trên độ dốc tại điểm giữa của khoảng thời gian, sử dụng ;
  • cũng là số gia dựa trên độ dốc ở điểm giữa, nhưng sử dụng ;
  • là số gia dựa trên độ dốc tại điểm cuối của khoảng thời gian, sử dụng .

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 độc lập với , để 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.[3]

So sánh Runge-Kutte 4 với các phương pháp bậc thấp hơn khác khi áp dụng cho một phương trình vi phân thường cho trước

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 , trong khi tổng lỗi tích lũy là bậc .

Các phương pháp Runge-Kutta hiện[sửa | sửa mã nguồ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 đó [4]

(Lưu ý: các phương trình bên trên có các định nghĩa khác nhau nhưng tương đương trong các văn bản khác nhau).[2]

Để 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 < is), 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 bici được biết đến như là các trọng lượng và các điểm nút.[5] 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 b1 + b2 = 1, b2c2 = 1/2, và a21 = c2.[6]

Nhìn chung, nếu một phương pháp Runge-Kutta hiện -giai đoạn có , và nếu , thì .[7] nhỏ nhất cần thiết cho một phương pháp Runge-Kutta hiện -giai đoạn để có bậc là một vấn đề mở. Một số giá trị đã biết:[8]

Ví dụ[sửa | sửa mã nguồn]

Phương pháp RK4 trong khuôn khổ này. Hoạt cảnh của nó là [9]

0
1/2 1/2
1/2 0 1/2
1 0 0 1
1/6 1/3 1/3 1/6

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.[10] Ư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à:

0
1/3 1/3
2/3 −1/3 1
1 1 −1 1
1/8 3/8 3/8 1/8

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 . Đâ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à

0
1

Các phương pháp bậc-hai với hai giai đoạn[sửa | sửa mã nguồ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à

0
1/2 1/2
0 1

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[11]

Hoạt cảnh Butcher của nó là

0

Trong họ này, đối với phương pháp điểm giữa, và đối với phương pháp Heun.[3]

Ứng dụng[sửa | sửa mã nguồn]

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

0
2/3 2/3
1/4 3/4

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[sửa | sửa mã nguồn]

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 và một với bậc .

Bước bậc-thấp hơn được cho bởi

trong đó 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 . 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 :

0

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à:

0
1/4 1/4
3/8 3/32 9/32
12/13 1932/2197 −7200/2197 7296/2197
1 439/216 −8 3680/513 -845/4104
1/2 −8/27 2 −3544/2565 1859/4104 −11/40
16/135 0 6656/12825 28561/56430 −9/50 2/55
25/216 0 1408/2565 2197/4104 −1/5 0

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à:

0
1 1
1/2 1/2
1 0

Ướ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[sửa | sửa mã nguồn]

Một phương pháp Runge-Kutta được gọi là phi hợp lưu [12] nếu tất cả đều khác nhau.

Các phương pháp Runge-Kutta ẩn[sửa | sửa mã nguồ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.[13] 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 đó

[14]

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ố 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[9]

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.[15]

Ví dụ[sửa | sửa mã nguồn]

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ự.[16]

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 2s (như vậy, các phương pháp với bậc cao tùy ý có thể được xây dựng).[17] Phương pháp với hai giai đoạn (và do đó có bậc bốn) có hoạt cảnh Butcher:

[15]

Độ ổn định[sửa | sửa mã nguồn]

Ư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 , với r được cho bởi

[18]

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.[19] 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(IzA) = 1 và rằng hàm tính ổn định là một đa thức.[20]

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) | < 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) < 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.[20]

Nếu phương pháp có bậc p, thì hàm tính ổn định thỏa mãn khi . 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.[21]

Phương pháp Gauss-Legendre với s giai đoạn có bậc 2s, 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.[22] Đ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.[23]

Độ ổn định-B[sửa | sửa mã nguồn]

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 . 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 , với , được gọi là ổn định-B, nếu điều kiện này dẫn đến .

Cho , là ba ma trận đượ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ố [24] nếu các ma trận and đều xác định không âm. Điều kiện đủ cho độ ổn định-B [25] 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[sửa | sửa mã nguồn]

Nói chung một phương pháp Runge-Kutta bậc s có thể được viết như sau:

trong đó:

là các số gia đạt được đánh giá các đạo hàm của tại bậc thứ .

Chúng ta rút ra[26] 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 , 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 , do đó chúng ta chọn:

và mặt khác . Chúng ta bắt đầu bằng cách định nghĩa các đại lượng sau đây:

trong đó 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 :

trong đó:

là đạo hàm toàn phần của 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 xung quanh :

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ó như đã nói trên.

Xem thêm[sửa | sửa mã nguồn]

Lưu ý[sửa | sửa mã nguồn]

  1. ^ Press et al. 2007, tr. 908; Süli & Mayers 2003, tr. 328
  2. ^ a ă Atkinson (1989, tr. 423), Hairer, Nørsett & Wanner (1993, tr. 134), Kaw & Kalu (2008, §8.4) and Stoer & Bulirsch (2002, tr. 476) leave out the factor h in the definition of the stages. Ascher & Petzold (1998, tr. 81), Butcher (2008, tr. 93) and Iserles (1996, tr. 38) use the y values as stages.
  3. ^ a ă Süli & Mayers 2003, tr. 328
  4. ^ Press et al. 2007, tr. 907
  5. ^ Iserles 1996, tr. 38
  6. ^ Iserles 1996, tr. 39
  7. ^ Butcher 2008, tr. 187
  8. ^ Butcher 2008, tr. 187–196
  9. ^ a ă Süli & Mayers 2003, tr. 352
  10. ^ Hairer, Nørsett & Wanner (1993, tr. 138) refer to Kutta (1901).
  11. ^ Süli & Mayers 2003, tr. 327
  12. ^ Lambert 1991, tr. 278
  13. ^ Süli & Mayers 2003, tr. 349–351
  14. ^ Iserles 1996, tr. 41; Süli & Mayers 2003, tr. 351–352
  15. ^ a ă Süli & Mayers 2003, tr. 353
  16. ^ Iserles 1996, tr. 43–44
  17. ^ Iserles 1996, tr. 47
  18. ^ Hairer & Wanner 1996, tr. 40–41
  19. ^ Hairer & Wanner 1996, tr. 40
  20. ^ a ă Iserles 1996, tr. 60
  21. ^ Iserles 1996, tr. 62–63
  22. ^ Iserles 1996, tr. 63
  23. ^ This result is due to Dahlquist (1963).
  24. ^ Lambert 1991, tr. 275
  25. ^ Lambert 1991, tr. 274
  26. ^ PDF reporting this derivation

Tham khảo[sửa | sửa mã nguồn]

Liên kết ngoài[sửa | sửa mã nguồn]

Bản mẫu:Numerical integrators