List of Runge–Kutta methods

From The Right Wiki
Jump to navigationJump to search

Runge–Kutta methods are methods for the numerical solution of the ordinary differential equation

dydt=f(t,y).

Explicit Runge–Kutta methods take the form

yn+1=yn+hi=1sbikik1=f(tn,yn),k2=f(tn+c2h,yn+h(a21k1)),k3=f(tn+c3h,yn+h(a31k1+a32k2)),ki=f(tn+cih,yn+hj=1i1aijkj).

Stages for implicit methods of s stages take the more general form, with the solution to be found over all s

ki=f(tn+cih,yn+hj=1saijkj).

Each method listed on this page is defined by its Butcher tableau, which puts the coefficients of the method in a table as follows:

c1a11a12a1sc2a21a22a2scsas1as2assb1b2bs

For adaptive and implicit methods, the Butcher tableau is extended to give values of bi*, and the estimated error is then

en+1=hi=1s(bibi*)ki.

Explicit methods

The explicit methods are those where the matrix [aij] is lower triangular.

First-order methods

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.

001

Second-order methods

Generic second-order method

Second-order methods can be generically written as follows:[1]

000αα0112α12α

with α ≠ 0.

Explicit midpoint method

The (explicit) midpoint method is a second-order method with two stages (see also the implicit midpoint method below):

0001/21/2001

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:

0001101/21/2

Ralston's method

Ralston's method is a second-order method[2] with two stages and a minimum local error bound:

0002/32/301/43/4

Third-order methods

Generic third-order method

Third-order methods can be generically written as follows:[1]

0000αα00ββαβ3α(1α)(3α2)βαβα(3α2)013α+3β26αβ3β26α(βα)23α6β(βα)

with α ≠ 0, α23, β ≠ 0, and αβ.

Kutta's third-order method

00001/21/20011201/62/31/6

Heun's third-order method

00001/31/3002/302/301/403/4

Ralston's third-order method

Ralston's third-order method[2] has a minimum local error bound and is used in the embedded Bogacki–Shampine method.

00001/21/2003/403/402/91/34/9

Van der Houwen's/Wray's third-order method

00008/158/15002/31/45/1201/403/4

Third-order Strong Stability Preserving Runge-Kutta (SSPRK3)

000011001/21/41/401/61/62/3

Fourth-order methods

Classic fourth-order method

The "original" Runge–Kutta method.[3]

000001/21/20001/201/200100101/61/31/31/6

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]

000001/31/30002/31/3100111101/83/83/81/8

Ralston's fourth-order method

This fourth order method[2] has minimum truncation error.

0000025250001435162889+14285102437851620510240013365+209456040975304652552467040+20396852408450263+24518121251000538283426304+1661952559247873045123

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

yn+1*=yn+hi=1sbi*ki,

where the ki are the same as for the higher order method. Then the error is

en+1=yn+1yn+1*=hi=1s(bibi*)ki,

which is O(hp). The Butcher Tableau for this kind of method is extended to give the values of bi*

c1a11a12a1sc2a21a22a2scsas1as2assb1b2bsb1*b2*bs*

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:

0111/21/210

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:

01/41/43/83/329/3212/131932/21977200/21977296/21971439/21683680/513845/41041/28/2723544/25651859/410411/4016/13506656/1282528561/564309/502/5525/21601408/25652197/41041/50

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.

111

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.

1/21/2

Crank-Nicolson method

The Crank–Nicolson method corresponds to the implicit trapezoidal rule and is a second-order accurate and A-stable method.

00011/21/21/21/2

Gauss–Legendre methods

These methods are based on the points of Gauss–Legendre quadrature. The Gauss–Legendre method of order four has Butcher tableau:

123614143612+3614+3614121212+321232

The Gauss–Legendre method of order six has Butcher tableau:

121510536291515536153012536+152429536152412+1510536+153029+151553651849518568356

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:

1/21/203/21/221/23/2

Qin and Zhang's two-stage, 2nd order, symplectic Diagonally Implicit Runge–Kutta method:

1/41/403/41/21/41/21/2

Pareschi and Russo's two-stage 2nd order Diagonally Implicit Runge–Kutta method:

xx01x12xx1212

This Diagonally Implicit Runge–Kutta method is A-stable if and only if x14. Moreover, this method is L-stable if and only if x equals one of the roots of the polynomial x22x+12, i.e. if x=1±22. Qin and Zhang's Diagonally Implicit Runge–Kutta method corresponds to Pareschi and Russo's Diagonally Implicit Runge–Kutta method with x=1/4. Two-stage 2nd order Diagonally Implicit Runge–Kutta method:

xx011xx1xx

Again, this Diagonally Implicit Runge–Kutta method is A-stable if and only if x14. As the previous method, this method is again L-stable if and only if x equals one of the roots of the polynomial x22x+12, i.e. if x=1±22. This condition is also necessary for 2nd order accuracy. Crouzeix's two-stage, 3rd order Diagonally Implicit Runge–Kutta method:

12+3612+36012363312+361212

Crouzeix's three-stage, 4th order Diagonally Implicit Runge–Kutta method:

1+α21+α20012α21+α201α21+α(1+2α)1+α216α2113α216α2

with α=23cosπ18. Three-stage, 3rd order, L-stable Diagonally Implicit Runge–Kutta method:

xx001+x21x2x013x2/2+4x1/43x2/25x+5/4x3x2/2+4x1/43x2/25x+5/4x

with x=0.4358665215 Nørsett's three-stage, 4th order Diagonally Implicit Runge–Kutta method has the following Butcher tableau:

xx001/21/2xx01x2x14xx16(12x)23(12x)213(12x)216(12x)2

with x one of the three roots of the cubic equation x33x2/2+x/21/24=0. The three roots of this cubic equation are approximately x1=1.06858, x2=0.30254, and x3=0.12889. The root x1 gives the best stability properties for initial value problems. Four-stage, 3rd order, L-stable Diagonally Implicit Runge–Kutta method

1/21/20002/31/61/2001/21/21/21/2013/23/21/21/23/23/21/21/2

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:

00011/21/21/21/210

The fourth-order method is given by

00001/25/241/31/2411/62/31/61/62/31/612212

These methods are A-stable, but neither L-stable nor B-stable [8]

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

01/2011/201/21/210

The fourth-order method is given by

01/61/601/21/61/3011/65/601/62/31/612212

Lobatto IIIB methods are A-stable, but neither L-stable nor B-stable[6].

Lobatto IIIC methods

The Lobatto IIIC methods also are discontinuous collocation methods. The second-order method is given by

01/21/211/21/21/21/210

The fourth-order method is given by

01/61/31/61/21/65/121/1211/62/31/61/62/31/612212

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

0001101/21/2

Butcher's three-stage, fourth-order method is given by

00001/21/41/4010101/62/31/6

These methods are not A-stable, B-stable or L-stable. The Lobatto IIIC* method for s=2 is sometimes called the explicit trapezoidal rule.

Generalized Lobatto methods

One can consider a very general family of methods with three real parameters (αA,αB,αC) by considering Lobatto coefficients of the form

ai,j(αA,αB,αC)=αAai,jA+αBai,jB+αCai,jC+αC*ai,jC*,

where

αC*=1αAαBαC.

For example, Lobatto IIID family introduced in (Nørsett and Wanner, 1981), also called Lobatto IIINW, are given by

01/21/211/21/21/21/2

and

01/601/61/21/125/12011/21/31/61/62/31/6

These methods correspond to αA=2, αB=2, αC=1, and αC*=2. 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.

Radau IA methods

The first order method is similar to the backward Euler method and given by

011

The third-order method is given by

01/41/42/31/45/121/43/4

The fifth-order method is given by

01916181+61835610191145+76360114543636035+610191145+4363601145763601949+63649636

Radau IIA methods

The ci of this method are zeros of

ds1dxs1(xs1(x1)s).

The first-order method is equivalent to the backward Euler method. The third-order method is given by

1/35/121/1213/41/43/41/4

The fifth-order method is given by

2561011457636037225169618002225+67525+61037225+169618001145+76360222567514963649+636194963649+63619

Notes

  1. 1.0 1.1 Butcher, John C. (2003). Numerical Methods for Ordinary Differential Equations. John Wiley. ISBN 978-0-471-96758-3.
  2. 2.0 2.1 2.2 Ralston, Anthony (1962). "Runge-Kutta Methods with Minimum Error Bounds". Math. Comput. 16 (80): 431–437. doi:10.1090/S0025-5718-1962-0150954-0.
  3. 3.0 3.1 Kutta, Martin (1901). "Beitrag zur näherungsweisen Integration totaler Differentialgleichungen". Zeitschrift für Mathematik und Physik. 46: 435–453.
  4. 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).
  5. 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.
  6. 6.0 6.1 6.2 6.3 See Laurent O. Jay (N.D.). "Lobatto methods". University of Iowa
  7. Ehle (1969)
  8. Cite error: Invalid <ref> tag; no text was provided for refs named jay

References