2.4. Deriving order conditions using trees

In the previous section we saw that to derive an Explicit Runge-Kutta (ERK) method we equate Taylor series expansions of the ODE \(y'=f(t,y)\) and the general form of a Runge-Kutta method to derive a set of order condtions which need to be satisfied. This means we need to evaluate the derivatives of the bivariate function \(f(t,y)\) which can soon get complicated as we increase the order. To simplify the derivation we consider the autonomous system of the form \(y'=f(y)\). Applying the product and chain rules to evaluate the derivatives

(2.12)\[\begin{split} \begin{align*} y' &= f(y), \\ y'' &= f'(y)y' \\ &= (f'f)(y), \\ y''' &= f''(y)(f(y), f'(y)) + f'(y)f'(y)y' \\ &= (f''(f,f) + f'f'f)(y) \\ &\vdots \end{align*}\end{split}\]

So we can see this soon gets quite complicated. Fortunately there is an easier way that uses rooted trees.

2.4.1. Trees

A rooted tree is a tree where a single node is designated as the root. Rooted trees are usually drawn with the root node at the bottom of the tree.

Fig. 2.5 An example of a rooted tree.

We now define the properties of order and density of a rooted tree

Definition 2.4 (Order of a rooted tree)

The order, \(r\), of a rooted tree is the total number of nodes in the tree.

Definition 2.5 (Density of a rooted tree)

The density, \(\gamma\), of a rooted tree is a measure related to the number of nodes and the children of the notes in the tree. The density can be calculated using the following:

• assign a value of 1 to each leaf node (a node with no children) in the tree;

• for all non-leaf nodes assign a value of 1 more than the sum of the values of their child nodes;

• calculate the product the values of all nodes in the tree which gives \(\gamma\).

Example 2.3

Determine the order and density of the rooted tree shown below.

Solution (click to show)

There are 7 nodes in this tree so \(r=7\).

Assigning the weights to the nodes gives

So \(\gamma = 7 \cdot 1 \cdot 3 \cdot 2 \cdot 1 \cdot 1 \cdot 1 = 42\)

Determining derivatives of \(f(y)\) using rooted trees

English mathematician Robert Merson [Merson, 1957] noticed that the structure of rooted trees matches that of the derivatives of \(f(y)\). Defining a rooted tree notation where \(\vec{f}\) denotes a node of the tree and the number of children the node has is denoted by a prime, e.g., \(\vec{f}''\) denotes a node has two children. A child node is written immediately following the parent node and sibling nodes are separated by a comma (using brackets if there are more than one child). A rooted tree can be represented as an expressing involving each node, examples of this are given in Table 2.1.

Table 2.1 Rooted trees of order 3 or below.

Tree
Order	1	2	3	3
Notation	\(\vec{f}\)	\(\vec{f}'\vec{f}\)	\(\vec{f}''(\vec{f},\vec{f})\)	\(\vec{f}'\vec{f}'\vec{f}\)

So how do rooted trees relate to the derivatives of \(f(y)\)? Consider the only rooted tree of order 2 which is \(\vec{f}'\vec{f}\). If we write \(\vec{f} = f(y)\) then

\[\vec{f}'\vec{f} = f'f(y)\]

which as we saw in equation (2.12) is equal to \(y''\) when \(y' = f(y)\). We can extend this to determine the derivative \(y'''\), the two rooted trees of order 3 are \(\vec{f}''(\vec{f},\vec{f})\) and \(\vec{f}'\vec{f}'\vec{f}\). Summing these gives

\[ \vec{f}''(\vec{f},\vec{f}) + \vec{f}'\vec{f}'\vec{f} = (f''(f,f) + f'f'f)(y) = y'''\]

So we can determine the \(N\)-th derivative \(y^{(N)}\) where \(y'=f(y)\) by summing the rooted tree notation of all of the possible \(N\)-th order rooted trees.

2.4.2. Order conditions of an ERK method using trees

We can also derive the order conditions of a Runge-Kutta method using rooted trees. To determine the values of \(a_{ij}\), \(b_i\) and \(c_i\) in the Butcher tableau we define a set of elementary weights, denoted by \(\Phi\), that are generated by the rooted trees using the following process:

• associate the label \(i\) to the root node and for each other non-leaf node associate unique labels \(j\), \(k\), etc;

• write down a sequence of factors for which the first is \(b_i\);

• for each edge that does not terminate in a leaf node, write down another factor \(a_{pq}\) where \(p\) and \(q\) are the labels associated with the parent and child node respectively;

• for each leaf node write down a factor \(c_p\) where \(p\) is the label associated with the parent node;

• sum the product of factors for all possible choices of the labels.

Example 2.4

Determine the elementary weight for the rooted tree shown below.

Solution (click to show)

Assigning the labels to the non-leaf nodes gives

So the elementary weight is

\[ \begin{align*} \Phi &= \sum_{i,j,k} b_ia_{ij} a_{ik} c_ic_jc_jc_k = \sum_{i,j,k} b_ia_{ij} a_{ik} c_ic_j^2c_k. \end{align*} \]

John Butcher noticed that comparing the Taylor series expansions for the autonomous ODE \(y'=f(y)\) and the general form of a Runge-Kutta method gives the order condition [1]

(2.13)\[\Phi = \dfrac{1}{\gamma}.\]

To derive the order conditions for a \(k\)-th order \(s\)-stage Runge-Kutta method we do the following:

• determine the set \(T\) of all rooted trees of order up to and including \(k\);

• determine the density and elementary weights summed to the number of stages \(s\) for all trees in \(T\);

• use equation (2.13) to determine the order condition for each tree in \(T\);

• if we don’t have order conditions that include all of the unknowns we apply the row sum condition which is

(2.14)\[c_i = \sum_{j=1}^sa_{ij}\]

Example 2.5

Use trees to derive the order conditions for a 2-stage second-order explicit Runge-Kutta method.

Solution (click to show)

The set of all rooted trees up to and including order 2 are

Tree
Order	1	2
\(\Phi\)	\(\displaystyle\sum_i b_i\)	\(\displaystyle\sum_i b_i c_i\)
\(\gamma\)	1	2

Using equation (2.13) and summing the elementary weights to \(s=2\) the order conditions for a second-order method are (remember that \(c_1=0\))

\[\begin{split} \begin{align*} b_1 + b_2 &= 1, \\ b_2c_2 &= \frac{1}{2}. \end{align*} \end{split}\]

We also need to determine a value for \(a_{21}\) which isn’t included in the order conditions above. Using the row sum condition for the second row we have

\[ \begin{align*} a_{21} = c_2. \end{align*} \]

We now have the three order conditions for a second-order ERK method which were derived in the previous section.

---

[1]

I’ve skipped the derivation here, for details see Butcher [2008].