Numerical Differential Equation Analysis Package

The NumericalDifferentialEquationAnalysis package combines functionality for analyzing differential equations using Butcher trees, Gaussian quadrature, and Newton-Cotes quadrature.

This loads the package.
In[1]:=
Click for copyable input

Butcher

RungeKutta methods are useful for numerically solving certain types of ordinary differential equations. Deriving highorder RungeKutta methods is no easy task, however. There are several reasons for this. The first difficulty is in finding the socalled 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 twelfthorder 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 coefficient , , and . The stage RungeKutta 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 rowsum condition and is the first in a sequence of rowsimplifying 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 time step. 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 stageindependent tensor notation. In addition to the matrix and the vectors and , this notation involves the vector , 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 RungeKutta method.

For further details of the theory see the references.

ai,jthe coefficient of in the formula for of the method
bjthe coefficient of in the formula for of the method
fia notational convenience for
ea notational convenience for the vector
tthe symbol used in continuous output for RungeKutta methods

Notation used by functions for Butcher.

RungeKuttaOrderConditions[p,s]give a list of the order conditions that any sstage RungeKutta method of order p must satisfy
ButcherPrincipalError[p,s]give a list of the order p+1 terms appearing in the Taylor series expansion of the error for an order p, sstage RungeKutta method
RungeKuttaOrderConditions[p], ButcherPrincipalError[p]give the result in stageindependent tensor notation

Functions associated with the order conditions of RungeKutta methods.

ButcherRowSumspecify whether the rowsum conditions for the should be explicitly included in the list of order conditions
ButcherSimplifyspecify whether to apply Butcher's row and column simplifying assumptions

Some options for RungeKuttaOrderConditions.

This gives the number of order conditions for each order up through order 10. Notice the combinatorial explosion.
In[2]:=
Click for copyable input
Out[2]=
This gives the order conditions that must be satisfied by any firstorder, threestage RungeKutta method, explicitly including the rowsum conditions. The coefficients are denoted by formal symbols, which in the explicit notation will be subscripted.
In[3]:=
Click for copyable input
Out[3]=
These are the order conditions that must be satisfied by any secondorder, threestage RungeKutta method. Here the rowsum conditions are not included.
In[4]:=
Click for copyable input
Out[4]=

It should be noted that the sums involved on the lefthand 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 highorder, manystage 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 secondorder, stage method.
In[5]:=
Click for copyable input
Out[5]=
Replacing by gives the same result as RungeKuttaOrderConditions[2, 3].
In[6]:=
Click for copyable input
Out[6]=
These are the order conditions that must be satisfied by any secondorder method. This uses tensor notation. The vector is a vector of ones whose length is the number of stages.
In[7]:=
Click for copyable input
Out[7]=
The tensor notation can likewise be expanded to give the conditions in full.
In[8]:=
Click for copyable input
Out[8]=
These are the principal error coefficients for any thirdorder method. Note that is a vector whose components are equal to the squared components of the vector .
In[9]:=
Click for copyable input
Out[9]=
This is a bound on the local error of any thirdorder method in the limit as approaches 0, normalized to eliminate the effects of the ODE.
In[10]:=
Click for copyable input
Out[10]=
Here are the order conditions that must be satisfied by any fourthorder, onestage RungeKutta 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]:=
Click for copyable input
Out[11]=
No solutions exist.
In[12]:=
Click for copyable input
Out[12]=
RungeKuttaMethodspecify the type of RungeKutta method for which order conditions are being sought
Explicita setting for the option RungeKuttaMethod specifying that the order conditions are to be for an explicit RungeKutta method
DiagonallyImplicita setting for the option RungeKuttaMethod specifying that the order conditions are to be for a diagonally implicit RungeKutta method
Implicita setting for the option RungeKuttaMethod specifying that the order conditions are to be for an implicit RungeKutta method
$RungeKuttaMethoda global variable whose value can be set to Explicit, DiagonallyImplicit, or Implicit

Controlling the type of RungeKutta 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 RungeKutta method being considered by setting $RungeKuttaMethod to one of Implicit, DiagonallyImplicit, or 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 thirdorder, twostage diagonally implicit RungeKutta method.
In[13]:=
Click for copyable input
Out[13]=
An alternative (but less efficient) way to get a diagonally implicit method is to force to be lower triangular by replacing uppertriangular elements with 0.
In[14]:=
Click for copyable input
Out[14]=
These are the order conditions that must be satisfied by any thirdorder, twostage explicit RungeKutta method. The contradiction in the order conditions indicates that no such method is possible, a result which holds for any explicit RungeKutta method when the number of stages is less than the order.
In[15]:=
Click for copyable input
Out[15]=
ButcherColumnConditions[p,s]give the column-simplifying conditions up to and including order p for s stages
ButcherRowConditions[p,s]give the row-simplifying conditions up to and including order p for s stages
ButcherQuadratureConditions[p,s]give the quadrature conditions up to and including order p for s stages
ButcherColumnConditions[p], ButcherRowConditions[p], etc. give the result in stageindependent tensor notation

More functions associated with the order conditions of RungeKutta methods.

Butcher showed that the number and complexity of the order conditions can be reduced considerably at high orders by the adoption of socalled simplifying assumptions. For example, this reduction can be accomplished by adopting sufficient row- and column-simplifying assumptions and quadraturetype 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[16]:=
Click for copyable input
Out[16]=
These are the row-simplifying conditions up to order 4.
In[17]:=
Click for copyable input
Out[17]=
These are the quadrature conditions up to order 4.
In[18]:=
Click for copyable input
Out[18]=

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

fthe elementary symbol used in the representation of Butcher trees
ButcherTrees[p]give a list, partitioned by order, of the trees for any RungeKutta method of order p
ButcherTreeSimplify[p,η,ξ]give the set of trees through order p that are not reduced by Butcher's simplifying assumptions, assuming that the quadrature conditions through order p, the row-simplifying conditions through order η, and the column-simplifying conditions through order ξ all hold; the result is grouped by order, starting with the first nonvanishing trees
ButcherTreeCount[p]give a list of the number of trees through order p
ButcherTreeQ[tree]give True if the tree or list of trees tree is valid functional syntax, and False otherwise

Constructing and enumerating Butcher trees.

This gives the trees that are needed for any thirdorder method. The trees are represented in a functional form in terms of the elementary symbol .
In[19]:=
Click for copyable input
Out[19]=
This tests the validity of the syntax of two trees. Butcher trees must be constructed using multiplication, exponentiation, or application of the function .
In[20]:=
Click for copyable input
Out[20]=
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[21]:=
Click for copyable input
Out[21]=
The previous result can be used to calculate the total number of trees required at each order through order 10.
In[22]:=
Click for copyable input
Out[22]=

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 fourthorder 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 fourthorder condition).
In[23]:=
Click for copyable input
Out[23]=

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 RungeKutta methods.

ButcherPlot[tree]give a plot of the tree tree
ButcherPlot[{tree1,tree2,}]give an array of plots of the trees in the forest

Drawing Butcher trees.

ButcherPlotColumnsspecify the number of columns in the plot of a list of trees
ButcherPlotLabelspecify a list of plot labels to be used to label the nodes of the plot
ButcherPlotNodeSizespecify a scaling factor for the nodes of the trees in the plot
ButcherPlotRootSizespecify a scaling factor for the highlighting of the root of each tree in the plot; a zero value does not highlight roots

Options to ButcherPlot.

This plots and labels the trees through order 4.
In[24]:=
Click for copyable input
Out[24]=

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].

ButcherHeight[tree]give the height of the tree tree
ButcherWidth[tree]give the width of the tree tree
ButcherOrder[tree]give the order, or number of vertices, of the tree tree
ButcherAlpha[tree]give the number of ways of labeling the vertices of the tree tree with a totally ordered set of labels such that if is an edge, then
ButcherBeta[tree]give the number of ways of labeling the tree tree with ButcherOrder[tree]-1 distinct labels such that the root is not labeled, but every other vertex is labeled
ButcherBeta[n,tree]give the number of ways of labeling n of the vertices of the tree with n distinct labels such that every leaf is labeled and the root is not labeled
ButcherBetaBar[tree]give the number of ways of labeling the tree tree with ButcherOrder[tree] distinct labels such that every node, including the root, is labeled
ButcherBetaBar[n,tree]give the number of ways of labeling n of the vertices of the tree with n distinct labels such that every leaf is labeled
ButcherGamma[tree]give the density of the tree tree; the reciprocal of the density is the righthand side of the order condition imposed by tree
ButcherPhi[tree,s]give the weight of the tree tree; the weight Φ(tree) is the lefthand side of the order condition imposed by tree
ButcherPhi[tree]give Φ(tree) using tensor notation
ButcherSigma[tree]give the order of the symmetry group of isomorphisms of the tree tree with itself

Other functions associated with Butcher trees.

This gives the order of the tree .
In[25]:=
Click for copyable input
Out[25]=
This gives the density of the tree .
In[26]:=
Click for copyable input
Out[26]=
This gives the elementary weight function imposed by for an stage method.
In[27]:=
Click for copyable input
Out[27]=

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

Gaussian Quadrature

As one of its methods, the Wolfram Language function NIntegrate uses a fairly sophisticated GaussKronrodbased algorithm. The Gaussian quadrature functionality provided in NumericalDifferentialEquationAnalysis allows you to easily study some of the theory behind ordinary Gaussian quadrature, which is a little less sophisticated.

The basic idea behind Gaussian quadrature is to approximate the value if an integral has a linear combination of values of the integrand evaluated at specific points:

Since there are free parameters to be chosen (both the abscissas and the weights ) and since both integration and the sum are linear operations, you can expect to be able to make the formula correct for all polynomials of degree less than about . In addition to knowing what the optimal abscissas and weights are, it is often desirable to know how large the error in the approximation will be. This package allows you to answer both of these questions.

GaussianQuadratureWeights[n,a,b]give a list of the pairs to machine precision for quadrature on the interval a to b
GaussianQuadratureError [ n , f , a , b ]
give the error to machine precision
GaussianQuadratureWeights [ n , a , b , prec ]
give a list of the pairs to precision prec
GaussianQuadratureError [ n , f , a , b , prec ]
give the error to precision prec

Finding formulas for Gaussian quadrature.

This gives the abscissas and weights for the fivepoint Gaussian quadrature formula on the interval .
In[28]:=
Click for copyable input
Out[28]=
Here is the error in that formula. Unfortunately it involves the tenth derivative of at an unknown point so you do not really know what the error itself is.
In[29]:=
Click for copyable input
Out[29]=
You can see that the error decreases rapidly with the length of the interval.
In[30]:=
Click for copyable input
Out[30]=

NewtonCotes

As one of its methods, the Wolfram Language function NIntegrate uses a fairly sophisticated GaussKronrod-based algorithm. Other types of quadrature formulas exist, each with its own advantages. For example, Gaussian quadrature uses values of the integrand at oddly spaced abscissas. If you want to integrate a function presented in tabular form at equally spaced abscissas, it will not work very well. An alternative is to use NewtonCotes quadrature.

The basic idea behind NewtonCotes quadrature is to approximate the value of an integral as a linear combination of values of the integrand evaluated at equally spaced points:

In addition, there is the question of whether or not to include the end points in the sum. If they are included, the quadrature formula is referred to as a closed formula. If not, it is an open formula. If the formula is open there is some ambiguity as to where the first abscissa is to be placed. The open formulas given in this package have the first abscissa one half step from the lower end point.

Since there are free parameters to be chosen (the weights) and since both integration and the sum are linear operations, you can expect to be able to make the formula correct for all polynomials of degree less than about . In addition to knowing what the weights are, it is often desirable to know how large the error in the approximation will be. This package allows you to answer both of these questions.

NewtonCotesWeights[n,a,b]give a list of the n pairs for quadrature on the interval a to b
NewtonCotesError[n,f,a,b]give the error in the formula

Finding formulas for NewtonCotes quadrature.

option namedefault value
QuadratureTypeClosedthe type of quadrature, Open or Closed

Option for NewtonCotesWeights and NewtonCotesError.

Here are the abscissas and weights for the fivepoint closed NewtonCotes quadrature formula on the interval .
In[31]:=
Click for copyable input
Out[31]=
Here is the error in that formula. Unfortunately it involves the sixth derivative of at an unknown point so you do not really know what the error itself is.
In[32]:=
Click for copyable input
Out[32]=
You can see that the error decreases rapidly with the length of the interval.
In[33]:=
Click for copyable input
Out[33]=
This gives the abscissas and weights for the fivepoint open NewtonCotes quadrature formula on the interval .
In[34]:=
Click for copyable input
Out[34]=
Here is the error in that formula.
In[35]:=
Click for copyable input
Out[35]=