The constrains of Butcher tableau

Question

Related posts(but did not answer the question):

1. deriving an implicit Runge Kutta method from its Butcher tableau

2. Understanding the Butcher tableau of implicit midpoint method

3. butcher tableau for given algorithm

4. butcher tableau runge kutta methods

One Wikipedia's webpage, Runge-Kutta methods could be generally described by Butcher tableau. However, it did not explain how to obtain the Butcher tableau.

There were several constrains

1. $\sum_{i=1}^s b_i=1$ for the consistence of Runge-Kutta method.

2. A "popular condition" for determining coefficients: $\sum_{j=1}^{i-1}a_{ij}=c_i$.

But then it left without comment as if one could just put any number there, but there was also example of generic second order and third order method which seemed to indicate further constrains on $b_i$, $c_i$, and $a_{ij}$.

My question was

1.a. how to obtain/calculate the Butcher tableau. What were the constrains exactly?

1.b. Especially, how was $a_ij$ being chosen under those constrains?(For example, how was "RK 3/8-rule" being read, since there were negative coefficients in $a_{ij}$)

1.c. Why was $\sum_{j=1}^{i-1}a_{ij}=c_i$ popular? Is this an explicit constrains or just a convention?

Answer 1

$\sum a_{ij}=c_i$: Consider the differential equation $\dot x(t)=1$, $x(0)=0$. Then it is quite reasonable to request that in the whole solution process the $x$ values are equal to the $t$ values. In general it should not make a difference if you consider a general ODE or its autonomous form.

If you can somewhat read German, go to the ultimate source, the article by M. Wilhelm Kutta "Beitrag zur näherungsweisen Lösung totaler Differentialgleichungen" is a quite explicit answer to your question. His approach for the low-order explicit methods is to completely solve the coefficient equations, then select a quadrature method for the $c_i$ and $b_i$, symmetry constraints and zero coefficients. These then mostly determine the tableau.

For the higher-order explicit methods, where the number of stages is larger than the order, equations are added for structural constraints that simplify the order conditions, demands on the approximation orders of intermediate points, also in view of constructing a "dense output" interpolation, constructing an embedded method, first-same-as-last, and again zero patterns in the matrix. Then often some of the coefficients of the leading error term are selected for minimization, the system is solved. If possible, the solution is perturbed into a close-by rational solution.

With implicit methods one has even more freedom to add constraints. A common method is to use the collocation approach. Others are to make the matrix lower-triangular giving semi-implicit methods where each stage equation can be solved separately, then making the diagonal entries all the same, so that their simplified Newton methods can all use the same Jacobi matrix and its factorization.