$$\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
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