Editing Runge–Kutta methods (section)

==Explicit Runge–Kutta methods==
The family of [[Explicit and implicit methods|explicit]] Runge–Kutta methods is a generalization of the RK4 method mentioned above. It is given by
:<math> y_{n+1} = y_n + h \sum_{i=1}^s b_i k_i, </math>
where<ref>{{harvnb|Press|Teukolsky|Vetterling|Flannery|2007|p=907}}</ref>
:<math>
\begin{align}
 k_1 & = f(t_n, y_n), \\
 k_2 & = f(t_n+c_2h, y_n+(a_{21}k_1)h), \\
 k_3 & = f(t_n+c_3h, y_n+(a_{31}k_1+a_{32}k_2)h), \\
     & \ \ \vdots \\
 k_s & = f(t_n+c_sh, y_n+(a_{s1}k_1+a_{s2}k_2+\cdots+a_{s,s-1}k_{s-1})h).
\end{align}
</math>
:(''Note: the above equations may have different but equivalent definitions in some texts.''<ref name=notation />)

To specify a particular method, one needs to provide the integer ''s'' (the number of stages), and the coefficients ''a<sub>ij</sub>'' (for 1 ≤ ''j'' < ''i'' ≤ ''s''), ''b<sub>i</sub>'' (for ''i'' = 1, 2, ..., ''s'') and ''c<sub>i</sub>'' (for ''i'' = 2, 3, ..., ''s''). The matrix [''a<sub>ij</sub>''] is called the ''Runge–Kutta matrix'', while the ''b<sub>i</sub>'' and ''c<sub>i</sub>'' are known as the ''weights'' and the ''nodes''.<ref>{{harvnb|Iserles|1996|p=38}}</ref> These data are usually arranged in a mnemonic device, known as a ''Butcher tableau'' (after [[John C. Butcher]]):

:{| style="text-align: center" cellspacing="0" cellpadding="3"
| style="border-right:1px solid;" | <math> 0 </math>
|-
| style="border-right:1px solid;" | <math> c_2 </math> || <math> a_{21} </math>
|-
| style="border-right:1px solid;" | <math> c_3 </math> || <math> a_{31} </math> || <math> a_{32} </math>
|-
| style="border-right:1px solid;" | <math> \vdots </math> || <math> \vdots </math> || || <math> \ddots </math>
|-
| style="border-right:1px solid; border-bottom:1px solid;" | <math> c_s </math>
| style="border-bottom:1px solid;" | <math> a_{s1} </math>
| style="border-bottom:1px solid;" | <math> a_{s2} </math>
| style="border-bottom:1px solid;" | <math> \cdots </math>
| style="border-bottom:1px solid;" | <math> a_{s,s-1} </math> || style="border-bottom:1px solid;" |
|-
| style="border-right:1px solid;" | || <math> b_1 </math> || <math> b_2 </math> || <math> \cdots </math> || <math> b_{s-1} </math> || <math> b_s </math>
|}

A [[Taylor series]] expansion shows that the Runge–Kutta method is consistent if and only if
:<math>\sum_{i=1}^{s} b_{i} = 1.</math>
There are also accompanying requirements if one requires the method to have a certain order ''p'', meaning that the local truncation error is O(''h<sup>p</sup>''<sup>+1</sup>). These can be derived from the definition of the truncation error itself. For example, a two-stage method has order 2 if ''b''<sub>1</sub> + ''b''<sub>2</sub> = 1, ''b''<sub>2</sub>''c''<sub>2</sub> = 1/2, and ''b''<sub>2</sub>''a''<sub>21</sub> = 1/2.<ref name="Iserles 1996 39">{{harvnb|Iserles|1996|p=39}}</ref> Note that a popular condition for determining coefficients is <ref name="Iserles 1996 39"/>
:<math>\sum_{j=1}^{i-1} a_{ij} = c_i \text{ for } i=2, \ldots, s.</math>
This condition alone, however, is neither sufficient, nor necessary for consistency.
<ref>
As a counterexample, consider any explicit 2-stage Runge-Kutta scheme with <math>b_{1}=b_{2}=1/2</math> and <math>c_1</math> and <math>a_{21}</math> randomly chosen. This method is consistent and (in general) first-order convergent. On the other hand, the 1-stage method with <math>b_1=1/2</math> is inconsistent and fails to converge, even though it trivially holds that <math>\sum_{j=1}^{i-1} a_{ij} = c_i \text{ for } i=2, \ldots, s.</math>.
</ref>

In general, if an explicit <math>s</math>-stage Runge–Kutta method has order <math>p</math>, then it can be proven that the number of stages must satisfy <math>s \ge p</math> and if <math>p \ge 5</math>, then <math>s \ge p+1</math>.<ref>{{harvnb|Butcher|2008|p=187}}</ref>
However, it is not known whether these bounds are ''sharp'' in all cases. In some cases, it is proven that the bound cannot be achieved. For instance, Butcher proved that for <math>p>6</math>, there is no explicit method with <math>s=p+1</math> stages.<ref name="Butcher 1965 408">{{harvnb|Butcher|1965|p=408}}</ref> Butcher also proved that for <math>p>7</math>, there is no explicit Runge-Kutta method with <math>p+2</math> stages.<ref name="Butcher 1985">{{harvnb|Butcher|1985}}</ref> In general, however, it remains an open problem what the precise minimum number of stages <math>s</math> is for an explicit Runge–Kutta method to have order <math>p</math>. Some values which are known are:<ref>{{harvnb|Butcher|2008|pp=187–196}}</ref>
:<math>
\begin{array}{c|cccccccc}
p & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\
\hline
\min s & 1 & 2 & 3 & 4 & 6 & 7 & 9 & 11
\end{array} 
</math>
The provable bound above then imply that we can not find methods of orders <math>p=1, 2, \ldots, 6</math> that require fewer stages than the methods we already know for these orders. The work of Butcher also proves that 7th and 8th order methods have a minimum of 9 and 11 stages, respectively.<ref name="Butcher 1965 408"/><ref name="Butcher 1985"/> An example of an explicit method of order 6 with 7 stages can be found in Ref.<ref>{{harvnb|Butcher|1964}}</ref> Explicit methods of order 7 with 9 stages<ref name="Butcher 1965 408"/> and explicit methods of order 8 with 11 stages<ref>{{harvnb|Curtis|1970|p=268}}</ref> are also known. See Refs.<ref>{{harvnb|Hairer|Nørsett|Wanner|1993|p=179}}</ref><ref>{{harvnb|Butcher|1996|p=247}}</ref> for a summary.

===Examples===
The RK4 method falls in this framework. Its tableau is<ref name="Süli 2003 352">{{harvnb|Süli|Mayers|2003|p=352}}</ref>

:{| style="text-align: center" cellspacing="0" cellpadding="3"
| style="border-right:1px solid;" | 0
|-
| style="border-right:1px solid;" | 1/2 || 1/2
|-
| style="border-right:1px solid;" | 1/2 || 0 || 1/2
|-
| style="border-right:1px solid; border-bottom:1px solid;" | 1 || style="border-bottom:1px solid;" | 0
| style="border-bottom:1px solid;" | 0 || style="border-bottom:1px solid;" | 1
| style="border-bottom:1px solid;" |
|-
| style="border-right:1px solid;" | || 1/6 || 1/3 || 1/3 || 1/6
|}

A slight variation of "the" Runge–Kutta method is also due to Kutta in 1901 and is called the 3/8-rule.<ref>{{harvtxt|Hairer|Nørsett|Wanner|1993|p=138}} refer to {{harvtxt|Kutta|1901}}.</ref> The primary advantage this method has is that almost all of the error coefficients are smaller than in the popular method, but it requires slightly more FLOPs (floating-point operations) per time step. Its Butcher tableau is

:{| style="text-align: center" cellspacing="0" cellpadding="3"
| style="border-right:1px solid;" | 0
|-
| style="border-right:1px solid;" | 1/3 || 1/3
|-
| style="border-right:1px solid;" | 2/3 || −1/3 || 1
|-
| style="border-right:1px solid; border-bottom:1px solid;" | 1 || style="border-bottom:1px solid;" | 1
| style="border-bottom:1px solid;" | −1 || style="border-bottom:1px solid;" | 1
| style="border-bottom:1px solid;" |
|-
| style="border-right:1px solid;" | || 1/8 || 3/8 || 3/8 || 1/8
|}

However, the simplest Runge–Kutta method is the (forward) [[Euler method]], given by the formula <math> y_{n+1} = y_n + hf(t_n, y_n) </math>. This is the only consistent explicit Runge–Kutta method with one stage. The corresponding tableau is

:{| style="text-align: center" cellspacing="0" cellpadding="3"
| width="10" style="border-right:1px solid; border-bottom:1px solid;" | 0
| width="10" style="border-bottom:1px solid;" |
|-
| style="border-right:1px solid;" | || 1
|}

===Second-order methods with two stages===
An example of a second-order method with two stages is provided by the explicit [[midpoint method]]:
:<math> y_{n+1} = y_n + hf\left(t_n+\frac{1}{2}h, y_n+\frac{1}{2}hf(t_n,\ y_n)\right). </math>
The corresponding tableau is

:{| style="text-align: center" cellspacing="0" cellpadding="3"
| style="border-right:1px solid;" | 0
|-
| style="border-right:1px solid; border-bottom:1px solid;" | 1/2 || style="border-bottom:1px solid;" | 1/2 || style="border-bottom:1px solid;" |
|-
| style="border-right:1px solid;" | || 0 || 1
|}

The midpoint method is not the only second-order Runge–Kutta method with two stages; there is a family of such methods, parameterized by α and given by the formula<ref>{{harvnb|Süli|Mayers|2003|p=327}}</ref>

:<math> y_{n+1} = y_n + h\bigl( (1-\tfrac1{2\alpha}) f(t_n, y_n) + \tfrac1{2\alpha} f(t_n + \alpha h, y_n + \alpha h f(t_n, y_n)) \bigr). </math>

Its Butcher tableau is

:{| style="text-align: center" cellspacing="0" cellpadding="8"
| style="border-right:1px solid;" | 0
|-
| style="border-right:1px solid; border-bottom:1px solid;" | <math>\alpha</math> || style="border-bottom:1px solid; text-align: center;" | <math>\alpha</math> || style="border-bottom:1px solid;" |
|-
| style="border-right:1px solid;" | || <math>(1-\tfrac1{2\alpha})</math> || <math>\tfrac1{2\alpha}</math>
|}

In this family, <math>\alpha=\tfrac12</math> gives the [[midpoint method]], <math>\alpha=1</math> is [[Heun's method]],<ref name="Süli 2003 328"/> and <math>\alpha=\tfrac23</math> is Ralston's method.