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
- .
YouTube Encyclopedic
-
1/5Views:298 6656 61011 08323 2471 998
-
Runge-Kutta Method Introduction
-
Learning the Runge-Kutta Method 1. Basic Runge-Kutta
-
Classical Runge-Kutta, ODE4
-
A Better Integrator? The Runge-Kutta Family of Integrators - Part 1 of 2 - Mathematical Foundation
-
Lecture 13 - Runge-Kutta methods in Mathematica
Transcription
In this video I'll describe a method used to solve ordinary differential equations and this is a better approximation that the Euler Method which is described in another of our videos. The Runge-Kutta Method's a fourth order approximation the idea is we have initial conditions namely at a certain location, a certain value of x we know the value of y and then we have an ordinary differential equation that relates how y changes as we change x and that's a function of x and y. So what we're going to do in the Runge-Kutta Method is use a recurrence formula and say if I know a value of y then I can make a small step and the step is to say xn plus 1 is equal to xn plus h so we make a small step in h and calculate the new value of y that corresponds to the xn plus 1 and we have this term here that's a function of xn and yn and the size of step. Smaller steps will give us more accurate calculations and of course this is something that in a computer program can very easily be done the step through. Programs can be more sophisticated than this but this gives you a good idea of how these programs work. So what I'm going to do is write down the formula for T4 and then discuss what the terms are in it. The T4 is 1/6 times the summation of the 6 terms essentially. k1 is just the function evaluated at x and y so at xn and yn for a given condition. k2 is a function evaluated but now x plus 1/2 the step size and y plus 1/2 the step size multiplied by the function, k1. k3 in very similar except it's k2 here and then K4 is evaluated at the full step size and k3 is here. And so this gives us a better approximation than say the Euler Method which just we use the function at the previous point and the forth order approximation means if we were to decrease the step size so instead if h, we used h over 2 as our step size then we reduce the error by a factor of 2^5. We can get fairly accurate measurements using this Runge-Kutta. So what we're going to do next is apply this formula to a simple differential equation and look at the first few steps to make it clear how we're doing these calculations on a computer. So let's look at this example, I've written a simple differential equation we could certainly solve this analytically but what we are interested in is the technique. And we're going to assume that at x0 equals 1 and y0 equals 2 so this is our initial conditions. And then we use a step size to calculate y at a larger value of x. So I've written down the recurrence formula and then I've substituted in the numbers. y0 is 2 the step size here is 0.1 and then k1 plus 2 k2 plus 2 k3 plus k4 and so we need to calculate the values. k1 is just the function evaluated at x0 and y0 which is then 3 x0 squared times y0. So that's k1 and similarly we calculated the other values k2, 3, and 4. So I've written the recurrence formula term now for k2 so it's evaluated x0 which is 1 plus the step size 0.1 divided by 2 and then again the step size over here 0.1 and then now the value of k1 that we just calculated. So we have the value for k2 and we do similar things to calculate k3 and k4. So here's the values calculated for k3 where we're using now k2 that we calculated in the previous step and we get the value of k3 and to calculate k4. Now we use step size h so this is 1.10 and we're using k3 in this calculation. Once we have these four values we can calculate y1. So y1 is y0 plus the step size h over 6 k1 plus 2 k2 plus 2 k3 plus k4 so I'll substitute this values in. And so substituting the values we calculate the value for k1 , k2, k3, and k4 we get y1 that corresponds to the next value of one value of 1.10. Well this is much more accurate than the Euler Method calculation. And then we continue the step through we get y2 as y1 plus hT4 evaluated x1 and y1 and the same idea we can calculate the function as we more through where k1 in this calculation is a function now of x1 and y1 the values we just calculated. This is then the technique that's used in numerical programs like polymath to solve ordinary differential equations and we can certainly solve simultaneously a number of ordinary differential equations with this technique.
Explicit methods
The explicit methods are those where the matrix is lower triangular.
Forward Euler
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
The (explicit) midpoint method is a second-order method with two stages (see also the implicit midpoint method below):
Heun's method
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. (Note: The "eu" is pronounced the same way as in "Euler", so "Heun" rhymes with "coin"):
Ralston's method
Ralston's method is a second-order method[1] with two stages and a minimum local error bound:
Generic second-order method
Kutta's third-order method
Generic third-order method
See Sanderse and Veldman (2019).[2]
for α ≠ 0, 2⁄3, 1:
Heun's third-order method
Van der Houwen's/Wray third-order method
Ralston's third-order method
Ralston's third-order method[1] is used in the embedded Bogacki–Shampine method.
Third-order Strong Stability Preserving Runge-Kutta (SSPRK3)
Classic fourth-order method
The "original" Runge–Kutta method.[3]
3/8-rule fourth-order method
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
This fourth order method[1] has minimum truncation error.
Embedded methods
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
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)
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
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
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
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
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
Backward Euler
The backward Euler method is first order. Unconditionally stable and non-oscillatory for linear diffusion problems.
Implicit midpoint
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
The Crank–Nicolson method corresponds to the implicit trapezoidal rule and is a second-order accurate and A-stable method.
Gauss–Legendre methods
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
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 .
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
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
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
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
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
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
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
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
The third-order method is given by
The fifth-order method is given by
Radau IIA methods
The ci of this method are zeros of
- .
The third-order method is given by
The fifth-order method is given by
Notes
- ^ 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
- 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.