Runge–Kutta–Fehlberg method

In mathematics, the Runge–Kutta–Fehlberg method (or Fehlberg method) is an algorithm in numerical analysis for the numerical solution of ordinary differential equations. It was developed by the German mathematician Erwin Fehlberg and is based on the large class of Runge–Kutta methods.

The novelty of Fehlberg's method is that it is an embedded method from the Runge–Kutta family, meaning that it reuses the same intermediate calculations to produce two estimates of different accuracy, allowing for automatic error estimation. The method presented in Fehlberg's 1969 paper has been dubbed the RKF45 method, and is a method of order O(h⁴) with an error estimator of order O(h⁵).According to Hairer et al. (1993, §II.4), the method was originally proposed in Fehlberg (1969); Fehlberg (1970) is an extract of the latter publication. By performing one extra calculation, the error in the solution can be estimated and controlled by using the higher-order embedded method that allows for an adaptive stepsize to be determined automatically.

Butcher tableau for Fehlberg's 4(5) method

Any Runge–Kutta method is uniquely identified by its Butcher tableau. The embedded pair proposed by Fehlberg{{harvtxt|Hairer|Nørsett|Wanner|1993|p=177}} refer to {{harvtxt|Fehlberg|1969}}

cellpadding=3px cellspacing=0px \|width="20px"\|	style="border-right:1px solid;" \| 0
	style="border-right:1px solid;" \| 1/4	1/4
	style="border-right:1px solid;" \| 3/8	3/32	9/32
	style="border-right:1px solid;" \| 12/13	1932/2197	−7200/2197	7296/2197
	style="border-right:1px solid;" \| 1	439/216	−8	3680/513	−845/4104
	style="border-right:1px solid; border-bottom:1px solid;" \| 1/2	style="border-bottom:1px solid;" \| −8/27	style="border-bottom:1px solid;" \| 2	style="border-bottom:1px solid;" \| −3544/2565	style="border-bottom:1px solid;" \| 1859/4104	style="border-bottom:1px solid;" \| −11/40	style="border-bottom:1px solid;" \|
	style="border-right:1px solid;" \|	16/135	0	6656/12825	28561/56430	−9/50	2/55
	style="border-right:1px solid;" \|	25/216	0	1408/2565	2197/4104	−1/5	0

The first row of coefficients at the bottom of the table gives the fifth-order accurate method, and the second row gives the fourth-order accurate method.

File:Periodic 3-body RKF Integration.gif simulation evolved with the Runge-Kutta-Fehlberg method. Most of the computer time is spent when the bodies pass close by and are susceptible to numerical error.]]

Implementing an RK4(5) Algorithm

The coefficients found by Fehlberg for Formula 1 (derivation with his parameter α₂=1/3) are given in the table below:

class="wikitable"

|+COEFFICIENTS FOR RK4(5), FORMULA 1 Table II in Fehlberg{{Failed verification|date=January 2025|reason=Someone reported that the coefficients in the below table do not work. You can help by correcting them, or by removing this "failed verification" template if they are correct.}}

! rowspan="2" |K

! rowspan="2" |A(K)

! colspan="5" |B(K,L)

! rowspan="2" |C(K)

! rowspan="2" |CH(K)

! rowspan="2" |CT(K)

L=1

|L=2

|L=3

|L=4

|L=5

| rowspan="2" |

| rowspan="3" |

| rowspan="4" |

| rowspan="5" |

|1/9

|47/450

| 1/150

|2/9

|1/3

|1/12

|1/4

|9/20

|12/25

| -3/100

|3/4

|69/128

| -243/128

|135/64

|16/45

|32/225

| 16/75

| -17/12

|27/4

| -27/5

|16/15

|1/12

|1/30

| 1/20

|5/6

|65/432

| -5/16

|13/16

|4/27

|5/144

|6/25

| -6/25

Fehlberg outlines a solution to solving a system of n differential equations of the form:

$\frac{dy_i}{dx} = f_i(x,y_1,y_2, \ldots, y_n), i=1,2,\ldots,n$

to iterative solve for

$y_i(x+h), i=1,2,\ldots,n$

where h is an adaptive stepsize to be determined algorithmically:

The solution is the weighted average of six increments, where each increment is the product of the size of the interval, $h$ , and an estimated slope specified by function f on the right-hand side of the differential equation.

$\begin{align}
k_1&=h\cdot f(x+A(1) \cdot h,y) \\
k_2&=h\cdot f(x+A(2)\cdot h,y+B(2,1)\cdot k_1) \\
k_3&=h\cdot f(x+A(3)\cdot h, y+B(3,1)\cdot k_1+B(3,2)\cdot k_2 ) \\
k_4&=h\cdot f(x+A(4)\cdot h, y+B(4,1)\cdot k_1+B(4,2)\cdot k_2+B(4,3)\cdot k_3 ) \\
k_5&=h\cdot f(x+A(5)\cdot h, y+B(5,1)\cdot k_1+B(5,2)\cdot k_2+B(5,3)\cdot k_3+B(5,4)\cdot k_4 ) \\
k_6&=h\cdot f(x+A(6)\cdot h, y+B(6,1)\cdot k_1+B(6,2)\cdot k_2+B(6,3)\cdot k_3+B(6,4)\cdot k_4+B(6,5) \cdot k_5)
\end{align}$

Then the weighted average is:

$y(x+h)=y(x) + CH(1) \cdot k_1 + CH(2) \cdot k_2 + CH(3) \cdot k_3 + CH(4) \cdot k_4 + CH(5) \cdot k_5 + CH(6) \cdot k_6$

The estimate of the truncation error is:

$\mathrm{TE} = \left|\mathrm{CT}(1) \cdot k_1 + \mathrm{CT}(2) \cdot k_2 + \mathrm{CT}(3) \cdot k_3 + \mathrm{CT}(4) \cdot k_4 + \mathrm{CT}(5) \cdot k_5 + \mathrm{CT}(6) \cdot k_6\right|$

At the completion of the step, a new stepsize is calculated:{{cite web |last1=Gurevich |first1=Svetlana |title=Appendix A Runge-Kutta Methods |url=https://www.uni-muenster.de/imperia/md/content/physik_tp/lectures/ss2017/numerische_Methoden_fuer_komplexe_Systeme_II/rkm-1.pdf |website=Munster Institute for Theoretical Physics |access-date=4 March 2022 |pages=8–11 |date=2017}}

$h_{\text{new}} = 0.9 \cdot h \cdot \left ( \frac {\varepsilon} {TE} \right )^{1/5}$

If $\mathrm{TE} > \varepsilon$ , then replace $h$ with $h_{\text{new}}$ and repeat the step. If $TE\leqslant\varepsilon$ , then the step is completed. Replace $h$ with $h_{\text{new}}$ for the next step.

The coefficients found by Fehlberg for Formula 2 (derivation with his parameter α₂ = 3/8) are given in the table below, using array indexing of base 1 instead of base 0 to be compatible with most computer languages:

class="wikitable"

|+COEFFICIENTS FOR RK4(5), FORMULA 2 Table III in Fehlberg

! rowspan="2" |K

! rowspan="2" |A(K)

! colspan="5" |B(K,L)

! rowspan="2" |C(K)

! rowspan="2" |CH(K)

! rowspan="2" |CT(K)

L=1

|L=2

|L=3

|L=4

|L=5

| rowspan="2" |

| rowspan="3" |

| rowspan="4" |

| rowspan="5" |

|25/216

|16/135

| -1/360

|1/4

|3/8

|3/32

|9/32

|1408/2565

|6656/12825

| 128/4275

|12/13

|1932/2197

| -7200/2197

|7296/2197

|2197/4104

|28561/56430

| 2197/75240

|439/216

| -8

|3680/513

| -845/4104

| -1/5

| -9/50

| -1/50

|1/2

| -8/27

| -3544/2565

|1859/4104

| -11/40

|2/55

| -2/55

In another table in Fehlberg, coefficients for an RKF4(5) derived by D. Sarafyan are given:

class="wikitable"

|+COEFFICIENTS FOR Sarafyan's RK4(5), Table IV in Fehlberg

! rowspan="2" |K

! rowspan="2" |A(K)

! colspan="5" |B(K,L)

! rowspan="2" |C(K)

! rowspan="2" |CH(K)

! rowspan="2" |CT(K)

L=1

|L=2

|L=3

|L=4

|L=5

| rowspan="2" |

| rowspan="3" |

| rowspan="4" |

| rowspan="5" |

|1/6

|1/24

| 1/8

|1/2

|1/4

|2/3

| 2/3

| -1

|1/6

|5/48

| 1/16

|2/3

|7/27

|10/27

|1/27

|27/56

| -27/56

|1/5

|28/625

| -1/5

|546/625

|54/625

| -378/625

|125/336

| -125/336

Notes

References

Fehlberg, Erwin (1968) Classical fifth-, sixth-, seventh-, and eighth-order Runge-Kutta formulas with stepsize control. NASA Technical Report 287. https://ntrs.nasa.gov/api/citations/19680027281/downloads/19680027281.pdf
Fehlberg, Erwin (1969) Low-order classical Runge-Kutta formulas with stepsize control and their application to some heat transfer problems. Vol. 315. National aeronautics and space administration.
{{cite journal|last1=Fehlberg|first1=Erwin |year=1969|title=Klassische Runge-Kutta-Nystrom-Formeln funfter und siebenter Ordnung mit Schrittweiten-Kontrolle |journal=Computing |volume=4 |pages=93–106 |doi=10.1007/BF02234758|s2cid=38715401}}
Fehlberg, Erwin (1970) Some experimental results concerning the error propagation in Runge-Kutta type integration formulas. NASA Technical Report R-352. https://ntrs.nasa.gov/api/citations/19700031412/downloads/19700031412.pdf
Fehlberg, Erwin (1970). "Klassische Runge-Kutta-Formeln vierter und niedrigerer Ordnung mit Schrittweiten-Kontrolle und ihre Anwendung auf Wärmeleitungsprobleme," Computing (Arch. Elektron. Rechnen), vol. 6, pp. 61–71. {{doi|10.1007/BF02241732}}
{{cite book |first1=Ernst |last1=Hairer |first2=Syvert |last2=Nørsett |first3=Gerhard |last3=Wanner |date=1993 |title=Solving Ordinary Differential Equations I: Nonstiff Problems |edition=Second |publisher=Springer-Verlag |location=Berlin |isbn=3-540-56670-8}}
Sarafyan, Diran (1966) Error Estimation for Runge-Kutta Methods Through Pseudo-Iterative Formulas. Technical Report No. 14, Louisiana State University in New Orleans, May 1966.

Runge–Kutta–Fehlberg method

Butcher tableau for Fehlberg's 4(5) method

Implementing an RK4(5) Algorithm

See also

Notes

References

Further reading