Butcher series

B-series

Let $ y : \mathbf R \rightarrow {\mathbf R ^ {d} } $ be an analytic function satisfying an ordinary differential equation $ y ^ \prime ( x ) = f ( y ( x ) ) $. A Butcher series for $ y $ is a series of the form

$$ B ( a,y ( x ) ) = \sum _ {t \in T } a ( t ) F ( t ) ( y ( x ) ) { \frac{h ^ {\rho ( t ) } }{\rho ( t ) ! } } , $$

where $ T $ is the set of rooted trees, $ a ( t ) \in \mathbf R $ is the coefficient for the series associated with the tree $ t $, $ F ( t ) ( y ( x ) ) \in \mathbf R ^ {d} $ is the elementary differential associated with the tree $ t $, $ h \in \mathbf R $ is a stepsize or $ x $- increment, and $ \rho ( t ) $, often called the order of the tree $ t $, is the number of nodes in the tree $ t $. All terms will be defined below. For a more thorough discussion of Butcher series, see [a1] or [a2].

Definitions

A tree is a connected acyclic graph (cf. also Graph). A rooted tree is a tree with a distinguished node, called the root (which is drawn at the bottom of the sample trees in the Table). Two rooted trees $t$ and $\widehat{t}$ are isomorphic (i.e. equivalent) if and only if there is a bijection $\sigma $ from the nodes of $t$ to the nodes of $\widehat{t}$ such that $ \sigma $ maps the root of $ t $ to the root of $ {\widehat{t} } $ and any two nodes $ n _ {1} $ and $ n _ {2} $ are connected by an edge in $ t $ if and only if $ \sigma ( n _ {1} ) $ and $ \sigma ( n _ {2} ) $ are connected by an edge in $ {\widehat{t} } $.

The following bracket notation for rooted trees is very useful. Let $\bullet$ be the tree with one node. For rooted trees $ t_{1} \dots t _ {m} $ with $ \rho ( t _ {i} ) \geq 1 $ for $ i = 1 \dots m $, let $ t = [ t _ {1} \dots t _ {m} ] $ be the rooted tree formed by connecting a new root to the roots of each of $ t _ {1} \dots t _ {m} $. Clearly, $ \rho ( t ) = 1 + \sum _ {i = 1 } ^ {m} \rho ( t _ {i} ) $ and any rooted tree formed by permuting the subtrees $ t _ {1} \dots t _ {m} $ of $ t $ is isomorphic to $ t $.

The rooted trees with at most four nodes are displayed in the table below.

$t_1$	$t_2=[t_1]$	$ t_{3} = [t_{1},t_{1}]$	$t_4 = [t_2]$

$t_5 =[t_1,t_1,t_1]$	$t_6=[t_2,t_1]$	$ t_{7} = [t_{3}]$	$ t_{8} = [t_4]$

Using this bracket notation for rooted trees, one can recursively define elementary differentials, as follows. Let

$$ F ( \emptyset ) ( y ( x ) ) = y ( x ) , \quad F ( \bullet ) ( y ( x ) ) = f ( y ( x ) ) , $$

and, for $ t = [ t _ {1} \dots t _ {m} ] $ with $ \rho ( t _ {i} ) \geq 1 $ for $ i = 1 \dots m $,

$$ F ( t ) ( y ( x ) ) = $$

$$ = f ^ {( m ) } ( y ( x ) ) ( F ( t _ {1} ) ( y ( x ) ) \dots F ( t _ {m} ) ( y ( x ) ) ) , $$

where $ f ^ {( m ) } ( y ( x ) ) $, the $ m $ th derivative of $ f $ with respect to $ y $, is a multi-linear mapping.

Since $ y ( x ) $ satisfies $ y ^ \prime ( x ) = f ( y ( x ) ) $, it is not hard to show that

$$ y ^ {( i ) } ( x ) = \sum _ {t \in T _ {i} } \alpha ( t ) F ( t ) ( y ( x ) ) , $$

where $ y ^ {( i ) } ( x ) $ is the $ i $ th derivative of $ y $ with respect to $ x $, $ T _ {i} = \{ {t \in T } : {\rho ( t ) = i } \} $, and $ \alpha ( t ) $ is the number of distinct ways of labeling the nodes of $ t $ with the integers $ \{ 1 \dots \rho ( t ) \} $ such that the labels increase as you follow any path from the root to a leaf of $ t $. Consequently, one can write the Taylor series for $ y ( x ) $ as a Butcher series:

$$ \tag{a1 } y ( x + h ) = \sum _ {i = 0 } ^ \infty y ^ {( i ) } ( x ) { \frac{h ^ {i} }{i! } } = $$

$$ = \sum _ {t \in T } \alpha ( t ) F ( t ) ( y ( x ) ) { \frac{h ^ {\rho ( t ) } }{\rho ( t ) ! } } . $$

The importance of Butcher series stems from their use to derive and to analyze numerical methods for differential equations. For example, consider the $ s $- stage Runge–Kutta formula (cf. Runge–Kutta method)

$$ \tag{a2 } y _ {n + 1 } = y _ {n} + h \sum _ {i = 1 } ^ { s } b _ {i} k _ {i} , $$

$$ k _ {i} = f \left ( y _ {n} + h \sum _ {j = 1 } ^ { s } a _ {ij } k _ {j} \right ) , $$

for the ordinary differential equation $ y ^ \prime ( x ) = f ( y ( x ) ) $. Let $ b = ( b _ {1} \dots b _ {s} ) ^ {T} \in \mathbf R ^ {s} $ be the vector of weights and $ A = [ a _ {ij } ] \in \mathbf R ^ {s \times s } $ the coefficient matrix for (a2). Then it can be shown that $ y _ {n + 1 } $ can be written as the Butcher series

$$ \tag{a3 } y _ {n + 1 } = \sum _ {t \in T } \alpha ( t ) \psi ( t ) F ( t ) ( y _ {n} ) { \frac{h ^ {\rho ( t ) } }{\rho ( t ) ! } } , $$

where the coefficients $ \psi ( t ) \in \mathbf R $, defined below, depend only on the rooted tree $ t $ and the coefficients of the formula (a2).

To define $ \psi ( t ) $, first let

$$ \phi ( \emptyset ) = ( 1 \dots 1 ) ^ {T} \in \mathbf R ^ {s} , $$

$$ \phi ( \bullet ) = A \phi ( \emptyset ) , $$

and then, for $ t = [ t _ {1} \dots t _ {m} ] $ with $ \rho ( t _ {i} ) \geq 1 $ for $ i = 1 \dots m $, define $ \phi ( t ) $ recursively by

$$ \phi ( t ) = \rho ( t ) A ( \phi ( t _ {1} ) \dots \phi ( t _ {m} ) ) , $$

where the product of $ \phi $' s in the bracket is taken component-wise. Then

$$ \psi ( \emptyset ) = 1, $$

$$ \psi ( \bullet ) = \sum _ {i = 1 } ^ { s } b _ {i} , $$

and, for $ t = [ t _ {1} \dots t _ {m} ] $ with $ \rho ( t _ {i} ) \geq 1 $ for $ i = 1 \dots m $,

$$ \psi ( t ) = \rho ( t ) b ^ {T} ( \phi ( t _ {1} ) \dots \phi ( t _ {m} ) ) , $$

where, again, the product of $ \phi $' s in the bracket is taken componentwise.

Assuming that $ y ( x ) = y _ {n} $ and that $ \psi ( t ) = 1 $ for all trees $ t $ of order $ \leq p $, it follows immediately from (a1) and (a3) that

$$ y _ {n + 1 } = y ( x + h ) + {\mathcal O} ( h ^ {p + 1 } ) . $$

The order of (a2) is the largest such $ p $.

Algebraic aspects

The Butcher series form a group, as they can be composed. This group is sometimes considered from the viewpoint of its Hopf algebra of functions.

The modern understanding of this notion uses the notion of pre-Lie algebras, for the following reasons:

- The Lie algebra of analytic vector fields on the affine space $\RR^d$ comes by anti-symmetrization from the pre-Lie product given by the usual torsion-free and flat connection.

- The free pre-Lie algebra on one generator can be described as the vector space spanned by rooted trees, under some kind of grafting.

Then, by the universal property of free pre-Lie algebras, the choice of any analytic vector field defines uniquely a morphism of pre-Lie algebras, which gives the "elementary differentials" associating a vector field to each rooted tree.

References

[a1]	J.C. Butcher, "The numerical analysis of ordinary differential equations" , Wiley (1987)
[a2]	E. Hairer, S.P. Nørsett, G. Wanner, "Solving ordinary differential equations I: nonstiff problems" , Springer (1987)