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 expansions of the ODE \(y'=f(t,y)\) and the general form of a Runge-Kutta method to derive a set of order conditions 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. 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

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

• The density of a rooted tree \(\tau\), denoted by \(\gamma(\tau)\), 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 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(\tau)\).

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(\tau)=7\).

Assigning the weights to the nodes gives

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

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

Consider the derivatives of the function \(y = f(y)\) using the product and chain rules

(2.13)\[\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}\]

As you can see this soon becomes complication, however, 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).

\(T\)
\(r(\tau)\)	1	2	3	4
\(\gamma(\tau)\)	\(\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.13) is equal to \(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 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(\tau)\). To generate \(\Phi(\tau)\) we use the following steps:

• associate a label \(i\) to the root node and for all non-leaf nodes associate unique labels \(j\), \(k\), \(\ell\) 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(\tau) &= \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*} \]

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.14)\[\Phi(\tau) = \dfrac{1}{\gamma(\tau)}.\]

So to derive the order conditions for a \(k\)-th order \(s\)-stage Runge-Kutta method we determine the set \(T\) of all rooted trees of order up to and include \(k\). We then use the condition from equation (2.14) for each tree in \(T\) to determine the order conditions. In addition to these order conditions there is also a condition placed on the value of \(c_i\)

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

i.e., the values of \(c_i\) are equal to the sum of the rows of the \(A\) matrix, hence this is called the **row sum condition.

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 is \(T = \left\{ \tau_1, \tau_2 \right\} = \left\{ \right.\) \(,\)\(\left. \right\}\)

The elementary weights and densities of these trees are

\[\begin{split} \begin{align*} \phi(\tau_1) &= \sum_{j = 1}^2 b_i, & \gamma(\tau_1) &= 1, \\ \phi(\tau_2) &= \sum_{j = 1}^2 b_ic_i, & \gamma(\tau_2) &= 2. \end{align*} \end{split}\]

Using equation (2.14) and the row sum condition from equation (2.15) we have the following order conditions

\[\begin{split} \begin{align*} b_1 + b_2 &= 1, \\ b_1c_1 + b_2c_2 &= \frac{1}{2}, \\ c_1 &= a_{11} + a_{12}, \\ c_2 &= a_{21} + a_{22}. \end{align*} \end{split}\]

Since we are deriving an ERK method, \(a_{11} = a_{12} = a_{22} = c_1 = 0\) and these simplify to

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

These are the same order condition derived in the previous section.

---

[1]

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