**NumericalMath****`****Butcher****`**

Runge-Kutta methods are useful for numerically solving certain types of ordinary differential equations. Deriving high-order Runge-Kutta methods is no easy task, however. There are several reasons for this. The first difficulty is in finding the so-called order conditions. These are nonlinear equations in the coefficients for the method that must be satisfied to make the error in the method of order for some integer where is the step size. The second difficulty is in solving these equations. Besides being nonlinear, there is generally no unique solution, and many heuristics and simplifying assumptions are usually made. Finally, there is the problem of combinatorial explosion. For a twelfth-order method there are 7813 order conditions!

This package performs the first task: finding the order conditions that must be satisfied. The result is expressed in terms of unknown coefficients , , and . The -stage Runge-Kutta method to advance from to

is then

where

Sums of the elements in the rows of the matrix occur repeatedly in the conditions imposed on and . In recognition of this and as a notational convenience it is usual to introduce the coefficients

and the definition

This definition is referred to as the row-sum condition and is the first in a sequence of row-simplifying conditions.

If for all the method is explicit; that is, each of the is defined in terms of previously computed values. If the matrix is not strictly lower triangular, the method is implicit and requires the solution of a (generally nonlinear) system of equations for each timestep. A diagonally implicit method has for all .

There are several ways to express the order conditions. If the number of stages is specified as a positive integer, the order conditions are expressed in terms of sums of explicit terms. If the number of stages is specified as a symbol, the order conditions will involve symbolic sums. If the number of stages is not specified at all, the order conditions will be expressed in stage-independent tensor notation. In addition to the matrix a and the vectors b and c, this notation involves the vector e, which is composed of all ones. This notation has two distinct advantages: it is independent of the number of stages

and it is independent of the particular Runge-Kutta method.

For further details of the theory see the references.

Notation used by functions in NumericalMath`Butcher`.

Functions associated with the order conditions of Runge-Kutta methods.

Some options for RungeKuttaOrderConditions.

This loads the package.
In[1]:= **<< NumericalMath`Butcher`**

This gives the number of order conditions for each order up through order

. Notice the combinatorial explosion.
In[2]:= **Length /@ RungeKuttaOrderConditions[10]**

Out[2]=

This gives the order conditions that must be satisfied by any first-order, 3-stage Runge-Kutta method, explicitly including the row-sum conditions.
In[3]:= **RungeKuttaOrderConditions[1, 3,**

ButcherRowSum -> True]

Out[3]=

These are the order conditions that must be satisfied by any second-order, 3-stage Runge-Kutta method. Here the row-sum conditions are not included.
In[4]:= **RungeKuttaOrderConditions[2, 3]**

Out[4]=

It should be noted that the sums involved on the left-hand sides of the order conditions will be left in symbolic form and not expanded if the number of stages is left as a symbolic argument. This will greatly simplify the results for high-order, many-stage methods. An even more compact form results if you do not specify the number of stages at all and the answer is given in tensor form.

These are the order conditions that must be satisfied by any second-order,

-stage method.
In[5]:= **RungeKuttaOrderConditions[2, s]**

Out[5]=

Replacing s by 3 gives the same result as RungeKuttaOrderConditions[2,3].
In[6]:= **% /. s -> 3**

Out[6]=

These are the order conditions that must be satisfied by any second-order method. This uses tensor notation. The vector e is a vector of ones whose length is the number of stages.
In[7]:= **RungeKuttaOrderConditions[2]**

Out[7]=

The tensor notation can likewise be expanded to give the conditions in full.
In[8]:= **% /. {a -> Array[a,{3,3}], b -> Array[b,3],**

c -> Array[c,3], e -> {1,1,1}}

Out[8]=

These are the principal error coefficients for any third-order method.
In[9]:= **ButcherPrincipalError[3]**

Out[9]=

This is a bound on the local error of any third-order method in the limit as h approaches 0, normalized to eliminate the effects of the ODE.
In[10]:= **(Plus @@ Abs[%]) h^4**

Out[10]=

Here are the order conditions that must be satisfied by any fourth-order, 1-stage Runge-Kutta method. Note that there is no possible way for these order conditions to be satisfied; there need to be more stages (the second argument must be larger) for there to be sufficiently many unknowns to satisfy all of the conditions.
In[11]:= **RungeKuttaOrderConditions[4, 1]**

Out[11]=

Controlling the type of Runge-Kutta method in RungeKuttaOrderConditions and related functions.

RungeKuttaOrderConditions and certain related functions have the option RungeKuttaMethod with default setting $RungeKuttaMethod. Normally you will want to determine the Runge-Kutta method being considered by setting $RungeKuttaMethod to one of Implicit, DiagonallyImplicit, and Explicit, but you can specify an option setting or even change the default for an individual function.

These are the order conditions that must be satisfied by any second-order, 3-stage diagonally implicit Runge-Kutta method.
In[12]:= **RungeKuttaOrderConditions[2, 3,**

RungeKuttaMethod -> DiagonallyImplicit]

Out[12]=

An alternative (but less efficient) way to get a diagonally implicit method is to force a to be lower triangular by replacing upper-triangular elements with 0.
In[13]:= **RungeKuttaOrderConditions[2, 3] /.**

a[i_,j_]:>0 /; i<j

Out[13]=

These are the order conditions that must be satisfied by any third-order, 2-stage explicit Runge-Kutta method. The contradiction in the order conditions indicates that no such method is possible, a result which holds for any explicit Runge-Kutta method when the number of stages is less than the order.
In[14]:= **RungeKuttaOrderConditions[3, 2,**

RungeKuttaMethod -> Explicit]

Out[14]=

More functions associated with the order conditions of Runge-Kutta methods.

Butcher showed that the number and complexity of the order conditions can be reduced considerably at high orders by the adoption of so-called simplifying assumptions. For example, this reduction can be accomplished by adopting sufficient row and column simplifying assumptions and quadrature-type order conditions. The option ButcherSimplify in RungeKuttaOrderConditions can be used to determine these automatically.

These are the column simplifying conditions up to order 4.
In[15]:= **ButcherColumnConditions[4]**

Out[15]=

These are the row simplifying conditions up to order 4.
In[16]:= **ButcherRowConditions[4]**

Out[16]=

These are the quadrature conditions up to order 4.
In[17]:= **ButcherQuadratureConditions[4]**

Out[17]=

Trees are fundamental objects in Butcher's formalism. They yield both the derivative in a power series expansion of a Runge-Kutta method and the related order constraint on the coefficients. This package provides a number of functions related to Butcher trees.

Constructing and enumerating Butcher trees.

This gives the trees that are needed for any third-order method. The trees are represented in a functional form in terms of the elementary symbol f.
In[18]:= **ButcherTrees[3]**

Out[18]=

This tests the validity of the syntax of two trees. Butcher trees must be constructed using multiplication, exponentiation or application of the function f.
In[19]:= **ButcherTreeQ /@ {f[f[f[f] f^2]], f[f f[f+f]]}**

Out[19]=

This evaluates the number of trees at each order through order 10. The result is equivalent to Out[2] but the calculation is much more efficient since it does not actually involve constructing order conditions or trees.
In[20]:= **ButcherTreeCount[10]**

Out[20]=

The previous result can be used to calculate the total number of trees required at each order through order 10.
In[21]:= **FoldList[ Plus, First[%], Rest[%] ]**

Out[21]=

The number of constraints for a method using row and column simplifying assumptions depends upon the number of stages. ButcherTreeSimplify gives the Butcher trees that are not reduced assuming that these assumptions hold.

This gives the additional trees that are necessary for a fourth-order method assuming that the quadrature conditions through order 4 and the row and column simplifying assumptions of order 1 hold. The result is a single tree of order 4 (which corresponds to a single fourth-order condition).
In[22]:= **ButcherTreeSimplify[4, 1, 1]**

Out[22]=

It is often useful to be able to visualize a tree or forest of trees graphically. For example, depicting trees yields insight which can in turn be used to aid in the construction of Runge-Kutta methods.

Drawing Butcher trees.

Options to ButcherPlot.

This plots and labels the trees through order 4.
In[23]:= **ButcherPlot[ #,**

ButcherPlotLabel -> (InputForm /@ #)]& @

Flatten[ ButcherTrees[4] ]

In addition to generating and drawing Butcher trees, many functions are provided for measuring and manipulating them. For a complete description of the importance of these functions, see Butcher [1].

Other functions associated with Butcher trees.

This gives the order of the tree f[f[f[f]f^2]].
In[24]:= **ButcherOrder[f[f[f[f] f^2]]]**

Out[24]=

This gives the density of the tree f[f[f[f]f^2]].
In[25]:= **ButcherGamma[f[f[f[f] f^2]]]**

Out[25]=

This gives the elementary weight function imposed by f[f[f[f]f^2]] for an

-stage method.
In[26]:= **ButcherPhi[f[f[f[f] f^2]], s]**

Out[26]=

The subscript notation is a formatting device and the subscripts are really just the indexed variable NumericalMath`Butcher`Private`$i.
In[27]:= **FullForm[%[[1,1]]]**

Out[27]//FullForm=

It is also possible to obtain solutions to the order conditions using Solve and related functions. Many issues related to the construction Runge-Kutta methods using this package can be found in Sofroniou [6]. The article also contains details concerning algorithms used in Butcher.m and discusses applications.

**References**

The Numerical Analysis of Ordinary Differential Equations: Runge-Kutta and General Linear Methods, J. C. Butcher, John Wiley and Sons, New York, 1987.

A First Course in the Numerical Analysis of Differential Equations , A. Iserles, Cambridge University Press, Cambridge, England, 1996.

Numerical Methods for Ordinary Differential Systems, The Initial Value Problem, J. D. Lambert, John Wiley and Sons, New York, 1991.

Solving Ordinary Differential Equations I: Nonstiff Problems, E. Hairer, S. P. Norsett and G. Wanner, Second edition, Springer Verlag, New York, 1993.

Solving Ordinary Differential Equations II: Stiff and Differential Algebraic Problems, E. Hairer and G. Wanner, Springer-Verlag, New York, 1991.

"Symbolic Derivation of Runge-Kutta Methods", M. Sofroniou, Journal of Symbolic Computation

, 18(3), pp. 265-296, 1994.