The first sixth order methods

$$\def\h{\!\!\!\!} \def\m{\;\;} \def\g{\!\!} \def\C{\!\!&\!} \def\ss{\sqrt5}\def\f#1#2{\!\!\!\frac{#1\ss}{#2}\!\!} \def\s{\;\;} \def\C{\!\!&\!\!}$$

The first sixth order methods

John Butcher

In the early 1960s, I came across two papers [A. Huťa, 1956], [A. Huťa, 1957].. The aim in these two papers was to derive Runge–Kutta methods with order 6. At that time of my life, I was trying to learn all I could about Runge–Kutta methods and the work of Huťa seemed to be something I should know about.

It was very difficult to read them because I only had very poor quality microfilms which I had to read in the University library. The mathematics department would not pay for useable prints and all I could afford was a magnifying class and portrait size copies. Nevertheless I was able to get the gist of the work.

The order conditions for a Runge–Kutta method with order $p$ and $s$ stages are a complicated system of polynomial equations up to degree $p$, in $s(s+1)/2$ variables. Above $p=4$, these equations differ for a scalar differential equation and a higher dimensional vector equation. Some details are shown in Table 1.

Table 1
\[ \begin{array}{@{}r|rrrrrrr@{}r@{}} \text{Order} &1&2&3&4&5&6&7&8\\ \hline \text{Scalar DE}&1&2&4&8&16&31\\ \text{Vector DE}&1&2&4&8&17&37\\ \hline \text{Variables}&1&3&6&10&15&21&28&36 \end{array} \] Huťa's work was with the scalar case and, since he was aiming for $p=6$, he concluded that he needed that $s=8$ was necessary to solve $31$ equations in $36$ unknowns. He succeeded in this mammoth task but his achievement uncovered some ironies.
  • If he had known that $37$ conditions had to be solved for a differential equation system of arbitrary dimension, he would have chosen $s=9$ .
  • But, surprisingly, his methods actually satisfy the additional $6$ conditions.
  • Perhaps even more surprisingly, sixth order methods exist which satisfy the $37$ conditions for a high dimensional problem with only $s=7$ stages. This means that a system of $37$ equations in $28$ uknowns has solutions.

In [J.C. Butcher, 1964] new sixth order methods were derived with $s=7$ stages. In this set of methods, a number of assumptions were made to simplify the derivation. These were \[ \begin{array}{r l r l} \sum_{i=1}^7 b_i a_{ij} &\h= b_j(1-c_j), & j=1,\dots,7,\\ \sum_{i=1}^7 a_{ij} c_j&\h= \frac12 c_i^2, & i =3,\dots,7,\\ b_2 &\h= 0,\\ \sum_{i>2} b_i c_i a_{i2}&\h= 0,\\ \sum_{i>2} b_i c_i^2 a_{i2}&\h= 0,\\ \sum_{i>j>2} b_i c_i a_{ij} a_{j2}&\h= 0. \end{array} \] These assumptions can lead to a sixth order method only if \[ c_4 = \frac{c_3}{2-10c_3+15c_3^2}. \] From the methods that arise from these developments, two representative examples are \[ \begin{array}{c|ccccccc} 0 \g&\g\\ \frac13 \g&\g \frac13 \g&\g\\ \frac23 \g&\g 0 \g&\g \frac23 \g&\g\\ \frac13\g&\g\frac1{12} \g&\g \frac13 \g&\g-\frac1{12}\m \g&\g\\ \frac12 \g&\g-\frac1{16}\m \g&\g\frac98 \g&\g -\frac3{16}\m \g&\g -\frac38\m \g&\g\\ \frac12\g&\g0\g&\g\frac98\g&\g-\frac38\m\g&\g-\frac34\m\g&\g\frac12\g&\g\\ 1 \g&\g \frac9{44} \g&\g-\frac9{11} \m\g&\g\frac{63}{44} \g&\g\frac{18}{11} \g&\g 0\g&\g -\frac{16}{11} \m \g&\g\\ \hline \g&\g\frac{11}{120} \g&\g 0 \g&\g \frac{27}{40} \g&\g \frac{27}{40} \g&\g-\frac4{15}\m\g&\g -\frac4{15}\m\g&\g\frac{11}{120} \end{array} \] and \[ \begin{array}{c|ccccccc} 0 \C\\ \frac{1}{2} \C \frac{1}{2}\C\\ \frac{2}{3} \C \frac{2}{9} \C \frac{4}{9}\C\\ \frac{1}{3} \C \frac{7}{36} \C \frac{2}{9} \C -\frac{1}{12}\s\C\\ \frac{5}{6} \C -\frac{35}{144}\s \C -\frac{55}{36}\s \C \frac{35}{48} \C \frac{15}{8}\C\\ \frac{1}{6} \C -\frac{1}{360}\s \C -\frac{11}{36}\s \C -\frac{1}{8}\s \C \frac{1}{2} \C \frac{1}{10}\C\\ 1 \C -\frac{41}{260}\s \C \frac{22}{13} \C \frac{43}{156} \C -\frac{118}{39}\s \C \frac{32}{195} \C\;\; \frac{80}{39}\C\\ \hline \C \frac{13}{200} \C 0 \C \frac{11}{40} \C \frac{11}{40} \C \frac{4}{25} \C \;\;\frac{4}{25} \C\;\: \frac{13}{200} \end{array} \] In addition to methods with rational coefficients, there exist methods based on Lobatto quadrature, such as the following from [J.C. Butcher, 1964] \[ \begin{array}{c|c@{}cccccc} 0&\\ \f{5-}{10} & \f{5-}{10} \\ \f{5+}{10} & \f{-}{10} & \f{5+2}{10} \\ \f{5-}{10} & \f{-15+7}{20} &\f{-1+}{4} & \f{15-7}{10} \\ \f{5+}{10} & \f{5-}{60} &0& \frac16 & \f{15+7}{60} \\ \f{5-}{10} & \f{5+}{60} &0& \f{9-5}{12} & \frac16 & \f{-5+3}{10}\\ 1 & \frac16 & 0 & \!\!\f{-55+25}{12} & \f{-25-7}{12} & \f{5-2}1 &\f{5+}2\\ \hline &\frac1{12} &0&0&0 &\frac5{12}&\frac5{12}&\frac1{12} \end{array}\s \] The significance of $\ss$ in this tableau hinges on a decision to design the method around the Lobatto quadrature formula \[ \int_0^1 f(x) dx \approx \tfrac1{12} f(0) + \tfrac5{12} f(\tfrac{5-\ss}{10})+ \tfrac5{12} f(\tfrac{5+\ss}{10}) + \tfrac1{12} f(1). \] Each of the three methods presented here has been verified to have order 6. There is a wide range of possible seven stage sixth order methods and these are only examples of early methods with this order.

References
[J.C. Butcher, 1963],
Coefficients for the study of Runge–Kutta integration processes, J. Austral. Math. Soc., 3, 185–201.
[J.C. Butcher, 1964],
On Runge–Kutta processes of high order, J. Austral. Math. Soc., 4, 179–194.
[J. C. Butcher, 1987],
The numerical analysis of ordinary differential equations, Wiley, Chichester.
[J.C. Butcher, 2012],
Numerical methods for ordinary differential equations, third edition, John Wiley & Sons Ltd., Chichester.
[G.J. Cooper and J.H. Verner, 1972],
Some explicit Runge–Kutta methods of high order, SIAM J. Numer. Anal., 9, 389–405.
[A. Huťa, 1956],
Une ámelioration de la méthode de Runge–Kutta–Nyström pour la résolution numérique des équations différentielles du premier ordre. Acta Fac. Nat. Univ. Comenian. Math. 1, 201–224.
[A. Huťa, 1957],
Contribution à la formule de sixième ordre dans la méthode de Runge–Kutta–Nyström, Acta Math. Univ. Comenian, 2, 21–24.
[James H. Verner, 1969],
Numerical Solution of Differential Equations, Ph.D. Thesis, Computing Science, University of Edinburgh, Scotland, 187 pages.

$\to$ The birth of B-series
$\to$ The first eighth order methods
$\to$ B-series book