Runge–Kutta methods are methods for the numerical solution of the ordinary differential equation
Explicit Runge–Kutta methods take the form
Stages for implicit methods of s stages take the more general form, with the solution to be found over all s
Each method listed on this page is defined by its Butcher tableau, which puts the coefficients of the method in a table as follows:
For adaptive and implicit methods, the Butcher tableau is extended to give values of , and the estimated error is then
- .
Explicit methods[edit]
The explicit methods are those where the matrix is lower triangular.
Forward Euler[edit]
The Euler method is first order. The lack of stability and accuracy limits its popularity mainly to use as a simple introductory example of a numeric solution method.
Explicit midpoint method[edit]
The (explicit) midpoint method is a second-order method with two stages (see also the implicit midpoint method below):
Heun's method[edit]
Heun's method is a second-order method with two stages. It is also known as the explicit trapezoid rule, improved Euler's method, or modified Euler's method:
Ralston's method[edit]
Ralston's method is a second-order method[1] with two stages and a minimum local error bound:
Generic second-order method[edit]
Kutta's third-order method[edit]
Generic third-order method[edit]
See Sanderse and Veldman (2019).[2]
for α ≠ 0, 2⁄3, 1:
Heun's third-order method[edit]
Van der Houwen's/Wray third-order method[edit]
Ralston's third-order method[edit]
Ralston's third-order method[1] is used in the embedded Bogacki–Shampine method.
Third-order Strong Stability Preserving Runge-Kutta (SSPRK3)[edit]
Classic fourth-order method[edit]
The "original" Runge–Kutta method.[3]
3/8-rule fourth-order method[edit]
This method doesn't have as much notoriety as the "classic" method, but is just as classic because it was proposed in the same paper (Kutta, 1901).[3]
Ralston's fourth-order method[edit]
This fourth order method[1] has minimum truncation error.
Embedded methods[edit]
The embedded methods are designed to produce an estimate of the local truncation error of a single Runge–Kutta step, and as result, allow to control the error with adaptive stepsize. This is done by having two methods in the tableau, one with order p and one with order p-1.
The lower-order step is given by
where the are the same as for the higher order method. Then the error is
which is . The Butcher Tableau for this kind of method is extended to give the values of
Heun–Euler[edit]
The simplest adaptive Runge–Kutta method involves combining Heun's method, which is order 2, with the Euler method, which is order 1. Its extended Butcher Tableau is:
The error estimate is used to control the stepsize.
Fehlberg RK1(2)[edit]
The Fehlberg method[4] has two methods of orders 1 and 2. Its extended Butcher Tableau is:
0 | ||||
1/2 | 1/2 | |||
1 | 1/256 | 255/256 | ||
1/512 | 255/256 | 1/512 | ||
1/256 | 255/256 | 0 |
The first row of b coefficients gives the second-order accurate solution, and the second row has order one.
Bogacki–Shampine[edit]
The Bogacki–Shampine method has two methods of orders 2 and 3. Its extended Butcher Tableau is:
0 | |||||
1/2 | 1/2 | ||||
3/4 | 0 | 3/4 | |||
1 | 2/9 | 1/3 | 4/9 | ||
2/9 | 1/3 | 4/9 | 0 | ||
7/24 | 1/4 | 1/3 | 1/8 |
The first row of b coefficients gives the third-order accurate solution, and the second row has order two.
Fehlberg[edit]
The Runge–Kutta–Fehlberg method has two methods of orders 5 and 4; it is sometimes dubbed RKF45 . Its extended Butcher Tableau is:
The first row of b coefficients gives the fifth-order accurate solution, and the second row has order four. The coefficients here allow for an adaptive stepsize to be determined automatically.
Cash-Karp[edit]
Cash and Karp have modified Fehlberg's original idea. The extended tableau for the Cash–Karp method is
0 | |||||||
1/5 | 1/5 | ||||||
3/10 | 3/40 | 9/40 | |||||
3/5 | 3/10 | −9/10 | 6/5 | ||||
1 | −11/54 | 5/2 | −70/27 | 35/27 | |||
7/8 | 1631/55296 | 175/512 | 575/13824 | 44275/110592 | 253/4096 | ||
37/378 | 0 | 250/621 | 125/594 | 0 | 512/1771 | ||
2825/27648 | 0 | 18575/48384 | 13525/55296 | 277/14336 | 1/4 |
The first row of b coefficients gives the fifth-order accurate solution, and the second row has order four.
Dormand–Prince[edit]
The extended tableau for the Dormand–Prince method is
0 | ||||||||
1/5 | 1/5 | |||||||
3/10 | 3/40 | 9/40 | ||||||
4/5 | 44/45 | −56/15 | 32/9 | |||||
8/9 | 19372/6561 | −25360/2187 | 64448/6561 | −212/729 | ||||
1 | 9017/3168 | −355/33 | 46732/5247 | 49/176 | −5103/18656 | |||
1 | 35/384 | 0 | 500/1113 | 125/192 | −2187/6784 | 11/84 | ||
35/384 | 0 | 500/1113 | 125/192 | −2187/6784 | 11/84 | 0 | ||
5179/57600 | 0 | 7571/16695 | 393/640 | −92097/339200 | 187/2100 | 1/40 |
The first row of b coefficients gives the fifth-order accurate solution, and the second row gives the fourth-order accurate solution.
Implicit methods[edit]
Backward Euler[edit]
The backward Euler method is first order. Unconditionally stable and non-oscillatory for linear diffusion problems.
Implicit midpoint[edit]
The implicit midpoint method is of second order. It is the simplest method in the class of collocation methods known as the Gauss-Legendre methods. It is a symplectic integrator.
Crank-Nicolson method[edit]
The Crank–Nicolson method corresponds to the implicit trapezoidal rule and is a second-order accurate and A-stable method.
Gauss–Legendre methods[edit]
These methods are based on the points of Gauss–Legendre quadrature. The Gauss–Legendre method of order four has Butcher tableau:
The Gauss–Legendre method of order six has Butcher tableau:
Diagonally Implicit Runge–Kutta methods[edit]
Diagonally Implicit Runge–Kutta (DIRK) formulae have been widely used for the numerical solution of stiff initial value problems; [5] the advantage of this approach is that here the solution may be found sequentially as opposed to simultaneously.
The simplest method from this class is the order 2 implicit midpoint method.
Kraaijevanger and Spijker's two-stage Diagonally Implicit Runge–Kutta method:
Qin and Zhang's two-stage, 2nd order, symplectic Diagonally Implicit Runge–Kutta method:
Pareschi and Russo's two-stage 2nd order Diagonally Implicit Runge–Kutta method:
This Diagonally Implicit Runge–Kutta method is A-stable if and only if . Moreover, this method is L-stable if and only if equals one of the roots of the polynomial , i.e. if . Qin and Zhang's Diagonally Implicit Runge–Kutta method corresponds to Pareschi and Russo's Diagonally Implicit Runge–Kutta method with .
Two-stage 2nd order Diagonally Implicit Runge–Kutta method:
Again, this Diagonally Implicit Runge–Kutta method is A-stable if and only if . As the previous method, this method is again L-stable if and only if equals one of the roots of the polynomial , i.e. if . This condition is also necessary for 2nd order accuracy.
Crouzeix's two-stage, 3rd order Diagonally Implicit Runge–Kutta method:
Crouzeix's three-stage, 4th order Diagonally Implicit Runge–Kutta method:
with .
Three-stage, 3rd order, L-stable Diagonally Implicit Runge–Kutta method:
with
Nørsett's three-stage, 4th order Diagonally Implicit Runge–Kutta method has the following Butcher tableau:
with one of the three roots of the cubic equation . The three roots of this cubic equation are approximately , , and . The root gives the best stability properties for initial value problems.
Four-stage, 3rd order, L-stable Diagonally Implicit Runge–Kutta method
Lobatto methods[edit]
There are three main families of Lobatto methods,[6] called IIIA, IIIB and IIIC (in classical mathematical literature, the symbols I and II are reserved for two types of Radau methods). These are named after Rehuel Lobatto[6] as a reference to the Lobatto quadrature rule, but were introduced by Byron L. Ehle in his thesis.[7] All are implicit methods, have order 2s − 2 and they all have c1 = 0 and cs = 1. Unlike any explicit method, it's possible for these methods to have the order greater than the number of stages. Lobatto lived before the classic fourth-order method was popularized by Runge and Kutta.
Lobatto IIIA methods[edit]
The Lobatto IIIA methods are collocation methods. The second-order method is known as the trapezoidal rule:
The fourth-order method is given by
These methods are A-stable, but not L-stable and B-stable.
Lobatto IIIB methods[edit]
The Lobatto IIIB methods are not collocation methods, but they can be viewed as discontinuous collocation methods (Hairer, Lubich & Wanner 2006, §II.1.4). The second-order method is given by
The fourth-order method is given by
Lobatto IIIB methods are A-stable, but not L-stable and B-stable.
Lobatto IIIC methods[edit]
The Lobatto IIIC methods also are discontinuous collocation methods. The second-order method is given by
The fourth-order method is given by
They are L-stable. They are also algebraically stable and thus B-stable, that makes them suitable for stiff problems.
Lobatto IIIC* methods[edit]
The Lobatto IIIC* methods are also known as Lobatto III methods (Butcher, 2008), Butcher's Lobatto methods (Hairer et al., 1993), and Lobatto IIIC methods (Sun, 2000) in the literature.[6] The second-order method is given by
Butcher's three-stage, fourth-order method is given by
These methods are not A-stable, B-stable or L-stable. The Lobatto IIIC* method for is sometimes called the explicit trapezoidal rule.
Generalized Lobatto methods[edit]
One can consider a very general family of methods with three real parameters by considering Lobatto coefficients of the form
- ,
where
- .
For example, Lobatto IIID family introduced in (Nørsett and Wanner, 1981), also called Lobatto IIINW, are given by
and
These methods correspond to , , , and . The methods are L-stable. They are algebraically stable and thus B-stable.
Radau methods[edit]
Radau methods are fully implicit methods (matrix A of such methods can have any structure). Radau methods attain order 2s − 1 for s stages. Radau methods are A-stable, but expensive to implement. Also they can suffer from order reduction. The first order Radau method is similar to backward Euler method.
Radau IA methods[edit]
The third-order method is given by
The fifth-order method is given by
Radau IIA methods[edit]
The ci of this method are zeros of
- .
The third-order method is given by
The fifth-order method is given by
Notes[edit]
- ^ a b c Ralston, Anthony (1962). "Runge-Kutta Methods with Minimum Error Bounds". Math. Comput. 16 (80): 431–437. doi:10.1090/S0025-5718-1962-0150954-0.
- ^ Sanderse, Benjamin; Veldman, Arthur (2019). "Constraint-consistent Runge–Kutta methods for one-dimensional incompressible multiphase flow". J. Comput. Phys. 384: 170. arXiv:1809.06114. Bibcode:2019JCoPh.384..170S. doi:10.1016/j.jcp.2019.02.001. S2CID 73590909.
- ^ a b Kutta, Martin (1901). "Beitrag zur näherungsweisen Integration totaler Differentialgleichungen". Zeitschrift für Mathematik und Physik. 46: 435–453.
- ^ Fehlberg, E. (July 1969). Low-order classical Runge-Kutta formulas with stepsize control and their application to some heat transfer problems (NASA Technical Report R-315).
- ^ For discussion see: Christopher A. Kennedy; Mark H. Carpenter (2016). "Diagonally Implicit Runge-Kutta Methods for Ordinary Differential Equations. A Review". Technical Memorandum, NASA STI Program.
- ^ a b c See Laurent O. Jay (N.D.). "Lobatto methods". University of Iowa
- ^ Ehle (1969)
References[edit]
- Ehle, Byron L. (1969). On Padé approximations to the exponential function and A-stable methods for the numerical solution of initial value problems (PDF) (Thesis).
- Hairer, Ernst; Nørsett, Syvert Paul; Wanner, Gerhard (1993), Solving ordinary differential equations I: Nonstiff problems, Berlin, New York: Springer-Verlag, ISBN 978-3-540-56670-0.
- Hairer, Ernst; Wanner, Gerhard (1996), Solving ordinary differential equations II: Stiff and differential-algebraic problems, Berlin, New York: Springer-Verlag, ISBN 978-3-540-60452-5.
- Hairer, Ernst; Lubich, Christian; Wanner, Gerhard (2006), Geometric Numerical Integration: Structure-Preserving Algorithms for Ordinary Differential Equations (2nd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-30663-4.